Benchmarking BigInteger

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

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!

A word about ‘out’ parameters in Delphi

Delphi compiler has a contract – any interface variable should be either a valid reference or nil. The same also applies to other lifetime managed types – strings and dynamic arrays. An interesting consequence of the contract is how Delphi interprets ‘out’ function parameters.
As the name suggests, ‘out’ means that an input value of a parameter should be ignored inside a function; but Delphi compiler cannot ignore input value of a lifetime managed instance. It decrements the reference count of an instance when an instance is no longer needed if a reference to instance is not nil.
As a workaround Delphi compiler applies the following trick. Suppose we have a procedure

procedure Foo(out II: IInterface);
begin
  II:= TInterfacedObject.Create;
end;

a call of the procedure

  Foo(II);

compiles as:

II:= nil;
Bar(II);

where

procedure Bar(var II: IInterface);
begin
  II:= TInterfacedObject.Create;
end;

Bar procedure decrements the reference count of the input parameter instance; the meaning of ‘out‘ parameter forbids to do so. Since Delphi compiler cannot ignore input value of a lifetime manage instance the problem was solved by assigning nil value to a parameter before calling a procedure.