Calculation with very long integers in Delphi

Sometimes it is necessary to multiply or divide very long integers (of course also to add and subtract) especially in the area of prime numbers and related problems. Basically Delphi is able to deal with very long integers (Extended can hold large numbers to 1.1 * 104932). But this is not of any use if one wants to know all and not only 20 digits.

To store very large integers and to deal with it is sensible to use an array of Cardinal (32 bit without sign). Multiplying two Cardinal numbers gives a result of INT64 (included since Delphi 2007). Addition and subtraction are uncritical as far as overflow is concerned, division uses multiplying of two Cardinal numbers.

Starting with an object-oriented approach one could encapsulate the very large integer into an object. Have a look at the declaration:

TVLI = class(TObject)
private
  // FIntAr represents the very long integer
  // FIntAr[0] + FIntAr[1] * Base + FIntAr[2] * Base^2 + ..
  FVLIAr: TIntAr;
  // FMinus holds the (negative) sign
  FMinus: Boolean;
  function GetAsFloat: Extended;
  function GetAsHex: AnsiString;
  function GetAsInt64: Int64;
  function GetAsInteger: Integer;
  function GetAsString: AnsiString;
  function GetIsZero: Boolean;
  function GetLenVLI: Integer;
  procedure Adjust;
  procedure Clean;
  procedure ComplementOnTwo;
  procedure Divide(const Value: Cardinal; out Remainder: Cardinal); overload;
  procedure Multiply(const Value: Cardinal); overload;
  procedure SetAsFloat(Value: Extended);
  procedure SetAsHex(Value: AnsiString);
  procedure SetAsInt64(const Value: Int64);
  procedure SetAsInteger(const Value: Integer);
  procedure SetAsString(Value: AnsiString);
  procedure SetLenVLI(const Value: Integer);
  property LenVLI: Integer read GetLenVLI write SetLenVLI;
public
  constructor Create; overload;
  constructor Create(const Value: AnsiString); overload;
  constructor Create(const Value: Int64); overload;
  constructor Create(const Value: Integer); overload;
  destructor Destroy; override;
  procedure Abs;
  procedure Add(const Value: Int64); overload;
  procedure Add(const Value: Integer); overload;
  procedure Add(const X, Y: TVLI); overload;
  procedure Add(const Y: TVLI); overload;
  procedure Assign(Source: TVLI);
  procedure Clear;
  function Compare(const X: TVLI): Integer; overload;
  function CompareAbs(const X: TVLI): Integer; overload;
  procedure Dec;
  procedure Divide(const Value: Int64; out Remainder: Int64); overload;
  procedure Divide(const Value: Integer; out Remainder: Integer); overload;
  procedure Divide(const X, Y: TVLI; out Remainder: TVLI); overload;
  procedure Divide(const Y: TVLI; out Remainder: TVLI); overload;
  function Equal(const X: TVLI): Boolean; overload;
  procedure GCD(const X, Y: TVLI); overload;
  procedure GCD(const Y: TVLI); overload;
  procedure Inc;
  procedure Multiply(const Value: Int64); overload;
  procedure Multiply(const Value: Integer); overload;
  procedure Multiply(const X, Y: TVLI); overload;
  procedure Multiply(const Y: TVLI); overload;
  procedure Negate;
  function Odd: Boolean;
  procedure Power(const Exponent: Cardinal); overload;
  procedure Power(const X: TVLI; Exponent: Cardinal); overload;
  procedure ShiftLeft(const N: Cardinal); overload;
  procedure ShiftLeft(const X: TVLI; N: Cardinal); overload;
  procedure ShiftRight(const N: Integer); overload;
  procedure ShiftRight(const X: TVLI; N: Integer); overload;
  function Sign: Integer;
  procedure Sqr(const X: TVLI); overload;
  procedure Sqr; overload;
  procedure Subtract(const Value: Int64); overload;
  procedure Subtract(const Value: Integer); overload;
  procedure Subtract(const X, Y: TVLI); overload;
  procedure Subtract(const Y: TVLI); overload;
  property AsFloat: Extended read GetAsFloat write SetAsFloat;
  property AsHex: AnsiString read GetAsHex write SetAsHex;
  property AsInt64: Int64 read GetAsInt64 write SetAsInt64;
  property AsInteger: Integer read GetAsInteger write SetAsInteger;
  property AsString: AnsiString read GetAsString write SetAsString;
  property IsZero: Boolean read GetIsZero;
end;

Now it is possible to create a VLI with

var
  VLI: TVLI;
  ...
  VLI := TVLI.Create(`123456789012345678901234567890´);

The second option creates first the VLI and then assigns the value.

  VLI := TVLI.Create;
  VLI.AsString := `123456789012345678901234567890´;

Add, Subtract, Multiply and Divide are the basic calculating operations. All methods are overloaded to fit different invocations. For example, the next method

procedure Multiply(const Y: TVLI);

expects one parameter and assigns the result to itself. Whereas the method

procedure Multiply(const X, Y: TVLI); overload;

requires three VLIs,  two to hold the factors X and Y and one to collect the result.

Follow the next lines to multiply two VLIs:

var
  Factor1, Factor2, Res: TVLI;
  ...
begin  
  Factor1 := TVLI.Create(`123456789012345678901234567890´);
  Factor2 := TVLI.Create(`987654321987654321987654321987´);
  Res := TVLI.Create;
  try
    Res.Multiply(Factor1, Factor2);
    // put the result somewhere
    Label1.Caption := Res.AsString;
  finally
    Factor1.Free;
    Factor2.Free;
    Res.Free;
  end;
end;

The source is available for download:

VLI.PAS

Many thanks to Prof. Harley Flanders, University of Michigan, for his suggestions.