Amiga ISO Collection/AmigaUtilCD2.iso/Programming/Misc/OB3.2D2.DMS/in.adf/Module/BigIntegers.mod

Text File | 1994-08-05 | 7.2 KB | 308 lines

(*-------------------------------------------------------------------------*)
(*                                                                         *)
(*  Amiga Oberon Interface Module: BigIntegers        Date: 02-Nov-92      *)
(*                                                                         *)
(*   © 1992 by Fridtjof Siebert                                            *)
(*                                                                         *)
(*-------------------------------------------------------------------------*)

MODULE BigIntegers;

IMPORT BT * := BasicTypes;

TYPE
  BigInteger * = POINTER TO BigIntegerDesc;
  BigIntegerDesc * = RECORD (BT.RINGDesc)
    negative - : BOOLEAN;
    digits   - : POINTER TO ARRAY OF INTEGER;
  END;

CONST

  MaxDigit * = 1000;
  (*
   * for all i, 0 <= i < LEN(digits^):
   *   0 <= digits[i] < MaxDigit
   *
   * NOTE: 2 * MaxDigit < MAX(INTEGER)
   *
   *)


PROCEDURE InternalCreate (numDigits: LONGINT): BigInteger;
(*
 * Create new BigInteger with room for numDigits digits.
 *
 *)

VAR
  bi: BigInteger;

BEGIN
  NEW(bi);
  NEW(bi.digits,numDigits);
  RETURN bi;
END InternalCreate;


PROCEDURE Create * (init: LONGINT): BigInteger;
(*
 * Create new BigInteger. Set its value to init.
 *
 * require
 *   -MAX(LONGINT) <= init <= MAX(LONGINT)
 *)

VAR
  bi: BigInteger;
  neg: BOOLEAN;

BEGIN
  IF init<0 THEN
    init := -init;
    neg := TRUE;
  ELSE
    neg := FALSE;
  END;
  IF init<MaxDigit THEN
    bi := InternalCreate(1);
    bi.digits[0] := SHORT(init);
  ELSIF init<MaxDigit*MaxDigit THEN
    bi := InternalCreate(2);
    bi.digits[0] := SHORT(init MOD MaxDigit);
    bi.digits[1] := SHORT(init DIV MaxDigit);
  ELSE
    bi := InternalCreate(3);
    bi.digits[0] := SHORT(init MOD MaxDigit);
    bi.digits[1] := SHORT(init DIV MaxDigit MOD MaxDigit);
    bi.digits[2] := SHORT(init DIV (MaxDigit*MaxDigit));
  END;
  bi.negative := neg;
  RETURN bi;
END Create;


PROCEDURE (a: BigInteger) Compare * (b: BT.COMPAREABLE): LONGINT;
VAR
  i: LONGINT;
BEGIN

  WITH b: BigInteger DO

    i := LEN(b.digits^);
    WHILE i>LEN(a.digits^) DO
      DEC(i);
      IF b.digits[i]#0 THEN RETURN 1 END;
    END;

    WHILE i>0 DO
      DEC(i);
      IF b.digits[i]#a.digits[i] THEN
        RETURN a.digits[i]-b.digits[i];
      END;
    END;

    RETURN 0

  END;

END Compare;


PROCEDURE (m: BigInteger) Add * (n: BT.GROUP): BT.GROUP;
VAR
  result,swap: BigInteger;
  len,i: LONGINT;
  carry: BOOLEAN;
BEGIN
  WITH n: BigInteger DO
    IF LEN(m.digits^)<LEN(n.digits^) THEN
      swap := m; m := n; n := swap;
    END;
    len := LEN(m.digits^);
    IF m.digits[len-1] >= MaxDigit DIV 2 THEN
      INC(len)
    END;
    IF (len=LEN(n.digits^)) & (n.digits[len-1] >= MaxDigit DIV 2) THEN
      INC(len)
    END;
    result := InternalCreate(len);
    IF m.negative = n.negative THEN
      result.negative := m.negative;
      carry := FALSE;
      FOR i:=0 TO len-1 DO
        result.digits[i] := 0;
        IF carry THEN
          INC(result.digits[i]);
        END;
        IF i<LEN(m.digits^) THEN INC(result.digits[i],m.digits[i]) END;
        IF i<LEN(n.digits^) THEN INC(result.digits[i],n.digits[i]) END;
        IF result.digits[i] >= MaxDigit THEN
          carry := TRUE;
          DEC(result.digits[i],MaxDigit);
        ELSE
          carry := FALSE;
        END;
      END;
    ELSE
      IF m.negative THEN
        swap := m; m := n; n := swap;
      END;
      carry := FALSE;
      FOR i:=0 TO len-1 DO
        result.digits[i] := 0;
        IF carry THEN
          DEC(result.digits[i]);
        END;
        IF i<LEN(m.digits^) THEN INC(result.digits[i],m.digits[i]) END;
        IF i<LEN(n.digits^) THEN DEC(result.digits[i],n.digits[i]) END;
        IF result.digits[i] < 0 THEN
          carry := TRUE;
          INC(result.digits[i],MaxDigit);
        ELSE
          carry := FALSE;
        END;
      END;
      IF carry THEN
        result.negative := TRUE;
        carry := FALSE;
        FOR i:=0 TO len-1 DO
          result.digits[i] := 0;
          IF carry THEN
            DEC(result.digits[i]);
          END;
          IF i<LEN(m.digits^) THEN DEC(result.digits[i],m.digits[i]) END;
          IF i<LEN(n.digits^) THEN INC(result.digits[i],n.digits[i]) END;
          IF result.digits[i] < 0 THEN
            carry := TRUE;
            INC(result.digits[i],MaxDigit);
          ELSE
            carry := FALSE;
          END;
        END;
      ELSE
        result.negative := FALSE;
      END;
    END;
  END;
  RETURN result;
END Add;


PROCEDURE (m: BigInteger) Neg * (): BT.GROUP;
VAR
  result: BigInteger;
  i: LONGINT;
BEGIN
  result := InternalCreate(LEN(m.digits^));
  IF result#NIL THEN
    FOR i:=0 TO LEN(m.digits^)-1 DO
      result.digits[i] := m.digits[i];
    END;
    result.negative := ~ m.negative;
  END;
  RETURN result;
END Neg;


PROCEDURE (m: BigInteger) Norm * (): LONGREAL;
VAR
  result: LONGREAL;
  i: LONGINT;
BEGIN
  result := 0;
  FOR i:=0 TO LEN(m.digits^)-1 DO
    result := 1000*result + m.digits[i];
  END;
  RETURN result;
END Norm;


PROCEDURE (m: BigInteger) Mul * (n: BT.RING): BT.RING;
VAR
  result: BigInteger;
  len: LONGINT;
  carry: INTEGER;
  zw: LONGINT;
  i,j: LONGINT;
BEGIN
  WITH n: BigInteger DO
    len := LEN(m.digits^) + LEN(n.digits^);
    result := InternalCreate(len);
    IF result#NIL THEN
      result.negative := m.negative # n.negative;
      FOR i := 0 TO LEN(m.digits^)-1 DO
        carry := 0;
        FOR j := 0 TO LEN(n.digits^)-1 DO
          INC(result.digits[i+j],carry);
          carry := 0;
          IF result.digits[i+j] >= MaxDigit THEN
            INC(carry);
            DEC(result.digits[i+j],MaxDigit);
          END;
          zw  := LONG(n.digits[j]) * LONG(m.digits[i]);
          INC(carry,SHORT(zw DIV MaxDigit));
          INC(result.digits[i+j],SHORT(zw MOD MaxDigit));
          IF result.digits[i+j] >= MaxDigit THEN
            INC(carry);
            DEC(result.digits[i+j],MaxDigit);
          END;
        END;
        INC(j,i);
        WHILE j < len DO
          INC(result.digits[j],carry);
          carry := 0;
          IF result.digits[j] >= MaxDigit THEN
            carry := 1;
            DEC(result.digits[j],MaxDigit);
          END;
          INC(j);
        END;
      END;
    END;
    RETURN result;
  END;
END Mul;


PROCEDURE (n: BigInteger) ConvertToString * (): BT.DynString;
(*
 * Allocates space for to^ and converts n to an ASCII-String
 *)
VAR
  i,off: LONGINT;
  to: BT.DynString;
BEGIN
  i := LEN(n.digits^);
  WHILE (i>0) & (n.digits[i-1]=0) DO DEC(i) END;
  NEW(to,i * 3 + 1);
  off := 0;
  DEC(i);
  to[LEN(to^)-3*i-3   ] := CHR(ORD("0") + n.digits[i] DIV 100 MOD 10);
  IF to[LEN(to^)-3*i-3]="0" THEN INC(off) END;
  to[LEN(to^)-3*i-2-off] := CHR(ORD("0") + n.digits[i] DIV  10 MOD 10);
  IF (off>0) & (to[LEN(to^)-3*i-2-off]="0") THEN INC(off) END;
  to[LEN(to^)-3*i-1-off] := CHR(ORD("0") + n.digits[i]         MOD 10);
  WHILE i>0 DO
    DEC(i);
    to[LEN(to^)-3*i-3-off] := CHR(ORD("0") + n.digits[i] DIV 100 MOD 10);
    to[LEN(to^)-3*i-2-off] := CHR(ORD("0") + n.digits[i] DIV  10 MOD 10);
    to[LEN(to^)-3*i-1-off] := CHR(ORD("0") + n.digits[i]         MOD 10);
  END;
  IF n.negative THEN
    to[0] := "-"
  ELSE
    to[0] := " ";
  END;
  RETURN to;
END ConvertToString;


END BigIntegers.