CS/COE 1501 Assignment 5
Goal:
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
integers values that would overflow long.

Specifications:
1. You are provided with the start of a class to process arbitrarily
sized integers called HeftyInteger. HeftyIntegers 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
based off of a provided byte[].

▪ A method to compute the sum of two
HeftyIntegers.

▪ A method to determine the negation of a
HeftyInteger.

▪ A method to compute the difference of two
HeftyIntegers.

▪ Several other helper methods.

• Due to the use of a two's complement representation of
the integers, positive HeftyIntegers 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).

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

• You will 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
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
200-digit inputs within 3 minutes.

Submission Guidelines:
• DO NOT SUBMIT any IDE package files.

• You must be able to compile the driver programs by running
javac MultiplicationTest.java and javac XgcdTest.java,
respectively.

• You must be able to run the driver program by running java
MultiplicationTest and java XgcdTest, respectively.

• You must fill out info_sheet.txt.

• Be sure to remember to push the latest copy of your code
back to your GitHub repository before the the assignment is
due. At the deadline, the repositories will automatically be
copied for grading. Whatever is present in your GitHub
repository at that time will be considered your submission for
this assignment.

Grading Rubric
• HeftyInteger

◦ multiply works properly: 40

◦ XGCD works properly: 55

• Assignment info sheet/submission: 5

欢迎咨询51作业君