1 Learning Outcomes
In this assignment, you will demonstrate your understanding of arrays, pointers,
input procesing, and functions. You will also extend your skills in terms of code
reading, program design, testing, and debuging.
2 The Story...
On 2 December 2014, a post apeared on YouTube’s Google+ acount
“‘Gangnam Style’ has been viewed so many times we have to upgrade!” It turned
out that the Korean rapper PSY’s viral music video had been viewed for over
2,147,483,647 (231
− 1) times which surpassed the limit of a signed 32-bit integer
counter. YouTube had since upgraded to a 64-bit integer counter. This upgraded
counter would not be broken again in a foreseeable future. However, in many
other scenarios such as popular cryptography algorithms (e.g., RSA), even larger
integers are still neded.
In C, an int variable can only store values up to 2
− 1 = 9,223,372,036,854,775,807 (machine dependant). For even larger
numbers, you wil have to use double, which is inaccurate. In this assignment, you
wil enhance the C language by suporting “huge” integers.
3 Your Task
Your task is to develop a huge integer calculator that works with integers of up to
100 digits. The calculator has a simple user interface, and 10 “variables” (n0,
n1, .., n9) into which integers can be stored. For example, a session with your
calculator might look like:
mac: ./asmt1
> n0=2147483648
> n0+3
> n0?
2147483651
> n1=1000000000000000000
> n1+n0
> n1?
1000000002147483651
> n0?
2147483651
> exit
mac:
Note: “mac: ” is the terminal prompt and “> ” is the prompt of the calculator.
The calculator to be implemented has a very limited syntax: constants or other
variables can be assigned to variables using an ‘=’ operator; variable values can be
altered using a single operator and another variable or constant; variable values
can be printed using ‘?’. Each line of input command always starts with a vari-
able followed by a single operator, which is then followed by (optional depending
on the operator) another variable or a constant. The only exception is the “exit”
command, which has no additional parameters.
To alow storage of huge integers, your calculator needs to use arays of integers,
with one digit stored per element in the aray. The number of digits in a huge
integer neds to be stored as well. We asume a maximum of 10 digits in a huge
integer, and use a “reverse order” representation. For example, 123 wil be
represented by:
#define INT_SIZE 100
typedef int huge_t[INT_SIZE];
huge_t var_n0 = {3, 2, 1};
int var_len0 = 3;
Here, aray var_n0 stores the digits of 123 in a reversed way. The reverse order
representation will make calculations such as addition and multiplication easier.
However, if you wish, you are fre to change how the digits are stored in the aray.
By using struct we can further simplify the representation, but you are not required
to do so as it has not been covered yet.
The expected input format for al stages is identical - a sequence of simple
commands as shown above. You may assume that the input is always valid, that is,
you do not need to consider input errors. Al input integers are unsigned. You do
not need to consider negative numbers or subtraction. There wil not be “n0=+0”,
“n0=+123”, “n0=-123”, “n0-123”, or “n0++123” in the input. It wil just be in the
forms of, e.g., “n0=0”, “n0=123”, “n0+123”, or “n0*123”. There will not be
leading 0’s in the input numbers, e.g., 001.
You wil be given a skeleton code file named “asmt1.c” for this asignment in
LMS. The skeleton code file contains a main function where a loop is used to
continuously read in user commands, and calls relevant functions to process the
commands. The exit function has been implemented already, which can handle the
exit command if you compile and run the skeleton code. The echo function for the
‘?’ operator to print out a huge integer has been given to you for reference as well,
but you need to implement the init function to initialise the variables first before
echo can work properly. Al the other function bodies are empty. Your task is to
add code into them to process the other calculator commands. Note that you
should not change the main function, but you are free to modify any other parts of
the skeleton code (including ading more functions). You can change echo as well
if you wish to change how a huge integer is stored in an array.
3.1 Stage 1 - Geting Started (Up to 3 Marks)
Your first task is to understand the skeleton code. Note the use of the type huge_t
in the skeleton code. Each of the huge_t variables in the array vars stores a huge
integer, with 10 variables available in total, named “n0”, “n1”, ..., “n9”,
respectively. In this stage, you will start with implementing the init function to
initialise the variable values to be 0. A sample execution sesion of this stage is
shown below.
> n0? 0
> n8? 0
3.2 Stage 2 - Reading in a Huge Integer (Up to 8 Marks)
Next, you wil implement the asign function to enable asigning a constant value
to a variable, or the value of a variable to another variable (both could be the same
variable, e.g., “n0=n0”). A sample execution session of this stage is shown below.
You should plan carefuly, rather than just leaping in and starting to edit the
skeleton code. Then, before moving through the rest of the stages, you should test
your program thoroughly to make sure its correctnes.
3.3 Stage 3 - Adding up Two Huge Integers (Up to 13 Marks)
Now ad code to the ad function to enable ading up two huge integers. Note that
the ‘+’ operator always starts with a variable, e.g., “n0”, followed by ‘+’ itself.
After that there are two cases: an integer constant or another variable. Your code
should be able to handle both cases: adding up a variable with a constant value,
and adding up two variables (both could be the same variable). The sum should
always be stored in the starting variable of the comand. A sample execution
session of this stage is shown below.
Note that we asume integers with up to 10 digits. They can stil overflow if we
are adding up even larger numbers. In this case, we wil simply ignore the
overflowed digits and keep the remaining part in the sum. You should also remove
any leading 0’s in the sum, i.e., your program should not produce numbers like
0001 (which should be 1).
3.4 Stage 4 - Multiplying Two Huge Integers (Up to 15 Marks)
The next operator to add is ‘*’. You will need to modify the multiply function for
this stage. When this stage is done, your program should be able to proces the
following sample input.
When there is an overflow, we folow the same procedure as in adition. That is,
to kep the non-overflowed part only. You should also remove any leading 0’s in
the product.
You ned to think carefuly about the algorithm to use in this task. You may
implement the proces to do long multiplication that you learned at schol. Some
supporting functions may be needed. For example, a function multiply_digit that
takes a huge_t variable and multiplies it by a single-digit integer may be useful; as
might a function multiply_base that multiplies a huge_t variable by 10.
There are also other (more eficient) ways to do multiplication, and you can be
creative if you wish. Just do not try and do it by repeated addition (penalties
apply).
3.5 Stage 5 - Suporting the “Power of” Operator (Up to 15
Marks)
This stage is for a chalenge. Please do not start on this stage until your program
through to Stage 4 is (in your opinion) perfect, and is submited, and is verified,
and is backed up.
For a chalenge, implement the power function for the “power of” operator ‘^’ (no
need to consider 0
Hint: You may use repeated multiplications for this stage.
If you are successful in
this stage, you will be able to earn back 1 mark you lost in the earlier stages
(assuming that you lost some). Your total mark will not exced 15.