unit BigInt;

interface

const MaxBytes = 100;
const MaxBits = 8 * MaxBytes;

type TBigInt = array [0..MaxBytes-1] of Byte;

procedure Init(var R: TBigInt; X: Byte); { R := X }
procedure Zero(var R: TBigInt); { R := 0 }

function IsZero(const A: TBigInt): Boolean; { A = 0 }

const Overflow: Boolean = False; { True = nastalo preteceni }

procedure Add(var R: TBigInt; const A,B: TBigInt);           { R := A + B }
function Sub(var R: TBigInt; const A,B: TBigInt): Boolean;   { R := A - B }
procedure Mul(var R: TBigInt; A: TBigInt; const B: TBigInt); { R := A * B }
procedure DivMod(var A: TBigInt; B: TBigInt; var R: TBigInt); { R := A div B; A := A mod B }

var Base: TBigInt; { zaklad pro prevod z a na retezce }

procedure StrToBig(const S: String; var A: TBigInt);
function BigToStr(A: TBigInt): String;

implementation

procedure Init(var R: TBigInt; X: Byte);
var I: Integer;
 begin
  R[0] := X;
  for I := 1 to MaxBytes-1 do R[I] := 0;
 end;

procedure Zero(var R: TBigInt);
begin Init(R,0) end;

function IsZero(const A: TBigInt): Boolean;
var I: Integer;
 begin
  IsZero := True;
  for I := 0 to MaxBytes-1 do if A[I] <> 0 then IsZero := False;
 end;

procedure SetBit(var A: TBigInt; I: Integer);
 begin A[I shr 3] := A[I shr 3] or (1 shl (I and 7)) end;

function IsBit(const A: TBigInt; I: Integer): Boolean;
 begin IsBit := A[I shr 3] and (1 shl (I and 7)) <> 0 end;

function Bits(const A: TBigInt): Integer;
var I: Integer;
 begin
  I := MaxBits;
  repeat
   I := I - 1;
   if IsBit(A,I) then Break;
  until I = 0;
  Bits := I + 1;
 end;

procedure Add(var R: TBigInt; const A,B: TBigInt);
var I, X, Carry: Integer;
 begin
  Carry := 0;
  for I := 0 to MaxBytes-1 do
   begin
    X := Integer(A[I]) + Integer(B[I]) + Carry;
    if X < 256 then begin R[I] := X; Carry := 0 end
    else begin R[I] := X - 256; Carry := 1 end;
   end;
  if Carry <> 0 then Overflow := True;
 end;

function Sub(var R: TBigInt; const A,B: TBigInt): Boolean;
var I, X, Carry: Integer;
 begin
  Carry := 0;
  for I := 0 to MaxBytes-1 do
   begin
    X := Integer(A[I]) - Integer(B[I]) - Carry;
    if X >= 0 then begin R[I] := X; Carry := 0 end
    else begin R[I] := X + 256; Carry := 1 end;
   end;
  Sub := Carry <> 0;
 end;

function ShiftRight(var A: TBigInt): Boolean; { A := A >> 1 }
var I, X, Carry: Integer;
 begin
  Carry := 0;
  for I := MaxBytes-1 downto 0 do
   begin
    X := A[I] + Carry;
    if odd(X) then Carry := 256 else Carry := 0;
    A[I] := X shr 1;
   end;
  ShiftRight := Carry <> 0;
 end;

procedure Mul(var R: TBigInt; A: TBigInt; const B: TBigInt);
var I: Integer;
 begin
  Zero(R);
  for I := 0 to Bits(B)-1 do
   begin
    if IsBit(B,I) then Add(R,R,A);
    Add(A,A,A);
   end;
 end;

procedure DivMod(var A: TBigInt; B: TBigInt; var R: TBigInt);
var I,N: Integer;
    E: TBigInt;
 begin
  N := Bits(B);
  if N = 0 then begin Overflow := True; Exit end;
  N := Bits(A)-N;
  Zero(R);
  for I := 1 to N do Add(B,B,B);
  for I := N downto 0 do
   begin
    if not Sub(E,A,B) then
      begin A := E; SetBit(R,I) end;
    ShiftRight(B);
   end;
 end;

procedure StrToBig(const S: String; var A: TBigInt);
var I: Integer;
    B: TBigInt;
 begin
  Zero(A);
  for I := 1 to Length(S) do
   begin
    Mul(A,A,Base);
    Init(B,ord(S[I])-ord('0'));
    Add(A,A,B);
   end;
 end;

function BigToStr(A: TBigInt): String;
var Result: String;
    B: TBigInt;
 begin
  if IsZero(A) then begin BigToStr := '0'; Exit end;
  Result := '';
  repeat
   DivMod(A,Base,B);
   Result := chr(A[0]+ord('0')) + Result;
   A := B;
  until IsZero(A);
  BigToStr := Result;
 end;

begin
 Init(Base, 10);
end.