CS/COE 1501 Assignment 5 Algorithms to perform mathematical operations on large integers.

To get hands on experience with algorithms to perform mathematical operations on large integers.

High-level description
You will be writing a replacement for Java's BigInteger to perform multiplications and to run the extended Euclidean algorithm on integer values that would overflow long .

Specifications
1.   You are provided with the start of a class to process arbitrarily-sized integers called HeftyInteger . HeftyInteger objects are represented internally as two's-complement raw integers using byte arrays (i.e., instances of byte[] ).

1. Currently, HeftyInteger has the following operations implemented:

A constructor that creates a new HeftyInteger object based on a provided byte[] .

A method to compute the sum of two HeftyInteger objects.

A method to determine the negation of a HeftyInteger object.

A method to compute the difference of two HeftyInteger objects.

Several other helper methods.

2.   Due to the use of a two's complement representation of the integers, positive HeftyInteger objects should always have at least one leading 0 bit (indicating that the integer is positive) in their byte[] representation. This property may cause the array to be bigger than expected (e.g., a 1024-bit positive integer will be represented using a length 129 byte array).

3.   HeftyIntegers are represented using a big-endian byte-order, so the most significant byte is at index 0 of the byte[] .

4.   You will further need to implement the following functions:

HeftyInteger multiply(HeftyInteger other)

HeftyInteger[] XGCD(HeftyInteger other)

Any additional helper functions that you deem necessary.

5.   You may not use any calls the Java API class java.math.BigInteger or any other JCL class within HeftyInteger .

2. Once HeftyInteger is complete, make sure your implementation of HeftyInteger can be used to run the driver programs contained in MultiplicationTest.java and XgcdTest.java . To get full credit, your implementation should be efficient enough to complete multiplication or XGCD given 200digit inputs within 3 minutes.