TInteger

Since the introduction of operator overloading in Delphi one can easily define custom data types that support arithmetic operations. For example it is quite easy to implement arithmetic of complex numbers like this:

type
  PComplex = ^TComplex;
  TComplex = record
    Re, Im: Extended;

    class operator Implicit(const A: Extended): TComplex;

    class operator Add(const A, B: TComplex): TksComplex;
    class operator Subtract(const A, B: TComplex): TComplex;
    class operator Multiply(const A, B: TComplex): TComplex;
{...}

Note that TComplex is a static type with fixed data size (Re, Im fields) and is normally allocated on stack. The problems arise when you need to implement arithmetic on dynamic data allocated on heap.
If you are about to implement big integer (TInteger) arithmetic you have two alternatives.
First, you can stick to static data types; that means that you should limit maximum number value in the implementation.
The second alternative is to use dynamic type to allocate the numbers, so there is no need to introduce artificial limits on maximum number value.

The first approach is obvious, the second is more interesting.
You can’t use GetMem/FreeMem to allocate/deallocate the numbers on heap because memory deallocation should be performed automatically by the compiler, and you just cannot instruct the compiler to call FreeMem for temporary TInteger value while evaluating arithmetic expression like

A:= (B + C) * D;

Consequently, the dynamic type to hold the number data should be lifetime-managed type – and the dynamic array seems to be the most probable candidate:

type
  TInteger = record
  private
    FData: array of LongWord;
{...}

The above implementation forbids “in-place” operations on TInteger variables – the reason is a side effect of TInteger assignment. Dynamic arrays do not support copy-on-write, so the following assertion will fail:

var
  A, B: TInteger;

begin
  A:= 1;
  B:= A;
  Inc(A);
  Assert(B=1);
end;

After B:= A both A.FData and B.FData reference the same data, so that after Inc(A) we have B = 2.

Now we have 3 alternatives:

• we can avoid completely the in-place operations on TInteger;
• we can use undocumented format of dynamic array to implement TInteger “copy-on-write” by hacking dynamic array’s reference count before calling in-place operations;
• we can use interfaces.

(Well, there are lifetime-managed data types in Delphi that support “copy-on-write” semantic – strings, but they can’t help us since we need some low-level hacking to manipulate the binary data in string format and “copy-on-write” will not work as we need).

Let us try the following:

type
  PIntegerData = ^TIntegerData;
  TIntegerData = record
    Size: LongInt;   // number of allocated longwords in Data
    Data: array[0..0] of LongWord;
  end;

  IInteger = interface
    function GetData: PIntegerData;
    function GetRefCount: Integer;
  end;

  TIntegerObject = class(TInterfacedObject, IInteger)
  private
    FData: PIntegerData;
  public
    constructor Create(Limbs: Integer);
    destructor Destroy; override;
    function GetData: PIntegerData;
    function GetRefCount: Integer;
  end;

  TInteger = record
  private
    FInteger: IInteger;
{..}

The implementation based on interfaces is the most “correct”. It does not use any dirty hacking or undocumented features to get reference count and implement “copy-on-write”. The bad thing is that the above implementation has the worst performance. For example, to allocate a single TInteger value you need to allocate two memory blocks on heap – first for a TIntegerObject and second for TIntegerData referenced by the TIntegerObject.

All in all, a TInteger implementation based on dynamic arrays (with or without refcount hacking) looks most optimal today.