COMP 212
Programming Assignment 1
Due Febuary 23, 2000

Most computer languages provide facilities for the fast manipulation of small integers (byte or word size) but not for large integers (requiring many words to represent). The purpose of this assignment is to design and implement a new abstract data type VeryLongInt (VLI). VLIs are integers with a finite (but not predetermined) length. You are to design and implement operations that will allow a client to

1.

read in and store VLIs,

2.

print out VLIs,

3.

negate a VLI,

4.

add two VLIs,

5.

subtract one VLI from another,

6.

compare two VLIs (i.e., compute the relations ==, <, >, >=, <=),

7.

multiply two VLIs,

8.

and compute the remainder resulting from the division of one VLI by another, i.e., the mod function.

Having implemented your ADT, you are to show its usefulness by writing the following client programs:

1.

Given two VLIs compute their greatest common divisor (GCD).

2.

Given three VLIs x, y and z compute x^y mod z.

Both of the above calculations are common in certain cryptographic protocols. A good starting point for this assignment may be found in the text by looking at the implementation of the polynomial ADT in section 4.9. Horner's rule described on page 195 can be adapted to the problem of computing x^y if one thinks of a integer as a polynomial evaluated at the number's base. Note also that x * y mod z = (x mod z) * (y mod z). Program 5.3 is a recursive implentation of Euclid's algorithm for computing the GCD.

As a bonus write a program to decide which of the following are prime numbers: 30³² +1, 2¹²⁷ -1 and 2¹⁰¹ -1.