On the operator overloading in Delphi

4

The operator overloading in Delphi records is straightforward if a record type does not contain fields which reference heap objects. To illustrate the problem which heap references arise let us consider the following (incorrect) example:

program DelphiDemo;

{$APPTYPE CONSOLE}

uses
  SysUtils;

type
  Adder = record
  private
    FRef: PInteger;
    function GetMemory: Integer;
    procedure SetMemory(AValue: Integer);
  public
    procedure Init(AValue: Integer = 0);
    procedure Done;
    class operator Add(const A, B: Adder): Adder;
    property Memory: Integer read GetMemory write SetMemory;
  end;

{ Adder }

class operator Adder.Add(const A, B: Adder): Adder;
begin
// !!! Memory leak
  New(Result.FRef);
  Result.Memory:= A.Memory + B.Memory;
end;

procedure Adder.Done;
begin
  Dispose(FRef);
end;

function Adder.GetMemory: Integer;
begin
  Result:= FRef^;
end;

procedure Adder.Init(AValue: Integer);
begin
  New(FRef);
  FRef^:= AValue;
end;

procedure Adder.SetMemory(AValue: Integer);
begin
  FRef^:= AValue;
end;

procedure Test;
var
  A, B, C: Adder;

begin
  A.Init(1);
  B.Init(2);
  C.Init();
  C:= A + B;
  Writeln(C.Memory);
  C.Done;
  B.Done;
  A.Done;
end;

begin
  ReportMemoryLeaksOnShutdown:= True;
  try
    Test;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
  ReadLn;
end.

The line #59 (C:= A + B) in the above program works as follows:

  • A temporary Result record is pushed on stack
  • The temporary record receives the sum A + B
  • The temporary record is assigned (by shallow copying) to the C variable
  • The temporary record is popped from stack

It would work fine if Adder did not reference a heap data; the FRef of the Adder record field makes things complicated. You should always initialize FRef field for every Adder instance but you can’t finalize it for a temporary record that is created on line #59. The only way to solve the memory leak issue in the above code is to comment out the line #58, but it will not work for more complicated right-hand side expressions and it is not a solid approach anyway.

The correct solution involves using a type with automatic memory management instead of a simple pointer. Here is a solution that uses interface:

program DelphiDemo2;

{$APPTYPE CONSOLE}

uses
  SysUtils, Classes;

type
  IAdder = interface
    function GetMemory: Integer;
    procedure SetMemory(AValue: Integer);
  end;

  TAdderRef = class(TInterfacedObject, IAdder)
  private
    FMemory: Integer;
    function GetMemory: Integer;
    procedure SetMemory(AValue: Integer);
  end;

  Adder = record
  private
    FRef: IAdder;
    function GetMemory: Integer;
    procedure SetMemory(AValue: Integer);
  public
    procedure Init(AValue: Integer = 0);
    procedure Done;
    class operator Add(const A, B: Adder): Adder;
    property Memory: Integer read GetMemory write SetMemory;
  end;

{ TAdderRef }

function TAdderRef.GetMemory: Integer;
begin
  Result:= FMemory;
end;

procedure TAdderRef.SetMemory(AValue: Integer);
begin
  FMemory:= AValue;
end;

{ Adder }

class operator Adder.Add(const A, B: Adder): Adder;
begin
  Result.FRef:= TAdderRef.Create;
  Result.Memory:= A.Memory + B.Memory;
end;

procedure Adder.Init(AValue: Integer);
begin
  FRef:= TAdderRef.Create;
  FRef.SetMemory(AValue);
end;

procedure Adder.Done;
begin
  FRef:= nil;
end;

function Adder.GetMemory: Integer;
begin
  Result:= FRef.GetMemory;
end;

procedure Adder.SetMemory(AValue: Integer);
begin
  FRef.SetMemory(AValue);
end;

procedure Test;
var
  A, B, C: Adder;

begin
  A.Init(1);
  B.Init(2);
//  C.Init();
  C:= A + B;
  Writeln(C.Memory);
//  C.Done;
//  B.Done;
//  A.Done;
end;

begin
  ReportMemoryLeaksOnShutdown:= True;
  try
    Test;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
  ReadLn;
end.

A nice side effect of the above approach is that you need not initialize or finalize the FRef fields manually anymore (though you can still do it). Some lines in the Test procedure above were commented out because they are not needed, but they can be uncommented and the code will remain correct – automatic memory management of interfaces takes care of it.

It is very interesting to know how the problem discussed above is solved in C++. The standard C++ approach is totally different – it involves overloading the assignment operator (a feature which Delphi does not support; Delphi allows to overload only conversionImplicit, Explicit operators) and writing a copy constructor (another concept absent in Delphi object model). I am planning to discuss it later.

On the Pointers and References

6

A Reference is a distinct concept in C/C++ languages. The next code sample (MinGW GCC compiler was used)

#include <iostream>

int main()
  {
    int Value;
    int &ValueRef = Value;

    Value = 2;
    std::cout << "Value: " << Value << "\n";
    std::cout << "ValueRef: " << ValueRef << "\n";

    ValueRef = 3;
    std::cout << "Value: " << Value << "\n";
    std::cout << "ValueRef: " << ValueRef << "\n";
    return 0;
  }

declares ValueRef as a reference to Value variable. The output is
_ref1
Though ValueRef variable is a pointer to Value internally the indirection operator is never used, and the syntax for accessing Value directly or indirectly via ValueRef is the same. ValueRef is also called an alias to Value; the point that ValueRef variable is a pointer internally is just an implementation detail.

Another important thing about C/C++ references is that they are always initialized. The language syntax enforces that you cannot declare a wild reference.

Pascal does not have the same reference concept. The closest concept is a procedure parameter passed by reference:

program ref;

{$APPTYPE CONSOLE}

var
  Value: Integer;

procedure Test(var ValueRef: Integer);
begin
  Writeln('ValueRef: ', ValueRef);
  ValueRef:= 3;
end;

begin
  Value:= 2;
  Writeln('Value: ', Value);
  Test(Value);

  Writeln('Value: ', Value);
  Test(Value);
end.

we can see that

  • ValueRef does not use indirection operator to access a referenced variable;
  • the language syntax enforces that ValueRef is always initialized.

Delphi does not elaborate the reference concept, though there are many built-in types in the language that are ‘transparent pointers’ – objects, interfaces, dynamic arrays, strings. The term reference can be used for example for object variables because the language syntax makes these variables indistinguishable from referenced instances. Instead the term object is usually used, that can mean object reference or object instance, so sometimes you think twice to understand what a particular object does mean.

Bitwise operations on big integers

0

Standard fixed-sized negative integers are stored in two’s complement format; for arbitrary-precision big integers the two’s complement format means infinite size, so internally it is not used. Still bitwise operation on big integers are implemented as if negative big integer values are stored in two’s complement format.

As a result bitwise boolean operations (and, or, xor) applied to big integers produce the same results as with standard fixed-sized integers:

procedure Test1(I, J: Integer);
var
  BigI, BigJ: BigInteger;

begin
  BigI:= I;
  BigJ:= J;
  Assert(BigI and BigJ = I and J);
  Assert(BigI or BigJ = I or J);
  Assert(BigI xor BigJ = I xor J);
end;

There is a difference between standard Delphi integer types and big integers in shift operations. Shift operations on big integers preserve sign. That means any shift applied to negative big integer results in negative big integer (the same is for non-negative values):

procedure Test2(I: BigInteger; N: Cardinal);
begin
  Assert(((I shl N) < 0) = (I < 0));
  Assert(((I shr N) < 0) = (I < 0));
end;

That is a natural consequence of the infinite-sized two’s complement negative values. Shift operations on big integers are arithmetic shifts rather than logical shifts. On the other hand ‘shl’ and ‘shr’ operations on the standard Delphi integer types are implemented as logical shifts and does not preserve sign:

procedure Test3;
var
  I: Integer;

begin
  I:= -1;
  Writeln(I shr 2);   // 1073741823, because 'shr' is logical shift
  I:= 1000000000;
  Writeln(I shl 2);   // -294967296, because of 32-bit overflow
end;

PS: right now TForge does not support bitwise operations on BigInteger type, they will be implemented soon.

Be careful with Ord function in Unicode Delphi versions

17

Here is a simple test:

program OrdTest;

{$APPTYPE CONSOLE}

uses
  SysUtils;

begin
  try
    Writeln(Ord('Я'), '  ', Ord(Char('Я')));   // 223,  1071
    Assert(Ord('Я') = Ord(Char('Я')));         // Fails
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
  Readln;
end.

While evaluating the Ord function with hardcoded character parameter the compiler treats the parameter as ANSI character. In the above example Ord(‘Я’) returns 223 (Cyrillic codepage 1251) instead of 1071 (UTF16) as one could expect. As a result the assertion fails (tested on Delphi XE):
assertion failed

After reading the comments I tried another test with both Cyrillic ‘Я’ (=223 on 1251 codepage) and German ‘ß’ (=223 on 1252 codepage):

program OrdTest2;

{$APPTYPE CONSOLE}

uses
  SysUtils;

begin
  try
    Writeln(Ord('Я'), '  ', Ord(Char('Я')));
    Writeln(Ord('ß'), '  ', Ord(Char('ß')));
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
  Readln;
end.

if I set the compiler’s codepage to 1251 I get

if I set the compiler’s codepage to 1252 I get

because German ‘ß’ has the same code (223) both in ANSI 1252 codepage and UTF16 encoding.

Benchmarking BigInteger

0

Last TForge commits contain PiBench console application that calculates decimal digits of Pi using Machin’s formula; the execution takes about 30 seconds on my laptop. The code was written to compare the execution time of subsequent TForge revisions, but it can also be used to compare TForge BigCardinal and BigInteger types with .NET 4.0 BigInteger type.

Here is Delphi PiBench code:

program PiBench;

{$APPTYPE CONSOLE}

uses
  SysUtils, Diagnostics, tfNumerics;

var
  StopWatch: TStopWatch;
  PiDigits: BigCardinal;

procedure BenchMark;
var
  Factor, Num, Den: BigCardinal;
  Term: BigCardinal;
  N, M: Cardinal;

begin
  PiDigits:= 0;
  Factor:= BigCardinal.Pow(10, 10000);
  Num:= 16 * Factor;
  Den:= 5;
  N:= 1;
  repeat
    Term:= Num div (Den * (2 * N - 1));
    if Term = 0 then Break;
    if Odd(N)
      then PiDigits:= PiDigits + Term
      else PiDigits:= PiDigits - Term;
    Den:= Den * 25;
    Inc(N);
  until N = 0;
  M:= N;
  Num:= 4 * Factor;
  Den:= 239;
  N:= 1;
  repeat
    Term:= Num div (Den * (2 * N - 1));
    if Term = 0 then Break;
    if Odd(N)
      then PiDigits:= PiDigits - Term
      else PiDigits:= PiDigits + Term;
    Den:= Den * 239 * 239;
    Inc(N);
  until N = 0;
  M:= (M + N) div 2;
// M last digits may be wrong
  PiDigits:= PiDigits div BigCardinal.Pow(10, M);
end;

begin
  ReportMemoryLeaksOnShutdown:= True;
  try
    Writeln('Benchmark test started ...');
    StopWatch:= TStopWatch.StartNew;
    BenchMark;
    StopWatch.Stop;
    Writeln(PiDigits.AsString);
    PiDigits.Free;
    Writeln;
    Writeln('Elapsed ms: ', StopWatch.ElapsedMilliseconds);
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
  Readln;
end.

And here is equivalent C# application:

using System;
using System.Numerics;
using System.Diagnostics;

namespace PiBench
{
    class Program
    {
        static void Main(string[] args)
        {
            int N, M;
            BigInteger Term;
            Console.WriteLine("Benchmark test started ...");
            Stopwatch Watch = new Stopwatch();
            Watch.Start();
            BigInteger PiDigits = 0;
            BigInteger Factor = BigInteger.Pow(10, 10000);
            BigInteger Num = 16 * Factor;
            BigInteger Den = 5;
            for(N = 1; N != 0; N++){
              Term = Num / (Den * (2 * N - 1));
              if (Term == 0) break;
              if ((N & 1) != 0) PiDigits = PiDigits + Term;
              else PiDigits = PiDigits - Term;
              Den = Den * 25;
            }
            M = N;
            Num = 4 * Factor;
            Den = 239;
            for(N = 1; N != 0; N++){
              Term = Num / (Den * (2 * N - 1));
              if (Term == 0) break;
              if ((N & 1) != 0) PiDigits = PiDigits - Term;
              else PiDigits = PiDigits + Term;
              Den = Den * 239 * 239;
            }
            M = (M + N) / 2;
       // M last digits may be wrong
            PiDigits = PiDigits / BigInteger.Pow(10, M);
            Watch.Stop();
            Console.WriteLine(PiDigits);
            Console.WriteLine();
            Console.WriteLine("Elapsed ms: " + Watch.ElapsedMilliseconds.ToString());
            Console.ReadLine();
        }
    }
}

You can run both and compare; my tests show nearly the same execution time.

TForge

0

My interface-based arbitrary precision integer arithmetic implementation for Delphi and Free Pascal now is a project on BitBucket.
Currently TForge is a single runtime package (tforge.dpk; future releases will also include a language agnostic dll); you can download the project, build the package and start hacking with BigCardinal and BigInteger types by adding tfNumerics unit to uses clause.
The code is not fully tested yet and not optimized at all, so use it carefully.

Here are some implementation details:

1. BigInteger and BigCardinal variables are initialized by assignment:

var A: BigCardinal;
    B: BigInteger;

begin
   A:= 1;
   B:= 2;
   Writeln(A.AsString, ', ', B.AsString);
   ..

2. No need to finalize BigInteger and BigCardinal variables, the compiler does cleanup when a variable goes out of scope; still you can finalize explicitly by Free method. You can also reuse a ‘Freed’ variable:

var A: BigCardinal;

   A:= 1;
   A.Free;
   A:= 10;
   Writeln(A.AsString);

3. Strings can be explicitly casted to BigInteger and BigCardinal types; you can also use TryFromString method to assign a string value to a BigInteger or BigCardinal variable:

var A: BigCardinal;
    B: BigInteger;

begin
  try
   A:= 1;
   B:= BigInteger('1234567890987654321');
   if not A.TryFromString('Wrong string')
     then Writeln('Bad value');
   Writeln(A.AsString, ', ', B.AsString);

4. BigInteger accommodates BigCardinal, so BigCardinal is implicitly casted to BigInteger, and BigInteger is explicitly casted to BigCardinal:

var A: BigCardinal;
    B: BigInteger;

begin
  A:= 1;
  B:= A; // never raises exception
  A:= BigCardinal(B); // no exception here
  B:= -1;
  A:= BigCardinal(B); // exception – negative value
  ..

5. BigInteger and BigCardinal variables can be mixed in Boolean expressions, with BigCardinal casted to BigInteger:

var A: BigCardinal;
    B: BigInteger;

begin
    A:= 1;
    B:= -2;
    if (A > B) then B:= 0;
    ..

6. BigInteger and BigCardinal variables can be mixed in arithmetic expressions, with BigCardinal casted to BigInteger:

var A: BigCardinal;
    B: BigInteger;

begin
    A:= 10;
    B:= -42;
    Writeln( (A * B).AsString);

The project has a public bug tracker, bug reports are welcome!