CEng242 Homework 3
Due 29^th March 2002

Some applications in computer science and technology like crypthography require arithmetic operations on integers without precision limits. In this homework you will implement an abstract data type for arbitrary precision signed integers. Number of digits in an arbitrary precision integer (I will name it ArbInt) is not limited. Theoretically you can have integers with millions of decimal digits. Since they cannot fit into any primitive or static data type they should be stored and processed in dynamic data structures like lists. Also operations like addition and multiplication cannot be carried out by the primitive operators of the processor, so a library of operators should be presented.

For all operators you can use primary school methods and algorithms. For multiplication there exists a nice algorithm from Donald Knuth. Feel free to use any algorithm as long as you understand it and you can show the internals of the algorithm when you are asked to. Your implementation should be an original work coded by you. Also another requirement is the efficiency. Adding n to 0 m times is not an effifient algorithm for multiplying m and n. Such a multiplication will last centuries for numbers with thousand digits. On the other hand it will last some seconds if you implement the primary school algorithm. Note that you are not limited to base 10 since your interpreter is capable of making operations on larger integers. So you can use any base with those algorithms.

You will define and implement an abstract data type ArbInt with the following exported operators, functions and values:

fromInt

int->ArbInt
Gets an integer and returns an arbitrary precision integer value.

DivisionbyZero

Exception
Exception to raise if a division by zero occurs.

InvalidNumber

Exception
Exception to raise if the string is not a valid integer.

fromString

string->ArbInt
Given a string containing a signed decimal notation, returns the corressponding ArbInt value. String can contain heading and trailing spaces and negative marker `~' like " ~1234567 ". If the string contains non-digit symbols, inner spaces function will raise InvalidNumber.

toString

ArbInt->string
Given an ArbInt value returns the signed decimal notation of the number in a string.

++

ArbInt*Arbint->Arbint
An infix operator for addition of two signed ArbInt values.

--

ArbInt*Arbint->Arbint
An infix operator for subtraction of two signed ArbInt values.

**

ArbInt*Arbint->Arbint
An infix operator for multiplication of two signed ArbInt values.

//

ArbInt*Arbint->Arbint
An infix operator for integer division of two signed ArbInt values. It is the integer part of the division. It corressponds the div operator of SML. Behaviour in negative values will be the same with the SML interpreter. If second operator is a zero DivisionbyZero is raised.

%%

ArbInt*Arbint->Arbint
An infix operator for integer remainder of two signed ArbInt values. It is the remadinder part of the integer division. It corressponds the mod operator of SML. Behaviour in negative values will be the same with the SML interpreter. If second operator is a zero DivisionbyZero is raised.

<< >> == <<= >>= !=

ArbInt*Arbint->bool
Infix operators for comparison of ArbInt values corressponding to < , > , = , <= , >= , <> respectively.

Operator precedences should be adjusted so that comparison operators have the lowest precedence, then addition and subtraction and then the other operators should come.

Your implementation should not produce any other definition than the definitions above. Enclose any other defitinitions in your implementation into a local ... in block inside of the abstype body.

Grading
The division and remainder operators are optional and will be graded as +20 bonus to your total 100. Late submission will be possible until the sunday midnight (31 March) with a -20 points give up.