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.