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.