INGENIEURBÜRO LANG

Manchmal benötigt man ja die Multiplikation oder Division beliebig großer Zahlen (Addition und Subtraktion natürlich auch), vor allem wenn man sich mit Primzahlen und ähnlichen Problemen beschäftigt. Theoretisch kann man in Delphi mit `beliebig großen´ Zahlen rechnen (die Hilfe sagt dazu, dass ‘Extended’ Zahlen bis 1,1 * 10 ^ 4932 aufnehmen kann, und das ist schon ganz schön `beliebig groß´). Nur nützt das leider nichts, wenn man alle und nicht nur 19 bis 20 Stellen wissen will oder muss.

Um beliebig große Zahlen zu speichern und ohne irgendwelche Überlauf-Fehler zu berechnen, ist es sinnvoll, diese in einem Cardinal-Array (32 Bit ohne Vorzeichen) abzulegen. Wenn man zwei Cardinal-Zahlen miteinander multipliziert, erhält man maximal eine UInt64 (gibt´s seit Delphi 2007). Addition und Subtraktion sind in Bezug auf Überlauffehler unkritischer, die Division nutzt an verschiedenen Stellen wieder die Multiplikation zweier Cardinals.

Geht man von einem objektorientierten Ansatz aus, kann man eigentlich auch gleich die beliebig großen Ganzzahlen (VLI - very long integer) in einem Objekt kapseln. Die Deklaration folgt dann hier:

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;

 Jetzt ist es möglich, mit

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

eine VLI anzulegen oder auch auf dem zweiten Weg

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

 erst eine VLI zu erzeugen und dann den Wert zuzuweisen.

Die eigentlichen Grundrechenoperationen übernehmen die Methoden Add, Subtract, Multiply und Divide. Alle Methoden sind überladen, um verschiedenen Varianten des Aufrufs gerecht zu werden. Zum Beispiel erwartet die Methode

procedure Multiply(const Y: TVLI);

einen Parameter, und weist das Ergebnis dann `sich selbst´ zu, während die Methode

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

drei VLIs benötigt, zwei für die Faktoren X und Y und eine für das Ergebnis.

Eine Multiplikation kann man nun folgendermaßen vornehmen:

var
  Faktor1, Faktor2, Ergebnis: TVLI;
  ...
begin  
  Faktor1 := TVLI.Create(`123456789012345678901234567890´);
  Faktor2 := TVLI.Create(`987654321987654321987654321987´);
  Ergebnis := TVLI.Create;
  try
    Ergebnis.Multiply(Faktor1, Faktor2);
    // und irgendwohin mit dem Ergebnis
    Label1.Caption := Ergebnis.AsString;
  finally
    Faktor1.Free;
    Faktor2.Free;
    Ergebnis.Free;
  end;
end;

 Den kompletten Quellcode gibt es hier:

An dieser Stelle noch vielen Dank an Herrn Prof. Harley Flanders, University of Michigan, für seine Anregungen.