Description
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
- 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[] ).
- 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.
- 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[] 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).
- HeftyIntegers are represented using a big-endian byte-order, so the most significant byte is at index 0 of the byte[] .
- 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.
- You may not use any calls the Java API class math.BigInteger or any other JCL class within HeftyInteger .
- 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.
