Ulm's Oberon Library: LargeIntegers

NAME

LargeIntegers - implementation of almost arbitrary large integers

SYNOPSIS

```TYPE LargeInteger = POINTER TO LargeIntegerRec;
TYPE LargeIntegerRec = RECORD (IntOperations.OperandRec) END;

PROCEDURE Create(VAR op: Operations.Operand);
PROCEDURE ReadS(s: Streams.Stream; VAR op: Operations.Operand);
PROCEDURE WriteS(s: Streams.Stream; op: Operations.Operand);
PROCEDURE Write(op: Operations.Operand);
PROCEDURE GCD(a, b: Operations.Operand; VAR res, c, d: Operations.Operand);
PROCEDURE Inverse(a, b: Operations.Operand; VAR res: Operations.Operand);
```

DESCRIPTION

LargeIntegers is an implementation of Operations and IntOperations. It provides arithmetic operations for almost arbitrary large integers. Each number is stored in a block allocated with SYSTEM.NEW and treated as an array of LONGINT (or any other whole-numbered variable type). Only the unsigned part of such a variable type is used and therefore one bit is vasted when using signed variable types. To avoid a lot of slow memory reallocations, memory is often not freed if the integers absolute value is decreased.

Create creates and initializes an operand op of type LargeInteger.

In addition to the procedures required by the interfaces Operations and IntOperations the following functions have been implemented:

Inverse: PROCEDURE(a, b: Operations.Operand; VAR res: Operations.Operand);
calculate a * res = 1 (mod b).

GCD: PROCEDURE(a, b: Operations.Operand; VAR res, c, d: Operations.Operand);
solves the equation a * c + b * d = res for the smallest possible absolute value of res (which is the greatest common divisor of a and b).
The other procedures provide in- and output functionality. Read and Write use Streams.stdin resp. Streams.stdout, ReadS and WriteS require any stream derived from Streams.Stream.

DIAGNOSTICS

Two kinds of assertions might fail in LargeIntegers:
DivMod
Divisions by zero cannot be recovered right now, but this can easily be changed in the future.
Log2
The logarithm of none positive numbers also leads to a program termination.

Operations
generic interface for arithmetic operations
IntOperations
generic interface for arithmetic integer operations
Card1024s
implementation of 1024 bit cardinals
SYSTEM
system-dependent built-ins of Ulm's Oberon Compiler

BUGS

Due to a low number of tests, there are most likely a lot of them left. Also LargeIntegers has been written to work with signed and unsigned blocks. This has never been tested with unsigned variables which has to be done as soon as an unsigned integer base type is available.

AUTHOR

Ingo Melzer
Edited by: , last change: , revision: , converted to HTML: 1999/02/22