Fórum Essa é difícil (números super grandes) #222246

TypeRangeFormat
Shortint–128..127signed 8-bit
Smallint–32768..32767signed 16-bit
Longint–2147483648..2147483647signed 32-bit
Int64–2^63..2^63–1signed 64-bit
Byte0..255unsigned 8-bit
Word0..65535unsigned 16-bit
Longword0..4294967295unsigned 32-bit

type
  Hugeint: packed array [0..3] of LongWord;

// Big Numbers by Beppe 27/03/2004

const
  DigitPrecision = 300; // deve ser ao menos 11

type
  BigNumber = array[1..DigitPrecision] of Byte;

var
  Zero, One: BigNumber;

function BigNumberToStr(const N: BigNumber): String;
var
  I: Integer;
begin
  I := Low(BigNumber);
  while (I <= High(BigNumber)) and (N[I] = 0) do Inc(I);
  SetString(Result, PChar(@N[I]), High(N) - I + 1);
  for I := 1 to Length(Result) do
    Inc(Result[I], Ord(´0´));
end;

function BigNumberToInt(const N: BigNumber): Integer;
begin
  Result := StrToInt(BigNumberToStr(N));
end;

function NewBigNumber(Value: Integer): BigNumber;
var
  I: Integer;
begin
  FillChar(Result, Length(Result), 0);
  I := High(BigNumber);
  repeat
    Result[I] := Value mod 10;
    Dec(I);
    Value := Value div 10;
  until Value = 0;
end;

function Equals(const Left, Right: BigNumber): Boolean;
begin
  Result := CompareMem(@Left, @Right, SizeOf(BigNumber));
end;

function Add(const Left, Right: BigNumber): BigNumber;
var
  I, Carry, Sum: Integer;
begin
  Result := NewBigNumber(0);
  Carry := 0;
  for I := High(BigNumber) downto Low(BigNumber) do
  begin
    Sum := Left[I] + Right[I] + Carry;
    Carry := Sum div 10;
    Result[I] := Sum mod 10;
  end;
end;

function DivideByTwo(const N: BigNumber): BigNumber;
var
  I, Carry, Quo: Integer;
begin
  Result := NewBigNumber(0);
  Carry := 0;
  for I := Low(BigNumber) to High(BigNumber) do
  begin
    Quo := Carry * 10 + N[I];
    Carry := Quo mod 2;
    Result[I] := Quo div 2;
  end;
end;

function IsOdd(const N: BigNumber): Boolean;
begin
  Result := Odd(N[DigitPrecision]);
end;

function Multiply(const Left, Right: BigNumber): BigNumber;
begin
  if Equals(Left, Zero) or Equals(Right, Zero) then
    Result := One
  else if Equals(Left, One) then
    Result := Right
  else if Equals(Right, One) then
    Result := Left
  else
  begin
    Result := Multiply(Left, DivideByTwo(Right));
    Result := Add(Result, Result);
    if IsOdd(Right) then
      Result := Add(Result, Left);
  end;
end;

function GreaterThan(const Left, Right: BigNumber): Boolean;
var
  I: Integer;
begin
  Result := False;
  for I := High(BigNumber) downto Low(BigNumber) do
  begin
    if Left[I] < Right[I] then
      Exit
    else if Left[I] > Right[I] then
    begin
      Result := True;
      Exit;
    end;
  end;
end;

function Power(const Left: BigNumber; Right: Cardinal): BigNumber;
begin
  case Right of
    0: Result := One;
    1: Result := Left;
  else
    Result := Power(Left, Right div 2);
    Result := Multiply(Result, Result);
    if Odd(Right) then
      Result := Multiply(Result, Left);
  end;
end;

function Mul(A, B: Cardinal): Cardinal;
begin
  case B of
    0: Result := 1;
    1: Result := A;
  else
    Result := Mul(A, B div 2);
    Result := Result + Result;
    if Odd(B) then
      Result := Result + A;
  end;
end;

function Pow(A, B: Cardinal): Cardinal;
begin
  case B of
    0: Result := 1;
    1: Result := A;
  else
    Result := Pow(A, B div 2);
    Result := Result * Result;
    if Odd(B) then
      Result := Result * A;
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  A, B: BigNumber;
begin
  A := NewBigNumber(1220232);
  B := NewBigNumber(5012321);
  // cheque no calc.exe: 6116194478472
  Edit1.Text := BigNumberToStr(Multiply(A, B));
  // cheque no calc.exe: 2705278928837504201024262930432
  Edit2.Text := BigNumberToStr(Power(A, 5));
end;

initialization
  Zero := NewBigNumber(0);
  One := NewBigNumber(1);