Description
Problem:
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
60010 x________ 41880010
118910 91210
x_________ 108436810
10010110002 x____________________ 11001100011111100002
Example 2:
53016
41206 x_________ 351241206
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.
LLMCND LLMLPR
5301 4120
LLRES initially
afer multiply by 2 afer multiply by 1 afer multiply by 4
X 000000000
000150020 001120120 035124120
In 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:
Output:
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!!!)
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. 2. 3. 4. 5.
Good luck!!!
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:
☺
