HugeInt_Div

[Bjoerk]

Ich habe mich das Wochenende etwas mit dieser Unit beschäftigt.

http://www.esanu.name/delphi/Algorit...20numbers.html

Läuft soweit ganz gut, nur eine Sache daran ist merkwürdig. Bei der Division kommen falsche Ergebnisse, falls die Ergebnisse ein Vielfaches von 256 sind. So wird zum Beispiel bei 7689 div 10 als Ergebnis 3 anstatt 768 ausgeben.

Da ich diesen Code nicht wirklich verstehe, wollte ich den Fehler einfach mal weiterreichen. Vielleicht hat ihn ja schon jemand korrigiert oder vielleicht hat ja jemand Zeit und Lust..

Delphi-Quellcode:

unit uHugeIntDiv;

(*
procedure TForm1.Button1Click(Sender: TObject);
begin
  // stimmt soweit alles ..
  ShowMessage(HugeIntToStr(HugeIntDiv(IntToHugeInt(7689), IntToHugeInt(5))));

  // .. außer, wenn Ergebnisse i*256 sind,
  // dann wird statt i*256 i ausgegeben !?
  ShowMessage(HugeIntToStr(HugeIntDiv(IntToHugeInt(7689), IntToHugeInt(10))));
end;

-> procedure HugeInt_DivMod(var A: HugeInt; B: HugeInt; var R: HugeInt);
*)

interface

const
  HugeIntSize = 1024;

type
  HugeInt = array [0..HugeIntSize-1] of byte;

  function HugeIntDiv(A, B: HugeInt): HugeInt;
  function StrToHugeInt(AString: string): HugeInt;
  function IntToHugeInt(AInteger: Integer): HugeInt;
  function HugeIntToStr(A: HugeInt): string;

implementation

function Null: HugeInt;
begin
  FillChar(Result, SizeOf(HugeInt), 0);
end;

function HugeInt_Zero(A: HugeInt): boolean;
var
  I: integer;
begin
  Result:= true;
  for I:= 0 to HugeIntSize-1 do
    if A[I] <> 0 then
    begin
      Result:= false;
      Break;
    end;
end; { HugeInt_Zero }

function HugeInt_HCD(A: HugeInt): integer;
var
  I: integer;
begin
  I:= HugeIntSize-1;
  while (I > 0) and (A[I] = 0) do Dec(I);
  Result:= I;
end; { HugeInt_HCD }

procedure HugeInt_SHL(var A: HugeInt; Digits: integer);
{ Shift "A" "Digits", digits (bytes) to the left,
"Digits" bytes will 'fall off' on the MSB side
 Fill the LSB side with 0's }
begin
  if Digits > HugeIntSize-1 then
    FillChar(A, SizeOf(HugeInt), 0)
  else
    if Digits > 0 then
    begin
      Move(A[0], A[Digits], HugeIntSize-Digits);
      FillChar(A[0], Digits, 0);
    end; { else if }
end; { HugeInt_SHL }

procedure HugeInt_Inc(var A: HugeInt);
{ A := A + 1 }
var
  I: integer;
  H: Word;
begin
  I:= 0;
  H:= 1;
  repeat
    H:= H + A[I];
    A[I]:= Lo(H);
    H:= Hi(H);
    Inc(I);
  until (I > HugeIntSize-1) or (H = 0);
end; { HugeInt_Inc }

procedure HugeInt_Add(A, B: HugeInt; var R: HugeInt);
{ R := A + B }
var
  I: integer;
  H: Word;
begin
  H:= 0;
  for I:= 0 to HugeIntSize-1 do
  begin
    H:= H + A[I]+ B[I];
    R[I]:= Lo(H);
    H:= Hi(H);
  end; { for }
end; { HugeInt_Add }

procedure HugeInt_Min(var A: HugeInt);
{ A := -A }
var
  I: integer;
begin
  for I:= 0 to HugeIntSize-1 do
    A[I]:= not A[I];
  HugeInt_Inc(A);
end; { HugeInt_Min }

function HugeInt_IsNeg(A: HugeInt): boolean;
begin
  Result:= A[HugeIntSize-1] and $80 > 0;
end; { HugeInt_IsNeg }

function HugeInt_Comp(A, B: HugeInt): integer;
{ A = B: 0; A > B: 1; A < B: -1 }
var
  A_IsNeg, B_IsNeg: boolean;
  I: integer;
begin
  A_IsNeg:= HugeInt_IsNeg(A);
  B_IsNeg:= HugeInt_IsNeg(B);
  if A_IsNeg Xor B_IsNeg then
  begin
    if A_IsNeg then
      Result:= -1
    else
      Result:= 1
  end
  else
  begin
    if A_IsNeg then HugeInt_Min(A);
    if B_IsNeg then HugeInt_Min(B);
    I:= HugeIntSize-1;
    while (I > 0) and (A[I] = B[I]) do Dec(I);
    if A_IsNeg then { both negative }
    begin
      if A[I] > B[I] then
        Result:= -1
      else
        if A[I] < B[I] then
          Result:= 1
        else
          Result:= 0
    end
    else { both positive }
    begin
      if A[I] > B[I] then
        Result:= 1
      else
        if A[I] < B[I] then
          Result:= -1
        else
          Result:= 0;
    end;
  end; { else }
end; { HugeInt_Comp }

procedure HugeInt_DivMod(var A: HugeInt; B: HugeInt; var R: HugeInt);
{ R := A div B; A := A mod B }
var
  MaxShifts, S, Q: integer;
  D, E: HugeInt;
  A_IsNeg, B_IsNeg: boolean;
begin
  A_IsNeg:= HugeInt_IsNeg(A);
  B_IsNeg:= HugeInt_IsNeg(B);
  if A_IsNeg then HugeInt_Min(A);
  if B_IsNeg then HugeInt_Min(B);
  if HugeInt_Comp(A, B) < 0 then
    { A<B; no need to divide }
    FillChar(R, SizeOf(R), 0)
  else
  begin
    FillChar(R, SizeOf(R), 0);
    repeat
      Move(B, D, SizeOf(HugeInt)); 
      { first work out the number of shifts }
      MaxShifts:= HugeInt_HCD(A)- HugeInt_HCD(B);
      S:= 0; 
      while (S <= MaxShifts) and (HugeInt_Comp(A, D) >= 0) do
      begin
        Inc(S);
        HugeInt_SHL(D, 1); 
      end; { while }
      Dec(S); 
      { Make A new copy of B }
      Move(B, D, SizeOf(HugeInt)); 
      { Shift D as needed }
      HugeInt_ShL(D, S);
      { Use E = -D for addition, faster then subtracting D }
      Move(D, E, SizeOf(HugeInt)); 
      HugeInt_Min(E);
      Q:= 0;
      { while A >= D do A := A+-D and keep trek of # in Q}
      while HugeInt_Comp(A, D) >= 0 do
      begin
        HugeInt_Add(A, E, A);
        Inc(Q);
      end; { while }
      { OOps!, one too many subtractions; correct }
      if HugeInt_IsNeg(A) then
      begin
        HugeInt_Add(A, D, A);
        Dec(Q);
      end; { if }
      HugeInt_SHL(R, 1);
      R[0]:= Q;
    until HugeInt_Comp(A, B) < 0;
    if A_IsNeg Xor B_IsNeg then HugeInt_Min(R);
  end; { else }
end; { HugeInt_Div }

procedure HugeInt_DivMod100(var A: HugeInt; var R: integer);
{ This works on positive numbers only
 256-Based division: R:= A mod 100; A:= A div 100; }
var
  Q: HugeInt;
  S: integer;
begin
  R:= 0; FillChar(Q, SizeOf(Q), 0);
  S:= HugeInt_HCD(A);
  repeat
    R:= 256*R + A[S];
    HugeInt_SHL(Q, 1);
    Q[0]:= R div 100;
    R:= R mod 100;
    Dec(S);
  until S < 0;
  Move(Q, A, SizeOf(Q));
end; { HugeInt_DivMod100 }

procedure HugeInt_Div(A, B: HugeInt; var R: HugeInt);
begin
  HugeInt_DivMod(A, B, R);
end; { HugeInt_Div }

procedure HugeInt2String(A: HugeInt; var S: string);
  function Str100(I: integer): string;
  begin
    Result:= Chr(I div 10 + Ord('0'))+ Chr(I mod 10 + Ord('0'));
  end; { Str100 }
var
  R: integer;
  Is_Neg: boolean; 
begin
  S:= '';
  Is_Neg:= HugeInt_IsNeg(A); 
  if Is_Neg then HugeInt_Min(A); 
  repeat
    HugeInt_DivMod100(A, R);
    Insert(Str100(R), S, 1); 
  until HugeInt_Zero(A);
  while (Length(S) > 1) and (S[1] = '0') do Delete(S, 1, 1);
  if Is_Neg then Insert('-', S, 1);
end; { HugeInt2String }

procedure String_DivMod256(var S: string; var R: integer);
{ This works on Positive numbers Only
 10(00)-based division: R:= S mod 256; S:= S div 256 }
var
  Q: string;
begin
  FillChar(Q, SizeOf(Q), 0); 
  R:= 0; 
  while S <> '' do
  begin
    R:= 10*R + Ord(S[1])- Ord('0');
    Delete(S, 1, 1); 
    Q:= Q + Chr(R div 256 + Ord('0'));
    R:= R mod 256;
  end; { while }
  while (Q <> '') and (Q[1] = '0') do Delete(Q, 1, 1); 
  S:= Q;
end; { String_DivMod256 }

procedure String2HugeInt(AString: string; var A: HugeInt);
var
  I, H: integer;
  Is_Neg: boolean;
begin
  if AString = '' then AString:= '0';
  Is_Neg:= AString[1] = '-';
  if Is_Neg then Delete(Astring, 1, 1);
  I:= 0;
  while (AString <> '') and (I <= HugeIntSize-1) do
  begin
    String_DivMod256(AString, H);
    A[I]:= H;
    Inc(I);
  end; { while }
  if Is_Neg then HugeInt_Min(A);
end; { String2HugeInt }

procedure Integer2HugeInt(AInteger: integer; var A: HugeInt);
var
  Is_Neg: boolean;
begin
  Is_Neg:= AInteger < 0;
  if Is_Neg then AInteger:= -AInteger;
  A:= Null;
  Move(AInteger, A, SizeOf(integer));
  if Is_Neg then HugeInt_Min(A);
end; { Integer2HugeInt }

function HugeIntDiv(A, B: HugeInt): HugeInt;
begin
  Result:= Null;
  HugeInt_Div(A, B, Result);
end;

function StrToHugeInt(AString: string): HugeInt;
begin
  Result:= Null;
  String2HugeInt(AString, Result);
end;

function IntToHugeInt(AInteger: Integer): HugeInt;
begin
  Result:= Null;
  Integer2HugeInt(AInteger, Result);
end;

function HugeIntToStr(A: HugeInt): string;
begin
  Result:= '';
  HugeInt2String(A, Result);
end;

end.

[gammatester]

Es ist noch viel schlimmer: 65536 / 1 wird zu 1 berechnet, 50331648 div 3 = 1, etc. Offensichtlich werden alle wertniedrigen 0-Bytes weggeshiftet und nicht nur eins. Aber ich denke, es lohnt nicht den Code weiter zu verfolgen, da offensichtlich wenig durchdacht. ZB kann der OOps-Zweig nie erreicht werden, da A - D nicht negativ sein kann, wenn A >= D ist. Wenn Du eine MP-Bibliothek brauchst, kann ich Dir MPArith empfehlen.

[Bjoerk]

Was er macht, ist eigentlich ein mod auf div aufgepäppelt.

Auch dieses merkwürdige shl. Und am Anfang dache ich, er macht D shl -S, aber das fängt er ab.

Anyway, jedenfalls vielen Dank für dein Feedback und den Link.


Gruß
Thomas

Delphi-Quellcode:

procedure HugeInt_Mod(A, B: HugeInt; var R: HugeInt);
begin
  HugeInt_DivMod(A, B, R);
  Move(A, R, SizeOf(HugeInt));
end;

Edit: So würde es mir fast schon reichen:

Delphi-Quellcode:

function HugeIntModInteger(A: HugeInt; B: integer): integer;
var
  Q: HugeInt;
  I: integer;
begin
  Result:= 0;
  FillChar(Q, SizeOf(HugeInt), 0);
  I:= HugeIntSize-1;
  while (I > 0) and (A[I] = 0) do Dec(I);
  while I >= 0 do
  begin
    Result:= 256*Result + A[I];
    if I > 0 then
    begin
      Move(Q[0], Q[I], HugeIntSize-I);
      FillChar(Q[0], I, 0);
    end;
    Q[0]:= Result div B;
    Result:= Result mod B;
    Dec(I);
  end;
end;

function HugeIntDivInteger(A: HugeInt; B: integer): HugeInt;
var
  Q: HugeInt;
  I, R: integer;
begin
  R:= 0;
  FillChar(Q, SizeOf(HugeInt), 0);
  I:= HugeIntSize-1;
  while (I > 0) and (A[I] = 0) do Dec(I);
  while I >= 0 do
  begin
    R:= 256*R + A[I];
    if I > 0 then
    begin
      Move(Q[0], Q[I], HugeIntSize-I);
      FillChar(Q[0], I, 0);
    end;
    Q[0]:= R div B;
    R:= R mod B;
    Dec(I);
  end;
  Move(Q, A, SizeOf(Q));
  Result:= A;
end;

procedure TForm1.Button3Click(Sender: TObject);
begin
  ShowMessage(HugeIntToStr(HugeIntDivInteger(IntToHugeInt(50331648), 3)));
  ShowMessage(IntToStr(HugeIntModInteger(IntToHugeInt(50331648), 3)));
end;

[gammatester]

Deine neuen Routinen haben noch einen schweren Fehler, denn sie arbeiten nur richtig für positive Integer, zB ergibt 16 div (-3) den Wert 251! Außerdem kann man sie noch drastisch vereinfachen (wenn Du nicht gleich ein kombiniertes div-mod berechnen willst), zB

Delphi-Quellcode:

function HugeIntDivCard(A: HugeInt; B: cardinal): HugeInt;
var
  I: integer;
  R: cardinal;
begin
  R:= 0;
  FillChar(Result, SizeOf(HugeInt), 0);
  I:= HugeIntSize-1;
  while (I > 0) and (A[I] = 0) do Dec(I);
  while I >= 0 do  begin
    R:= 256*R + A[I];
    Result[I]:= R div B;
    R:= R mod B;
    Dec(I);
  end;
end;

function HugeIntModCard(A: HugeInt; B: cardinal): cardinal;
var
  I: integer;
begin
  Result:= 0;
  I:= HugeIntSize-1;
  while (I > 0) and (A[I] = 0) do Dec(I);
  while I >= 0 do begin
    Result:= (256*Result + A[I]) mod B;
    Dec(I);
  end;
end;

Falls Du wirklich Integer brauchst, müssen neben dem Aufruf der ...Card-Routinen noch die Vorzeichen betrachtet werden. Weiterhin darf B nicht zu groß sein (kleiner 2^24), sonst gibt es einen Overflow und man muß in den Schleifen mit Int64 rechnen.

[Bjoerk]

Hey Gammatester, danke für die Vereinfachung (das mit dem Vorzeichen ist klar).

BTW, für HugeInt_Mod konnte ich außer daß das Ergebnis negativ ist, wenn A negativ ist, bisher keinen Fehler feststellen(Der "Oops-Fehler"). Kann man ein A div X iregndwie als mod casten und zurückrechnen, ansonsten bleibt nur Result[I]:= R div B gesondert zu behandeln (N* Subtraktion).

[gammatester]

Zitat von Bjoerk:

BTW, für HugeInt_Mod konnte ich außer daß das Ergebnis negativ ist, wenn A negativ ist, bisher keinen Fehler feststellen(Der "Oops-Fehler"). Kann man ein A div X iregndwie als mod casten und zurückrechnen, ansonsten bleibt nur Result[I]:= R div B gesondert zu behandeln (N* Subtraktion).

Das mit dem casten verstehe ich nicht. Man hat bei richtiger Implementation von div und mod die Formel A = (A div B)*B + A mod B also A div B = (A - A mod B) div B ohne Rest, aber das könnte die Sache noch verschlimmern, weil dann eventuell ja eine weitere 0 weggeshiftet wird. Ansonsten ist hier ein Fix ohne Garantie für die Original-Routine. Die Anzahl der R-Stellen wird vorher berechet und damit eine for-Schleife durchlaufen:

Delphi-Quellcode:

procedure HugeInt_DivMod(var A: HugeInt; B: HugeInt; var R: HugeInt);
{ R := A div B; A := A mod B }
var
  MaxShifts, S, Q, I: integer;
  D, E: HugeInt;
  A_IsNeg, B_IsNeg: boolean;
begin
  A_IsNeg:= HugeInt_IsNeg(A);
  B_IsNeg:= HugeInt_IsNeg(B);
  if A_IsNeg then HugeInt_Min(A);
  if B_IsNeg then HugeInt_Min(B);
  if HugeInt_Comp(A, B) < 0 then
    { A<B; no need to divide }
    FillChar(R, SizeOf(R), 0)
  else
  begin
    FillChar(R, SizeOf(R), 0);
    Move(B, D, SizeOf(HugeInt));
    { first work out the number of shifts }
    MaxShifts:= HugeInt_HCD(A)- HugeInt_HCD(B);
    S:= 0;
    while (S <= MaxShifts) and (HugeInt_Comp(A, D) >= 0) do
    begin
      Inc(S);
      HugeInt_SHL(D, 1);
    end; { while }
    Dec(S);
    for I:=S downto 0 do begin
      { Make A new copy of B }
      Move(B, D, SizeOf(HugeInt));
      { Shift D as needed }
      HugeInt_ShL(D, I);
      { Use E = -D for addition, faster then subtracting D }
      Move(D, E, SizeOf(HugeInt));
      HugeInt_Min(E);
      Q:= 0;
      { while A >= D do A := A+-D and keep trek of # in Q}
      while HugeInt_Comp(A, D) >= 0 do
      begin
        HugeInt_Add(A, E, A);
        Inc(Q);
      end; { while }
      { OOps!, one too many subtractions; correct }
      if HugeInt_IsNeg(A) then
      begin
        HugeInt_Add(A, D, A);
        Dec(Q);
      end; { if }
      R[I]:= Q;
    end;
    if A_IsNeg Xor B_IsNeg then HugeInt_Min(R);
  end; { else }
end; { HugeInt_Div }

Für die bisherigen Fälle und zB für (456*123456+78) div 456 scheint's zu laufen, aber ...! Die minimale Änderung hat den undurchsichtigen Code nicht klarer gemacht.

[Bjoerk]

Ja, versteh' ich auch selbst nicht mehr, vergiß das mit dem casten, war Nonsens von mir

Ich teste gerade das.

Delphi-Quellcode:

function HugeIntDivNew(A, B: HugeInt): HugeInt;
var
  I: integer;
  R: HugeInt;
  ANeg, BNeg: boolean;
begin
  ANeg:= HugeIntIsNeg(A);
  if ANeg then A:= HugeIntMinus(A);
  BNeg:= HugeIntIsNeg(B);
  if BNeg then B:= HugeIntMinus(B);
  R:= Null;
  Result:= Null;
  I:= HugeIntSize-1;
  while (I > 0) and (A[I] = 0) do
    Dec(I);
  while I >= 0 do
  begin
    R:= HugeIntAdd(HugeIntMult(IntToHugeInt(256), R), IntToHugeInt(A[I]));
    Result[I]:= StrToInt(HugeIntToStr(HugeIntDiv(R, B)));
    R:= HugeIntMod(R, B);
    Dec(I);
  end;
  if ANeg xor BNeg then Result:= HugeIntMinus(Result)
end;

Deinen Code werde ich mir heute abend anschauen und testen. Ich melde mich noch mal. Danke für dein Interesse!

[Bjoerk]

Jo, meine funktioniert soweit. Hab ein paar Millionen Tests durchgeführt. Die DivMod-Routine geht sicher nur für S = 0. Und, wie du schon vermutet hast, deine liefert z.B. für 6624 div 9 = 33554656 statt 736. Anyway..

Danke für deine Unterstützung, ohne deine Vereinfachung von heute morgen hätte ich’s nicht geschafft!!

Zu guter Letzt, hast du eine Idee für eine elegante HugeIntToInteger ?

Sorry ziehe die Frage zurück, ist ja wohl zu ...

Delphi-Quellcode:

function HugeIntToInteger(A: HugeInt): integer;
begin
  Move(A, Result, SizeOf(integer));
end;