Arbitrary precision integers

I have decided to extract the BigInteger and BigCardinal data types from DeHL and make a bundle with them separately. Someone may be interested in these types and not so much in DeHL. The attached unit should compile on D2007 and D2006 (not sure for earlier versions).

What can you learn:

  • Shows you how to develop “value types” with predictable states in Delphi using records, operator overloading and “managed types” (in this case a dynamic array).
  • How to develop a proxy class that plugs your type into the Variant manager.
  • Demonstrates how to use operator overloading (and I have overloaded a lot of operators there).
  • The reliance of the predictable state of the managed types to check whether a value is initialized or not.
  • Shows how the use an in-place BCD-izer algorithm that helps converting a big number into a string. It took me a quite some time and tweaking to come up with it so it may be interesting to someone.

Where can you use it:

  • Everywhere, except FOR loops of course.
  • The types are transparent and should be used the exact way as normal integer do.
  • Use it in applications that require very big integer values.
  • … you’ll come up with something else.

A small example of course:

var
  a, b: BigInteger;
begin
  a := StrToBigInteger('8942374632463284632623837643468589' + 
        '26367423509458904389575645349857');
  b := a * a;
  WriteLn(IntToStr(b));
end.

… or as variants …

var
  a, b: Variant;
begin
  a := StrToBigInteger('8942374632463284632623837643468589' + 
        '26367423509458904389575645349857');
  b := a * a;
  WriteLn(b);
end.

Final note: the code is tested since it’s a part of DeHL (in which I try to test everything I can) so it’s safe to use. BUT if you find any bugs, please drop me a line.

Finally! The code! You can find it here: [download#39]

7 Comments

  1. You say that these are value types. I had a look at the code and see that the records contain dynamics arrays. You also perform value copies of the record types which results value copies of the dynamic arrays.

    Since dynamic arrays are reference types (not copy on write like strings) doesn’t this make those copies actually reference copies? I don’t have a modern enough version of Delphi (I’m still on D6) but what would happen for code like this:

    var
    a, b: BigInteger;
    begin
    a := 1;
    b := a;
    a := 2; //what would be in b?
    end;

    Ah, now I think I see it! In the line a := 2 what results is a call to

    constructor BigInteger.Create(const ANumber: Integer)

    and this disconnects a from b. Is that right?

    If that is so then can we think of this technique as a way to get “copy on write” semantics for dynamic arrays?

    Very interesting stuff!

  2. You can think of it as way of a delayed “copy on write”, where this copy is made only when it is actually needed. This is much more performance efficient in compare to always copying the contents each time you may only want to duplicate a reference, becaues reference copy is low cost and deep copy is high cost.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.