HugeInt_Div

[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;