CSE225 Data Structures Project 1 -Solved

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 
1. the source code of your program 
2. an executable version of your program, 
3. a sample input file 
4. a sample output file 
5. and a documentation in a proper word processor that contains a 
detailed discussion of your algorithm: 
Good luck!!! ☺