BigInteger redux

11

TForge 0.72 is released.

What’s new:

  • Big integer arithmetic is included in TForge package; that is BigCardinal and BigInteger classes are now available after installing TForge package, without dll. Old dll implementation (Numerics 0.58) is still available but is not developed for now.
  • More demo projects added.
  • Improved FPC/Lazarus support; TCiphers package and demos are ported to FPC/Lazarus.
  • Several new methods are added to ByteArray class.
Advertisements

Numerics 0.57 released (Hashtables, Bugfix)

2

1. The main purpose of the release is to implement hash tables (aka associative arrays) with keys of BigCardinal or BigInteger type; such hash tables are important for cryptographic applications. The hash tables in Delphi are implemented by a generic TDictionary<TKey,TValue> class. The release includes a new unit GNumerics.pas with two helper generic classes TBigIntegerDictionary<TValue> and TBigCardinalDictionary<TValue> specializing the base generic dictionary class. For example to work with a hash table having BigInteger keys and string values you need something like this:

uses GNumerics;

[..]
var
  HashTable: TBigIntegerDictionary<string>;
  A: BigInteger;

[..]
begin
// create hash table instance
  HashTable:= TBigIntegerDictionary<string>.Create;
  A:= BigInteger('1234567890987654321');
  try
// fill hash table with data
    HashTable.Add(A * A, 'some string value');
    [..]
  finally
// destroy hash table
    HashTable.Free;
  end;
end;

2. Some bugs fixed; in particular a nasty access violation bug in BigInteger.ModPow function was fixed.

3. Minor changes in BigCardinal/BigInteger methods.

Link to the download page

Update

Version 0.58 fixes the conversion bug from (U)Int64 to BigInteger/BigCardinal.

Numerics 0.55 released

0

Numerics 0.55 is available for download

The main improvements are:

1) Explicit DLL load is supported by the function

function LoadNumerics(const Name: string = ''): TF_RESULT;

and this is now the recommended method to load the dll because it enables error handling:

if LoadNumerics() < 0 then
  raise Exception.Create('!!! - DLL load error');

if the LoadNumerics was not called the dll is loaded transparently when needed.

2) More BigInteger functions implemented:

2.1) Integer square root:

    class function Sqrt(A: BigInteger): BigInteger; static;

2.2) Euclid algorithm (aka Greatest Common Divisor) and Extended Euclid algorithm:

    class function GCD(A, B: BigInteger): BigInteger; static;
    class function EGCD(A, B: BigInteger; var X, Y: BigInteger): BigInteger; static;

2.3) Modular arithmetic:

    class function ModPow(const BaseValue, ExpValue, Modulo: BigInteger): BigInteger; static;
    class function ModInverse(A, Modulo: BigInteger): BigInteger; static;

Most of the above functions were written while I was doing the programming assignments of the Coursera Cryptography 1 course by prof. Dan Boneh. It was fun to use my own BigInteger implementation.

3) C++ support added. I used free CodeBlocks IDE to port the PiBench console application to C++.

Merry Christmas and Happy New Year!

Numerics for Delphi & FPC

20

I “officially” released first beta version of my multiple-precision integer arithmetic implementation – Numerics050. The project taken more time than I expected but now the design (I hope) become stable.

All that is needed to use BigCardinal and BigInteger types with Delphi or Lazarus/FPC is a single pascal unit Numerics.pas and a single dll (numerics32.dll for 32-bit Windows and numerics64.dll for 64-bit Windows). Both dll are built by FPC 2.6.2 and contain pure Pascal code without assembler optimization.

The archive also contains console application PiBench (for Delphi and Lazarus) which demonstrates how to use BigCardinal and BigInteger types (not much different from plain old Cardinal and Integer types).

The software contained in the archive (compiled dll’s numerics32.dll and numerics64.dll, dll wrapper unit Numerics.pas and demo benchmark application PiBench) is free and released under MIT license.

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.

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!