---
tags: 2023DS
---
# 2023 Data Structure - Homework 4
## Big number with BCD encoding and Linked-List
* Deadline: 5/19 - 14:00
* Upload your homework to **moodle** platform.
* Please consult with TA if you have any questions.
* FB or email
* Notice that this will be the **most difficult** homework in the Data Structure course, and you should start to complete it **as early as possible**.
## Review Our Expertise
* If you still remember **Big number** and **BCD encoding**, you can just view 「**Big number with BCD**」, and then go to read the problem and I/O description.
### Big number
**Big number** is a classic question in Computer Science. In all of the [primitive data types](https://en.wikipedia.org/wiki/Primitive_data_type), we can use the data type like```unsigned long long``` in C/C++ to store a number less than $2^{64} - 1$. But, if the number is larger than the maximum of ```unsigned long long```, the one of strategies is using **Big number**. That is, we just use **more bytes** to store the number.

The common way of storing a big number uses an **array** to store each digit of the number.
* pseudo code of storing big number (e.g. ```23456789125678912345```, and an array with ```byte``` type).

num_str <- "23456789125678912345" // 20 digits
byte array[50]    // It can store a number with 50 digits

for i (0 to num_str.length) do
    array[i] <- num_str[i] - '0';
end for

Now, here wants to discuss two big numbers' **addition**. If you want to add two big numbers, you may store them in two different arrays, reverse them, add them digit by digit to the third array and reverse the third array to get the correct result.
* pseudo code - Add two big numbers

func initBigN(array, num_str)
    for i (0 to num_str.length) do
        array[i] <- num_str[i] - '0';
    end for
end func

func addBigN(array3, array1, array2)
    reverse(array1)
    reverse(array2)
    
    carry <- 0
    for i (0 to array1.length) do
        array3[i] <- array1[i] + array2[i] + carry
        carry <- array3[i] / 10
        array3[i] <- array3[i] % 10
    end for
    
    reverse(array3)
end func

num_str1 <- "23456789125678912345"
byte array1[50]
num_str2 <- "14562332554589123456"
byte array2[50]

initBigN(array1, num_str1)
initBigN(array2, num_str2)

byte array3[50]
add(array3, array1, array2)

Then, you need to use dynamic memory allocation to store a big number if you want to store it without the information of the number of digits (that is, ```num_str```'s length).

And, you may suffer from the cost of addition, which needs to reverse arrays three times, **unless you store the big number reversely**.
* Another way to store a big number.

num_str <- "23456789125678912345" // 20 digits
byte array[50]    // It can store a number with 50 digits

for i (0 to num_str.length) do
    array[i] <- num_str[num_str.length - i - 1] - '0';
end for
// the byre array will be {6, 5, 4, 3, 2, 1, 9, 8..., 5, 4, 3, 2}

So that, your addition doesn't need to reverse three times! You just add two numbers to the third array, and print out the elements of the third array from end to start!
### BCD encoding
In our department, we have two courses - "Introduction to Digital Systems"（數位系統導論） and "Digital Circuits"（數位電路學）to introduce some basic computer architecture and digital circuits.

However, there must have a chapter - "Encoding", and you can learn many encoding (e.g. Binary Code, Gary Code) and know their usages.

Here helps to review **BCD** encoding. Basically, BCD coding is using 4-bit to **store a digit of a number**. Remember that BCD code doesn't use 5 codes - ```0b1010 ~ 0b1111``` because they represent ```10 ~ 15``` in decimal.
* DEC-to-BCD coding

DEC              BCD coding 
              (bin)       (hex)
0            0b0000        0x0
1            0b0001        0x1
2            0b0010        0x2
3            0b0011        0x3
4            0b0100        0x4
5            0b0101        0x5
6            0b0110        0x6
7            0b0111        0x7
8            0b1000        0x8
9            0b1001        0x9
--------------------------------
10          (no use)    (no use)
11          (no use)    (no use)
12          (no use)    (no use)
13          (no use)    (no use)
14          (no use)    (no use)
15          (no use)    (no use)

Here is an example:
* Store ```159``` and ```86742``` by BCD encoding

159 -> 0b0001 0b0101 0b1001 (binary)
    -> 0x159                (hexadecimal)

86742 -> 0b1000 0b0110 0b0111 0b0100 0b0010
      -> 0x86742

Now, similarly, let's discuss **addition** in BCD encoding.
* Use the previous two numbers ```159``` and ```86742```

159 + 86742 = 86901

Addition of two BCD numbers
carry                            1         1
        0b0000    0b0000    0b0001    0b0101    0b1001
+ )     0b1000    0b0110    0b0111    0b0100    0b0010
--------------------------------------------------------
        0b1000    0b0110    0b1001    0b1010    0b1011 
           |         |         |     +0b0110   +0b0110  (it needs to add 6 when overflow!)
           |         |         |     -------   -------
           |         |         |      0b0000    0b0001
           |         |         |         |         |
->ans:  0b1000    0b0110    0b1001    0b0000    0b0001
 (DEC)     8         6         9         0         1  

You should review how BCD encoding works to understand the above process.
### Big number with BCD
Here combines big number and BCD encoding together! Let's use BCD encoding to store a big number!

View the previous example again - store a big number ```23456789125678912345 (20 digits)```

If you store the big number by a ```byte``` array, it needs at least **20** bytes to store it.

But, let's use BCD encoding to store it.

23456789125678912345
->   23   45   67   89   12   56   78   91   23   45 (DEC)
-> 0x23 0x45 0x67 0x89 0x12 0x56 0x78 0x91 0x23 0x45 (BCD with hexadecimal)

(You can convert the number to BCD with binary first, 
and becomes hexadecimal! 
Then, you will know how it works.)

So, we get a hexadecimal number: ```0x23456789125678912345```.

## Problem
* **Please go to moodle to download the test case and needed source code.** (```hw4-ref-testcase.zip```)

Here explains the header ```bcd.h``` provided by TA.
### bcd.h
**TA has completed the class ```BCD64```**, which uses ```uint64_t``` (aka```unsigned long long```) type to store a number having length less than **16** digits by BCD encoding.
* class ```BCD64``` declaraition. Actually, **```BCD64```'s declaration and implementation are written in ```bcd.h```**, and here just shows it's declaration.

class BCD64 {
    public:
	BCD64();

	BCD64(uint64_t bcd);

	BCD64(const BCD64 &bcd_obj);

	BCD64(string &num_str);

	BCD64 add(BCD64 &num, unsigned char *carryout = nullptr, unsigned char carryin = 0) ;
            
	friend ostream &operator<<(ostream &sout, BCD64 &num);

    private:
	uint64_t bcd;
};

TA has defined the methods so that you can use them to finish your homework 4.

// The usage of constructor/methods
// Notice that BCD64's data member - `bcd` stores the encoded number. 

BCD64 obj1;             // create a number - 0
BCD64 obj2(0x6414589);    // create a number - 0x6414589

BCD64 obj3("185456214562186") /* create a number 0x185456214562186 
                               * the length of string should be less than 16.
                               * */

BCD64 obj4("1854562145621864821562189") // Exception will occur!

uint8_t carry = 0;    /* You may need to prepare a carry variable to 
                       * get the carryout produced by add() method!
                       * 
                       * And, initialize it to 0!
                       * */
                       
BCD64 obj5 = obj2.add(obj3, &carry);    /* Add obj2 and obj3 to obj5. 
                                         * 
                                         * You may use the third parameter 
                                         * when using linked list!
                                         * */
cout << obj5 << endl;    // It can be printed by cout directly!

You can see the test cases, and you will find that all input are numbers with digits (```'0' ~ '9'```). So, **Don't worry that input may has ```'a', 'b', 'c', 'd', 'e'``` characters**. But **you still need to prevent the length of string large than 16, which is passed to constructor**.

---
### Target
Now, Given the file ```bcd.h``` with class ```BCD64```, please write a class ```LinkedList``` using ```BCD64``` to store a big number!

**Hint [4/20 17:39 updated]**

class ListNode {
public:
    // ...
private:
    BCD64 obj;
    // ...
};

Your ```LinkedList``` can be **singly** list or **doubly** list.
## Input Description
There just has one test file ```test.in``` with $2n$ lines. (That is, it has $n$ cases.) You just read the input until EOF!
Each case consists of two lines, containing two numbers separately.
### Sample Input
* ```test.in```

45
5
898888889
111111111
4789125486211584
6415878115268
7894141128974124189414778999
1174753214485321584123574881001
456215567892412354586875624156153579873278
456241862153878523418753242357
7448621117475321445615678424484565486215868785321584123574881001447895
448362156555896221456115
5144563145185654896515832418568754621535456948695156348972412374897635412374856248954878924231504561
4945615321565748954352156212324896873215632415674742321567483542378104556778954234835248565423153219

## Output Description
Output a formula, ```<summand> + <addend> = <sum>```, means the sum of two big numbers.
### Sample output
* ```test.out```

45 + 5 = 50
898888889 + 111111111 = 1010000000
4789125486211584 + 6415878115268 = 4795541364326852
7894141128974124189414778999 + 1174753214485321584123574881001 = 1182647355614295708312989660000
456215567892412354586875624156153579873278 + 456241862153878523418753242357 = 456215567892868596449029502679572333115635
7448621117475321445615678424484565486215868785321584123574881001447895 + 448362156555896221456115 = 7448621117475321445615678424484565486215868785769946280130777222904010
5144563145185654896515832418568754621535456948695156348972412374897635412374856248954878924231504561 + 4945615321565748954352156212324896873215632415674742321567483542378104556778954234835248565423153219 = 10090178466751403850867988630893651494751089364369898670539895917275739969153810483790127489654657780

Hint: ```<iomanip>```
## Python - Validation
TA provides a simple python code to help everyone to check the answer.
* ```bignum.py```

# Python has builtin big number!
while True:
	try:
		num1 = int(input())
		num2 = int(input())
		print(num1, "+", num2, "=", num1 + num2)
	except:
		break

You can create your test cases to test your program and validate it by the python code.

// Hint: Command Line - I/O Redirection

// Windows style
$ python bignum.py < test.in

// Linux/MacOS style     (I still don't know MacOS...)
$ python3 bignum.py < test.in

/* If you have difficult to use command, 
 * you can modify the given python code to use File I/O.
 * */

## Restriction
**C++ STL containers**, such as ```<stack>```, ```<vector>```... , **are forbidden** for this homework.

And, for ```<string>```, ```string``` **is just accepted to be used in two places.**
1. main function: Read the input. Here shows an example.

#include <iostream>
#include <string>
using namespace std;

int main(void) {
    string num1;
    string num2;
    
    while(getline(cin, num1) && getline(cin, num2)) {
        // Create your objects and add two big numbers
        // <Your list class> obj1();
        // <Your list class> obj2();
        // <Your list class> sum = obj1 + obj2;
    }
    
    return 0;
}

2. Be **parameter(s) and local variable(s) of your classes' constructors**!
* That is, for your data members and other methods, they cannot use any ```string``` object!

:::info
此處的限制並不是禁制使用string 的 ".size()" 或是 "[i]"，主要是限制在建構BCD64儲存輸入值時，不能夠在BCD64中使用string 變數值將將直儲存起來。
:::
## Score
* Source code and your output of ```test.in```: 50% + 5%
* Source code: 40%
* Remind you that uses ```new```/```delete``` to allocate and deallocate memory.
* output: 10%
* **Bonus: 5%**
* **Test your program, and add two big numbers with at least 300 (or more) digits. If it is correct, the extra 5 points will be given.**
* **Bonus output filename: ```ex-test.out```**
* Report: 50%

Your compressed file:

|-A110500_hw4.zip (.rar)
| |-main.cpp
| |-xxx.h
| |-xxx.cpp
| |-Report.pdf
| |-(And other files...)

or

|-A1105500_hw4.zip (.rar)
| |-A1105500 (Folder)
| | |-main.cpp
| | |-xxx.h
| | |-xxx.cpp
| | |-Report.pdf
| | |-(And other files...)

### The key points of your report
Here lists some questions, and you can **select at most three** questions to write your report.

**Notice that this report is just scored at most three questions.**
#### 1. Your **thoughts**(心得): 10%
#### 2. The advantages of Big number with BCD encoding: 10%
* Hint: **At least two advantages.**
#### 3. Design of your **linked list**: 10%
Please describe your design and consideration of linked list and how to use ```BCD64``` to store a big number.
#### 4. Review/Improve class ```BCD64```: 20%
Class ```BCD64``` is created by TA and helps you to store a BCD encoded number. But, actually, the current implementation **is not optimal** (especially, for linked list), and you may view the ```BCD64```'s design.

Please write down...
1. how does ```BCD64``` work?
2. The current fault of the ```BCD64```.
3. how to improve ```BCD64``` so that the performance can be raised
4. After doing ```2. 3.```, tell me your modification and consideration of the new design of **your class BCD**
* Assurely, **C++ STL is forbidden.**
#### 5. Comparison with other data structure: 20%
You may be curious that why don't use **other data structures or other ways** to store a big number.

Here provides some comparisons

* The way of storing big numbers
* **General Big number**: means the way mentioned in **Review Our Expertise** (Store each digit)
* Storing each digit is the easiest way, and you can use ```uint32_t``` or ```uint64_t``` to store a big number...
* **BCD encoded Big number**
* The data structures
* Array
* Linked List

So, there has **4** combinations (If you stores general big number by other data types, it can be up to **6** combinations).

Then, you just list **1~2** comparison(s) and provide your analysis so that the score of this part will be given.

Here notices some important precautions:
1. The standard of comparison between 2 items should be the same as possible:
* e.g.:
* Everything is an object.
* Array vs Linked List (They should use BCD encoding or general big number, simultaneously.)
* General big number vs BCD encoding (Use array or linked list simultaneously.)
2. Time measurement: you may use ```clock_gettime()``` and ```struct timespec``` to calculate the execution time. (or by other functions to get the execution time)
* Also, the assessment of the elapsed time should use the same standard.
* e.g.: If you compare **array** with **linked list**, you should test the time of ...
* creating objects
* adding two objects (big numbers)
* printing the result

, respectively.
* You can record the above time together.
## Previous TA's experiment(reference)
I also write this question. (Of course, because this homework is designed by me. XD)

I write two classes - ```bcd-list``` and ```bcd-arr```, which implement big number with BCD encoding by linkedlist and array, respectively.

I compare this two ways to parse their the time consumption and expect that array implementation will be faster than list implementation.

I prepare 17 test cases, and their number of digits are listed as following:

     the number of digits
summand                 addend
2 			 1
3 			 3
4 			 5
41 			 41
50 			 50
133 			 68
99 			 142
205 			 186
344 			 392
1187 			 1232
2380 			 2376
4761 			 4759
4761 			 4751
6910 			 7127
9522 			 9502
14281 			 14235
19044 			 19004

Then, I calculate these two implementations' execution time (containing the time of **creation of objects**, **addition of big numbers** and **the print out**) and find a surprising result!
* Experiment - running three times and thier results:
* 
* 
* 
---
**List implementation can be faster than array???**

Actually, it also has to analyze the space usage.