Description
Assume two positive natural numbers of (theoretically) infinitely many digits
specified in any-base number system such as binary, octal, decimal etc. (but no
number base system larger than the decimal system is mandatory). How can we
multiply them in our computer? We look for a solution that is capable of multiplying
two such numbers. All numbers concerning the multiplication (i.e., the multiplicand
and the multiplier and the result) should be shown both in the original number system
presented to your program and in the decimal system.
Example 1:
10101110102
69810
10010110002
60010
x____________________
x________
11001100011111100002
41880010
Example 2:
53016
118910
41206
91210
x_________
x_________
351241206
108436810
The requirement that the numbers may be infinitely large implies that you cannot use
standard data types to represent these numbers. Therefore, you will need a data
structure that appropriately represents such large natural numbers and you will
redefine the multiplication operation in terms of these data structures. A typical data
structure to exploit in this case is linked lists (LLs). You may hold each number
(including the result) in a LL each digit stored in a node and, while multiplying each
pair of digits of multiplicand and multiplier, you may accordingly update the relevant
digits in the result. We provide below how the second example is implemented.
Please note that the numbers are base-6 numbers and multiplication is performed in
this number system.
5
3
0
1
4
1
2
0
X
0
0
0
0
0
0
0
0
0
initially
LLMCND
LLMLPR
LLRES
0
0
2
0
0
0
1
5
0
afer multiply by 2
0
1
2
0
0
1
1
2
0
afer multiply by 1
4
1
2
0
3
5
1
2
0
afer multiply by 4In this project you are expected to develop an algorithm that is capable of finding a
solution to the above problem and implement this algorithm in ANSI C. Provided
that your program correctly finds a solution, you will earn the more credits for your
algorithm the shorter it requires to run to completion. The following points are given
to clarify what is given and what is expected at the end of this project:
Input:
An input file containing
- the multiplicand,
- the multiplier, and
- the base 2≤k≤10 (note that any number with any digit l≥k is invalid in
a k-base number system!!!)
Output:
An output file containing
- the multiplicand
- the multiplier and
- the result
in both k-base and decimal number system.
You are responsible for demonstrating your program to Mr. Mehmet Kaya at a date to
be specified and announced from the class’ webpage. By the due date you are to
electronically submit
- the source code of your program
- an executable version of your program,
- a sample input file
- a sample output file
- and a documentation in a proper word processor that contains a
detailed discussion of your algorithm:
