Unit HugeObj;

Interface

Const
  Base = 10000; { system base }
  MaxLen = 300; { max digits length }
  DigitSep : String = ''; { digits delimiter for output, '|' for example }

  max = (Pred(Base) + maxLen + Abs(Pred(Base) - maxLen)) Div 2;

Type
  Digit = 0 .. Pred(Base);
  Inter = 0 .. Pred(Base)*Succ(Base);
  Index = 0 .. maxLen;

Type
  TArrItem = 0 .. max;

  VLIError = (vliOverflow, vliNegative);

  TLargeInt =
    Object
    Public
      Constructor Init(x: LongInt);

      Function Cmp(Const B: TLargeInt): Integer;
      Function CmpDigit(x: Digit): Integer;

      Procedure AddDigit(x: Digit);
      Procedure SubDigit(x: Digit);
      Procedure MulDigit(x: Digit);
      Function DivDigit(x: Digit): Digit;

      Procedure Add(Const B: TLargeInt);
      Procedure Sub(Const B: TLargeInt);
      Procedure Mul(Const B: TLargeInt);

      Procedure Print(Var f: Text);
      Procedure ErrorMsg(Code: VLIError;
                         Const s: String);

    Private
      _me: Array [0 .. maxLen] Of 0 .. max;

      Function Get(i: Index): TArrItem;
      Function GetLen: TArrItem;
      Function GetLast: TArrItem;
      Procedure Put(i: Index; x: TArrItem);
      Procedure SetLen(x: TArrItem);

      Procedure DecLen;
      Procedure IncLen;
    End;


Procedure Fact(Var A: TLargeInt; n: LongInt);


Implementation


Function TLargeInt.Get(i: Index): TArrItem;
  Begin
    Get := _me[i]
  End;
Function TLargeInt.GetLen: TArrItem;
  Begin GetLen := Get(0) End;
Function TLargeInt.GetLast: TArrItem;
  Begin GetLast := Get(GetLen) End;

Procedure TLargeInt.Put(i: Index; x: TArrItem);
  Begin
    _me[i] := x
  End;
Procedure TLargeInt.SetLen(x: TArrItem);
  Begin Put(0, x) End;

Procedure TLargeInt.DecLen;
  Begin SetLen(Pred(GetLen)) End;
Procedure TLargeInt.IncLen;
  Begin SetLen(Succ(GetLen)) End;


Const
  ErrDesc: Array[VLIError] Of String =
    ('Overflow ', 'Negative result ');

Procedure TLargeInt.ErrorMsg(Code: VLIError;
          Const s: String);
  Begin
    WriteLn('Error:'#13#10 + ErrDesc[Code] + 'when making ', s);
    Halt(1)

  End;

{ LargeInt initialization by (x) number --  A := x }
{ ASSERT: using LongInt instead of Digit, }
{ guessing that MaxLongInt >= Base-1 }
Constructor TLargeInt.Init(x: LongInt);
  Var i: Index;
  Begin
    FillChar(_me, SizeOf(_me), 0); i := 0;
    Repeat
      If i = maxLen Then ErrorMsg(vliOverflow, 'Init');
      Inc(i); Put(i, x mod Base);
      x := x div Base
    Until x = 0;
    SetLen(i)
  End;

{ CmpDigit := sgn(A-x), }
{   -1, if A < x }
{    0, if A = x }
{   +1, if A > x }
Function TLargeInt.CmpDigit(x: Digit): Integer;
  Var i: Index;
  Begin
    If GetLen > 1 Then CmpDigit := (+1)
    Else CmpDigit := Ord(Get(1) > x) - Ord(Get(1) < x)
  End;

{ A := A + x }
Procedure TLargeInt.AddDigit(x: Digit);
  Var i: Index; T: Inter;
  Begin
    i := 0; T := x;
    While T > 0 Do
      Begin
        If i = maxLen Then ErrorMsg(vliOverflow, 'AddDigit');
        Inc(i); Inc(T, Get(i));
        Put(i, T mod Base);
        T := T div Base
      End;
    If i > GetLen Then SetLen(i)
  End;

{ A := A - x }
Procedure TLargeInt.SubDigit(x: Digit);
  Var i: Index; T: Inter;
  Begin
    i := 0; T := x;
    While T > 0 Do
      Begin
        If i = GetLen Then ErrorMsg(vliNegative, 'SubDigit');
        Inc(i); T := Get(i) + (Base - T);
        Put(i, T mod Base);
        T := 1 - T div Base
      End;
    If (GetLen > 1) and (GetLast = 0) Then DecLen
  End;

{ A := A * x }
Procedure TLargeInt.MulDigit(x: Digit);
  Var i: Index; T: Inter;
  Begin
    T := 0;
    For i := 1 To GetLen Do
      Begin
        T := Inter(Get(i)) * x + T;
        Put(i, T mod Base);
        T := T div Base
      End;

    If T > 0 Then
      Begin
        If GetLen = maxLen Then ErrorMsg(vliOverflow, 'MulDigit');
        IncLen; Put(GetLen, T)
      End
  End;

{ A := A Div x; DivDigit := A Mod x  }
Function TLargeInt.DivDigit(x: Digit): Digit;
  Var i: Index; T: Inter;
  Begin
    If x = 0 Then ErrorMsg(vliOverflow, 'DivDigit');
    T := 0;
    For i := GetLen DownTo 1 Do
      Begin
        T := T * Base + Get(i);
        Put(i, T div x); T := T mod x
      End;
    If (GetLen > 1) and (GetLast = 0) Then DecLen;
    DivDigit := T
  End;

{ Cmp := sgn(A-B), }
{   -1, if A < B }
{    0, if A = B }
{   +1, if A > B }
Function TLargeInt.Cmp(Const B: TLargeInt): Integer;
  Var i: Index;
  Begin
    If GetLen > B.GetLen Then Cmp := (+1)
    Else
      If GetLen < B.GetLen Then Cmp := (-1)
      Else
        Begin
          i := GetLen;
          While (i>0) and (Get(i) = B.Get(i)) Do Dec(i);
          Cmp := Ord(Get(i) > B.Get(i)) - Ord(Get(i) < B.Get(i))
        End
  End;

{ A := A + B }
Procedure TLargeInt.Add(Const B: TLargeInt);
  Var i: Index; T: Inter;
  Begin
    T := 0;
    If GetLen < B.GetLen Then SetLen(B.GetLen);
    For i := 1 To GetLen Do
      Begin
        { A[i] and B[i] casted to Inter before addition }
        Inc(T, Get(i)); Inc(T, B.Get(i));
        Put(i, T mod Base); T := T Div Base
      End;
    If T > 0 Then
      Begin
        If GetLen = maxLen Then ErrorMsg(vliOverflow, 'Add');
        IncLen; Put(GetLen, T)
      End
  End;

{ A := A - B }
Procedure TLargeInt.Sub(Const B: TLargeInt);
  Var i: Index; T: Inter;
  Begin
    If B.GetLen > GetLen Then ErrorMsg(vliNegative, 'Sub');
    T := 0;
    For i := 1 To GetLen Do
      Begin
        T := Get(i) + (Base - B.Get(i) - T);
        Put(i, T mod Base); T := 1 - T div Base
      End;
    If t <> 0 Then ErrorMsg(vliNegative, 'Sub');
    While (GetLen > 1) And (GetLast = 0) Do DecLen
  End;

{ A := A * B }
Procedure TLargeInt.Mul(Const B: TLargeInt);
  Var
    C: TLargeInt;
    i, j: Index; T: Inter;
  Begin
    If GetLen - 1 > maxLen - B.GetLen Then  {Overflow('Mul');}
    C.Init(0); C.SetLen(GetLen + B.GetLen - 1);
    For i := 1 To GetLen Do
      Begin
        T := 0;
        For j := 1 To B.GetLen Do
          Begin
            T := C.Get(i + j - 1) + Inter(Get(i)) * B.Get(j) + T;
            C.Put(i + j - 1, T mod Base); T := T div Base
          End;

        If T > 0 Then
          Begin
            If i + j - 1 = maxLen Then ErrorMsg(vliOverflow, 'Mul');
            C.Put(i + j, T);
            If i + j > C.GetLen Then C.SetLen(i + j)
          End
      End;

    { In case A=0 and/or B=0 }
    While (C.GetLen > 1) And (C.Get(C.GetLen) = 0) Do C.DecLen;
    Self := C
  End;

{ Printing LargeInt  --  Write(A) }
Procedure TLargeInt.Print(Var f: Text);
  Var
    i: Index; k: Digit; s: String;
  Begin
    Str(Base - 1, s); k := Length(s);
    Write(f, GetLast);
    For i := GetLen - 1 DownTo 1 Do
      Begin
        Str(Get(i), s);
        While Length(s) < k Do s := '0' + s;
        Write(f, DigitSep, s)
      End
  End;


{ A := n! }
Procedure Fact(Var A: TLargeInt; n: LongInt);
  Var T: TLargeInt; i: LongInt;
  Begin
    T.Init(1);
    For i := 2 To n Do
      T.MulDigit(i);
    A._me := T._me
  End;

end.