I wrote this class for doing arithmetic with extremely large numbers. It can of course be optimised but meh.. It's fast enough for all intents and purposes..
Simba Code:
type
BigInteger = record
sign: ShortInt;
digits: string;
end;
type
TString = String; //work-around for a lape bug..
Function TString.Reverse(): String;
var
C: Char;
L, H: PChar;
begin
if (self.size() < 1) then
exit;
L := @self[1];
H := @self[self.size()];
while (L < H) do
begin
C := H^;
H^ := L^;
L^ := C;
H -= 1;
L += 1;
end;
Result := self;
end;
Function TString.Erase(Index, Amount: Integer = 1): String;
Begin
Delete(self, Index, Amount);
Result := self;
End;
Function TString.Size(): Integer;
Begin
Result := Length(Self);
End;
Function BigInteger.Init(value: Int64): BigInteger;
Begin
Result := self;
if (value = 0) then
sign := 0
else if (value > 0) then
sign := 1
else
sign := -1;
digits := ToStr(value);
if (self.isNegative()) then
digits.Erase(0);
digits.Reverse();
End;
Function BigInteger.Init(value: UInt64): BigInteger; overload;
Begin
Result := self;
if (value = 0) then
sign := 0
else if (value > 0) then
sign := 1;
digits := ToStr(value).Reverse();
End;
Function BigInteger.Init(value: Integer): BigInteger; overload
Begin
Result := self.Init(Int64(value));
End;
Function BigInteger.Init(value: UInt32): BigInteger; overload;
Begin
Result := self.Init(UInt64(value));
End;
Function BigInteger.Init(value: String): BigInteger; overload;
var
I: Integer;
Begin
Result := Self;
self.sign := 0;
if (value.size() > 0) then
begin
self.sign := 1;
self.digits := value;
if (self.digits[1] = '-') then
self.sign := -1
if ((self.digits[1] = '+') or (self.digits[1] = '-')) then
self.digits.Erase(0);
end;
self.digits.Reverse();
self.Normalise();
For I := 1 To self.digits.size() Do
begin
if ((Ord(digits[I]) < $30) or (Ord(digits[I]) > $39)) then
begin
self.sign := 0;
self.digits := '0';
end;
end;
End;
Function BigInteger.Init(other: BigInteger): BigInteger; overload;
Begin
self.sign := other.sign;
self.digits := other.digits;
End;
Function BigInteger.Clone(): BigInteger;
Begin
Result := self.Init(self);
End;
Function BigInteger.IsNeutral(): Boolean;
Begin
Result := Sign = 0;
End;
Function BigInteger.IsPositive(): Boolean;
Begin
Result := Sign > 0;
End;
Function BigInteger.IsNegative(): Boolean;
Begin
Result := Sign < 0;
End;
Function BigInteger.Normalise(): BigInteger;
var
I: Integer;
Begin
Result := Self;
For I := self.digits.size() DownTo 1 Do
begin
if (self.digits[I] <> '0') then
break;
self.digits.Erase(I);
end;
if (self.digits.size() < 1) then
begin
self.sign := 0;
self.digits := '0';
end;
End;
Function BigInteger.toDigit(Index: Integer): Integer;
Begin
if ((Index > 0) and (Index <= self.digits.size())) then
Result := Ord(self.digits[Index]) - $30;
End;
Function BigInteger.toString(): String;
Begin
Result := toStr(self);
End;
Function toString(var other: BigInteger): String; override;
Begin
if (other.digits.size() < 1) Then
begin
Result := inherited(other);
end else
begin
Result := other.Digits;
Result.Reverse();
if (other.isNegative()) then
Result := '-' + Result;
end;
End;
Function BigInteger.isLessThan(var other: BigInteger): Boolean;
var
I: Integer;
Begin
Result := false;
if (self.isNeutral() or other.isNeutral()) then
begin
if (self.isNeutral()) then
exit(other.isPositive())
else
exit(self.isNegative());
end;
if (sign <> other.sign) then
exit(self.isNegative());
if (digits.size() <> other.digits.size()) then
exit(((self.digits.size() < other.digits.size()) and self.isPositive()) or ((self.digits.size() > other.digits.size()) and self.isNegative()));
For I := self.digits.size() DownTo 1 Do
begin
if (self.toDigit(I) < other.toDigit(I)) then
exit(self.isPositive());
if (self.toDigit(I) > other.toDigit(I)) then
exit(self.isNegative());
end;
End;
Function BigInteger.isGreaterThan(var other: BigInteger): Boolean;
var
I: Integer;
Begin
Result := false;
if (self.isNeutral() or other.isNeutral()) then
begin
if (self.isNeutral()) then
exit(other.isNegative())
else
exit(self.isPositive());
end;
if ((sign <> other.sign) and not (self.isNeutral() or other.isNeutral())) then
exit(self.isPositive());
if (digits.size() <> other.digits.size()) then
exit(((self.digits.size() > other.digits.size()) and self.isPositive()) or ((self.digits.size() < other.digits.size()) and self.isNegative()));
For I := self.digits.size() DownTo 1 Do
begin
if (self.toDigit(I) > other.toDigit(I)) then
exit(self.isPositive());
if (self.toDigit(I) < other.toDigit(I)) then
exit(self.isNegative());
end;
End;
Function BigInteger.isLessThanEQ(var other: BigInteger): Boolean;
Begin
Result := self.isLessThan(other) or self.isEqualTo(other);
End;
Function BigInteger.isGreaterThanEQ(var other: BigInteger): Boolean;
Begin
Result := self.isGreaterThan(other) or self.isEqualTo(other);
End;
Function BigInteger.isEqualTo(var other: BigInteger): Boolean;
var
I: Integer;
Begin
Result := true;
if ((self.sign <> other.sign) or (self.digits.size() <> other.digits.size())) then
exit(false);
For I := self.digits.size() DownTo 1 Do
if (self.toDigit(I) <> other.toDigit(I)) then
exit(false);
End;
Function BigInteger.isNotEqualTo(var other: BigInteger): Boolean;
Begin
Result := Not self.isEqualTo(other);
End;
Function BigInteger.Add(other: Int64): BigInteger;
Begin
Result := self.Add(Result.Init(other));
End;
Function BigInteger.Add(var other: BigInteger): BigInteger; overload;
var
Carry, Total: Integer;
I, Len: Integer;
Begin
if (other.isNeutral()) then
exit(self);
if (@self = @other) then
exit(self.Multiply(2));
if (self.sign <> other.sign) then
exit(self.Subtract(other.Multiply(-1)));
Result.sign := self.sign;
Carry := 0; Total := 0; Len := Max(self.digits.size(), other.digits.size());
For I := 1 To Len Do
begin
Total := self.toDigit(I) + other.toDigit(I) + Carry;
Carry := Total div 10;
Total := Total mod 10;
if (I >= Result.digits.size()) then
SetLength(Result.digits, Result.digits.size() + 1);
Result.digits[I] := Chr(Total + $30);
end;
if (Carry <> 0) then
begin
SetLength(Result.digits, Result.digits.size() + 1);
Result.digits[Result.digits.size()] := Chr(Carry + $30);
end;
End;
Function BigInteger.Subtract(other: Int64): BigInteger;
Begin
Result := self.Subtract(Result.Init(other));
End;
Function BigInteger.Subtract(var other: BigInteger): BigInteger; overload;
var
Borrow, Total: Integer;
I, Len: Integer;
Begin
if (other.isNeutral()) then
exit(self);
if (@self = @other) then
exit(Result.Init(0));
if (self.sign <> other.sign) then
exit(self.Add(other.Multiply(-1)));
if ((self.isPositive() and self.isLessThan(other)) or (self.isNegative() and self.isGreaterThan(other))) then
begin
Result := other.Subtract(self);
Result.sign := 1;
if (self.isPositive()) then
Result.sign := -1;
exit(Result);
end;
Result.sign := self.sign;
Borrow := 0; Total := 0; Len := Max(self.digits.size(), other.digits.size());
SetLength(Result.digits, Len);
For I := 1 To Len Do
Begin
Total := self.toDigit(I) - other.toDigit(I) - Borrow;
Borrow := 0;
if (Total < 0) then
begin
Borrow := 1;
Total += 10;
end;
Result.digits[I] := Chr(Total + $30);
End;
Result.Normalise();
End;
Function BigInteger.Multiply(other: Int64): BigInteger;
Begin
Result := self.Multiply(Result.Init(other));
End;
Function BigInteger.Multiply(var other: BigInteger): BigInteger; overload;
var
I, J: Integer;
Carry, Total: Integer;
Begin
Result.Init(0);
if (self.isNeutral() or other.isNeutral()) then
exit(Result);
Result.sign := 1;
if (self.sign <> other.sign) then
Result.sign := -1;
For J := 0 To other.digits.size() - 1 Do
begin
Carry := 0; Total := 0;
For I := 0 To digits.size() - 1 Do
begin
Total := Result.toDigit(I + J + 1) + (self.toDigit(I + 1) * other.toDigit(J + 1)) + Carry;
Carry := Total div 10;
Total := Total mod 10;
if ((I + J + 1) > Result.digits.size()) then
SetLength(Result.digits, Result.digits.size() + 1);
Result.digits[I + J + 1] := Chr(Total + $30);
end;
if (Carry <> 0) then
begin
SetLength(Result.digits, Result.digits.size() + 1);
Result.digits[Result.digits.size()] := Chr(Carry + $30);
end;
end;
End;
Function BigInteger.Divide(other: Int64): BigInteger;
Begin
Result := self.Divide(Result.Init(other));
End;
Function BigInteger.Divide(var Divisor: BigInteger; Remainder: ^BigInteger = nil): BigInteger; overload;
var
Rem_Sign: ShortInt;
Res_Neg: Boolean;
Dvr: BigInteger;
Quotient: BigInteger;
I, Len, Diff, Offset: Integer;
Borrow, Total: Integer;
Begin
if (Divisor.isNeutral()) then
RaiseException(erDivideByZero, 'Division By Zero Exception');
Rem_Sign := self.sign;
Res_Neg := self.sign <> Divisor.sign;
if (Not self.isNeutral()) then
Result.sign := 1;
if (self.isLessThan(Divisor)) then
begin
if (Remainder <> nil) then
Remainder^ := self;
exit(Result.Init(0));
end;
if (@self = @Divisor) then
begin
if (Remainder <> nil) then
Remainder^ := self;
exit(Result.Init(1));
end;
Result.Init(self);
Dvr.Init(Divisor);
Quotient.Init(0);
Dvr.sign := 1;
Len := Max(Result.digits.size(), Dvr.digits.size());
Diff := Max(Result.digits.size(), Dvr.digits.size()) - Min(Result.digits.size(), Dvr.digits.size());
Offset := Len - Diff - 1;
Result.digits := PadL(Result.digits, Len, '0');
Dvr.digits := PadL(Dvr.digits, Len, '0');
Quotient.digits := PadL(Quotient.digits, Len, '0');
MemMove(Dvr.digits[Diff + 1], Dvr.digits[1], Len - Diff);
For I := 1 To Diff Do Dvr.digits[I] := '0';
while (Offset < Len) do
begin
while (Result.isGreaterThanEQ(Dvr)) do
begin
For I := 1 To Len Do
Begin
Total := Result.toDigit(I) - Dvr.toDigit(I) - Borrow;
Borrow := 0;
if (Total < 0) then
begin
Borrow := 1;
Total += 10;
end;
Result.digits[I] := Chr(Total + $30);
End;
Inc(Quotient.digits[Len - Offset]);
end;
if ((Remainder <> nil) and (Offset = (Len - 1))) then
begin
Remainder^ := Result;
Remainder^.sign := Rem_Sign;
Remainder^.Normalise();
if (Remainder = @self) then
exit(Result);
end;
MemMove(Dvr.digits[2], Dvr.digits[1], Len - 1);
Dvr.digits[Len] := '0';
Inc(Offset);
end;
Quotient.sign := 1;
if (Res_Neg) then
Quotient.sign := -1;
Quotient.Normalise();
Result := Quotient;
End;
Function BigInteger.Modulo(var other: BigInteger): BigInteger;
Begin
self.Divide(other, @Result);
End;
Test case:
Simba Code:
var
A, B: BigInteger;
begin
ClearDebug();
A.Init('123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789');
B.Init('5678901234567890123456789');
writeln(A.Multiply(B));
writeln(A.Divide(B));
writeln(A.Modulo(B));
writeln(A.Add(B));
writeln(A.Subtract(B));
writeln(A.Add(B.Multiply(A).Divide(B))); //Chaining.
end.
Result:
Progress Report:
701098911537997408300588491020579849102057984910205798491020579849102057984910205798491020579849101987875019051998750190521
21739555578261356323493334462240019404063213093086385865664001138064832939
229383133009231653083918
123456789012345678901234567890123456789012345678901234567890123456789012351357802469135780246913578
123456789012345678901234567890123456789012345678901234567890123456789012340000000000000000000000000
246913578024691357802469135780246913578024691357802469135780246913578024691357802469135780246913578
If Lape had operator overloading, it's be nice because then you could get rid of all the annoying functions and just do BigInteger *+/-%, etc.. instead of Multiply, Add, Subtract, Modulo, etc..
Anyway, Enjoy..