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.

Advertisements

2 thoughts on “TInteger

  1. You can use dynamic array for this with no problems. You can simulate CoW on your TInteger by making it immutable (that’s what I did). The idea is to generate a new TInteger on each operation that is going top change its value. For example Add:

    class operator TInteger.Add(const A1, A2: TInteger): TInteger;
    begin
      SetLength(Result.FArray, Length(A1.FArray);
      Move( .. from A1.FArray to Result.FArray);
      ... Do your math on Result + A2.
    end;
    

    applying the same technique on all mutable operations and you are OK. Also note that Inc() is mapped to A := A + B if you don’t override Inc() operator. But even Inc() operator accepts a type and returns another so you can always adhere to immutability rules.

    But yes, using interfaces in this case has its own advantages over dyn arrays.

    • “Immutable values” is exactly the term I missed (I was saying about “avoiding in-place operations” meaning the immutable values). Yes, if you adhere to immutable dynamic arrays you have no troubles. You can get performance gain by making the values mutable, but as I tried to explain in the post that is not so easy and you should take into account reference counting.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s