--- date: '2024-02-11' description: assignment on large integer addition and multiplication algorithms including karatsuba method with recurrence tree analysis and master theorem. id: A4 modified: 2026-06-05 15:08:41 GMT-04:00 tags: - sfwr2c03 title: Efficient additions created: '2024-02-11' published: '2024-02-11' pageLayout: default slug: thoughts/university/twenty-three-twenty-four/sfwr-2c03/a4/A4 permalink: https://aarnphm.xyz/thoughts/university/twenty-three-twenty-four/sfwr-2c03/a4/A4.md generator: quartz: v4.6.0 hostedProvider: Cloudflare baseUrl: aarnphm.xyz full: https://aarnphm.xyz/llms-full.txt --- ## problem statement. Typically, we assume that basic operations on natural numbers (e.g., adding or multiplying two natural numbers together) are performed in constant time. In practice, this assumption is correct whenever we restrict ourselves to natural numbers with some maximum size (e.g., 64 bit natural numbers, for which basic operations are supported directly by modern processors). Applications such as cryptography often work with huge natural numbers, however (e.g., 4048 bit values, which can hold a maximum of $\approx 3.7 \cdot 10^{1218}$). Hence, for these applications we can no longer assume that operations on natural numbers are in constant time: these applications require the development of efficient algorithms even for basic operations on natural numbers. Consider two $n$-digit natural numbers $A = a_{1} \dots a_{n}$ and $B = b_{1} \dots b_{n}$ written in base 10: the digits $a_{1} \dots a_{n}$ and $b_{1} \dots b_{n}$ each have a value in $0 \dots 9$. For example, if $n=4$, then we could have $A=3456, B=9870$, in which case $a_{1}=3, a_{2}=4, a_{3}=5, a_{6}=6, b_{1}=9, b_{2}=8, b_{3}=7, b_{4}=0$. > \[!question\] 1.1 > > Write an algorithm `ADD(A, B)` that computes $A + B$ in $\Theta(n)$. Explain why your algorithm is correct and the runtime complexity is $\Theta(n)$. Assumption: one converts $A$ and $B$ into two arrays of $n$ integers, $A = \lbrack a_{1} \dots a_{n} \rbrack$ and $B = \lbrack b_{1} \dots b_{n} \rbrack$.

"\\begin{algorithm}\n\\caption{ADD(A, B)}\n\\begin{algorithmic}\n\\INPUT $A \\coloneqq \\lbrack a_{1} \\dots a_{n} \\rbrack$\n\\INPUT $B \\coloneqq \\lbrack b_{1} \\dots b_{n} \\rbrack$\n\\STATE $C \\gets \\lbrack \\space \\rbrack \\text{ where } |C| = n + 1$\n\\STATE $carry \\gets 0$\n\\STATE $i \\gets n-1$\n\\WHILE{$i \\geq 0$}\n \\STATE $C[i+1] \\gets (a_{i} + b_{i} + carry) \\mod 10$\n \\STATE $carry \\gets \\lfloor (a_{i} + b_{i} + carry) / 10 \\rfloor$\n \\STATE $i \\gets i - 1$\n\\ENDWHILE\n\\STATE $C[0] \\gets carry$\n\\IF{$C[0] == 0$}\n \\STATE $C \\gets C[1 \\dots n]$\n\\ENDIF\n\\OUTPUT $C$\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 20 ADD(A, B)

Input: $A \coloneqq \lbrack a_{1} \dots a_{n} \rbrack$

Input: $B \coloneqq \lbrack b_{1} \dots b_{n} \rbrack$

1: $C \gets \lbrack \space \rbrack \text{ where } |C| = n + 1$

2: $carry \gets 0$

3: $i \gets n-1$

4:while $i \geq 0$ do

5: $C[i+1] \gets (a_{i} + b_{i} + carry) \mod 10$

6: $carry \gets \lfloor (a_{i} + b_{i} + carry) / 10 \rfloor$

7: $i \gets i - 1$

8:end while

9: $C[0] \gets carry$

10:if $C[0] == 0$ then

11: $C \gets C[1 \dots n]$

12:end if

Output: $C$

Runtime complexity: $\Theta(n)$ - L1 takes $\Theta(n)$ time to initialise. - `while` loop iterates $n$ times, each iteration perform constant time operations (additions, modulo, division) in $\Theta(1)$ time. - Finally, the adjustment of the output array $C$ takes $\Theta(1)$ time. Thus, total runtime complexity is $\Theta(n)$. Correctness: Invariants: $$ \begin{align} 0 \leq i \leq n-1, & \space i+2 \leq j \leq n \land c_{n-1} = 0 \\\ \quad c &= \lfloor \frac{\sum_{k=i+1}^{n-1}(a_k + b_k + c_k)}{10^{n-k-1}} \rfloor \mod 10 \\\ \quad C[i+1] &= (a_i + b_i + c) \mod 10 \\\ \quad C[j] &= ((a_{j-1} + b_{j-1} + c_{j-1}) \mod 10) \end{align} $$ where $c$ defines as the carry value resulting from the addition. bound function $f(i) = |A| - i$ starts at $|A|, |A| \geq 0$ _Proof_ Base case: $i = n-1$ (_L2,3_) Invariant for carry holds, as $c_{i} = c_{n-1} = 0$ Now we will prove these invariants still hold til reach the end of `m-th` loop: Assuming the invariants hold at the start of `m-th` loop, or: $$ \begin{align*} 0 \leq &m \leq n-1 \\\ c_m &= \lfloor \frac{\sum_{k=m}^{n-1}(a_k + b_k + c_k)}{10^{n-k-1}} \rfloor \mod 10 \\\ \quad C[m+1] &= (a_m + b_m + c_m) \mod 10 \\\ \quad C[j] &= ((a_{j-1} + b_{j-1} + c_{j-1}) \mod 10) \end{align*} $$ L4-7: The `while` loop. - Carry forward invariants holds $c_{m-1} = c_{\text{new}} = \lfloor \frac{(a_m + b_m + c_m)}{10} \rfloor \mod 10$ - $C[m+1] = (a_m + b_m + c_m) \mod 10$, or $C[m+1]$ holds correct digits after addition of $a_m, b_m$ and carry $c_m$ - $f(i)$ strictly decreases after each iteration, $i_{\text{new}} := i + 1$ Therefore the invariants holds. > \[!question\] 1.2 > > What is the runtime complexity of this algorithm in terms of the number of digits in A and B? Runtime complexity is $\Theta(n^2)$, where $n$ is the number of digits in $A$ and $B$. For each digits of $B$, it multiply every digits of $A$, which results in $n^2$ operations. Each addition operation takes at most $2n$ digit additions, and we perform $n$ of these additions, therefore resulting in $O(n^2)$ time. Overall, pen-and-paper addition of two $n$-digit numbers takes $\Theta(n^2)$ time. > \[!question\] 1.3 > > Let $C$ be an $n$-digit number with $n=2m$. Hence, $C = C_{\text{high}} \cdot 10^m + C_{\text{low}}$ where $C_{\text{high}}$ the first $m$ digits of C and $C_{\text{low}}$ is the remaining $m$ digits of C. For example, if $n=4, A=3456, B=9870$, then $m=2$ and > > $$ > \begin{aligned} > &A=A_{\text{high}} \cdot 10^m + A_{\text{low}}, &A_{\text{high}} = 34,\quad &A_{\text{low}} = 56 \\\ > &B=B_{\text{high}} \cdot 10^m + B_{\text{low}}, &B_{\text{high}} = 98,\quad &B_{\text{low}} = 70 > \end{aligned} > $$ > > Using the breakdown of a number into their high and low part, one notices the following > > $$ > \begin{aligned} > A \times B &= (A_{\text{high}} \cdot 10^m + A_{\text{low}}) \cdot (B_{\text{high}} \cdot 10^m + B_{\text{low}}) \\\ > & = A_{\text{high}} \times B_{\text{high}} \cdot 10^{2m} + (A_{\text{high}} \times B_{\text{low}} + A_{\text{low}} \times B_{\text{high}}) \cdot 10^m + A_{\text{low}} \times B_{\text{low}} > \end{aligned} > $$ > > Here is the following recursive algorithm `BREAKSDOWNMULTIPLY(A, B)` that computes $A \times B$: > >

"\\begin{algorithm}\n\\caption{BREAKSDOWNMULTIPLY(A, B)}\n\\begin{algorithmic}\n\\INPUT $A \\text{ and } B \\text{ have } n=2m \\text{ digits}$\n\\IF{$n = 1$}\n \\RETURN $a_{1} \\times b_{1}$\n\\ELSE\n \\STATE $hh \\coloneqq \\text{BREAKSDOWNMULTIPLY}(A_{\\text{high}}, B_{\\text{high}})$\n \\STATE $hl \\coloneqq \\text{BREAKSDOWNMULTIPLY}(A_{\\text{high}}, B_{\\text{low}})$\n \\STATE $lh \\coloneqq \\text{BREAKSDOWNMULTIPLY}(A_{\\text{low}}, B_{\\text{high}})$\n \\STATE $ll \\coloneqq \\text{BREAKSDOWNMULTIPLY}(A_{\\text{low}}, B_{\\text{low}})$\n \\RETURN $hh \\cdot 10^{2m} + (hl + lh) \\cdot 10^m + ll$\n\\ENDIF\n\\RETURN $A \\times B$\n\\end{algorithmic}\n\\end{algorithm}"

> Algorithm 21 BREAKSDOWNMULTIPLY(A, B)

> Input: $A \text{ and } B \text{ have } n=2m \text{ digits}$

> 1:if $n = 1$ then

> 2:return $a_{1} \times b_{1}$

> 3:else

> 4: $hh \coloneqq \text{BREAKSDOWNMULTIPLY}(A_{\text{high}}, B_{\text{high}})$

> 5: $hl \coloneqq \text{BREAKSDOWNMULTIPLY}(A_{\text{high}}, B_{\text{low}})$

> 6: $lh \coloneqq \text{BREAKSDOWNMULTIPLY}(A_{\text{low}}, B_{\text{high}})$

> 7: $ll \coloneqq \text{BREAKSDOWNMULTIPLY}(A_{\text{low}}, B_{\text{low}})$

> 8:return $hh \cdot 10^{2m} + (hl + lh) \cdot 10^m + ll$

> 9:end if

> 10:return $A \times B$

> > Prove that algorithm `BREAKSDOWNMULTIPLY(A, B)` is correct. The proposed `BREAKSDOWNMULTIPLY(A, B)` is a variant of Karatsuba’s algorithm. Base case: $m=1 \implies n=2$, which implies $A \times B$ are correct (multiplication of two two-digits number). Through recursions, at any level $k, k = \log_2 n, n_k = 2^k \cdot m$, one would observe: - $A_k = A_{\text{high}_k} \cdot 10^{m_k} + A_{\text{low}_k}$ - $B_k = B_{\text{high}_k} \cdot 10^{m_k} + B_{\text{low}_k}$ The recursive call $hh_k, hl_k, lh_k, ll_k$ correctly computes the product of $A_k \times B_k$ til the base case. The combination of the products is proven through previous math steps, therefore, the algorithm is correct. > \[!question\] 1.4 > > Give a recurrence $T(n)$ for the runtime complexity of `BREAKSDOWNMULTIPLY(A, B)` Explain each term in the recurrence. > > Draw a recurrence tree for $T(n)$ and use this recurrence tree to solve the recurrence $T(n)$ by proving that $T(n) = \Theta (f(n))$ for some function $f(n)$ > > What is the runtime complexity of `BREAKSDOWNMULTIPLY(A, B)`? Do you expect this algorithm to be faster than the pen-and-paper multiplication algorithm? > _Hint: Feel free to assume that $n = 2^k, k \in \mathbb{N}$. Feel free to assume that we can add two $v$-digit number in $\Theta(v)$ (e.g., using `ADD`) and that we can multiply a $v$-digit number with $10^w$ in $\Theta (v+w)$._ For two $n$ digits number $A$ and $B$, the recurrent $T(n)$ is: $$ T(n) = \begin{cases} \Theta(1) & \text{if } n = 1 \\\ 4T(n/2) + \Theta(n) & \text{if } n > 1 \end{cases} $$ - The base case when $n=1$ is $\Theta(1)$, as it only performs a single digit multiplication, without no recursive calls. - The recursive case when $n>1$ performs 4 recursive calls, each with $n/2$ digits, each on number half the size of original input (since $n=2m$), hence $4T(n/2)$. - $\Theta(n)$ is the linear time complexity adding the products of the recursive calls, per our assumption that we can multiply a $v$-digit number with $10^w$ in $\Theta(v+w)$. The recurrence tree for $T(n)$ is: ```bash T(n) ├── T(n/2) │ ├── T(n/4) │ │ ├── T(n/8) │ │ │ ├── ... │ │ │ ... │ │ │ ├── ... │ │ │ └── ... │ │ ... │ │ └── T(n/8) │ ├── T(n/4) │ │ ├── ... │ │ ├── ... │ │ ├── ... │ │ └── ... │ ├── T(n/4) │ │ ├── ... │ │ ├── ... │ │ ├── ... │ │ └── ... │ └── T(n/4) │ ├── ... │ ├── ... │ ├── ... │ └── ... ├── T(n/2) │ ├── ... │ ├── ... │ ├── ... │ └── ... ├── T(n/2) │ ├── ... │ ├── ... │ ├── ... │ └── ... └── T(n/2) ├── ... ├── ... ├── ... └── ... ``` - The total number of nodes at depth $k$ is $4^k$, since each level of recursion calls the function four times. - Work done at level $k$ is $4^k \cdot n/2^k = 2^k \cdot n$, since work done per depth is $n$ times the number of nodes add that depth. - Depth of the tree is $\log_2 n$, since the input size is halved at each level. Therefore, one can solve for $T(n)$: $$ \begin{aligned} T(n) &= \sum_{k=0}^{\log_2(n)} 2^k \cdot n \\\ &= n \cdot \sum_{k=0}^{\log_2(n)} 2^k \\\ &= n \cdot \frac{2^{\log_2(n) + 1} - 1}{2 - 1} \\\ &= n \cdot (2n - 1) \\\ &= 2n^2 - n \\\ &= \Theta(n^2) \end{aligned} $$ Thus the runtime complexity of `BREAKSDOWNMULTIPLY(A, B)` is quadratic, $\Theta(n^2)$. From here, the algorithm is the same as the pen-and-paper multiplication algorithm, which also takes $\Theta(n^2)$ time. > \[!question\] 1.5 > > One can observe > > $$ > (A_{\text{high}} + A_{\text{low}}) \times (B_{\text{high}} + B_{\text{low}}) = A_{\text{high}} \times B_{\text{high}} + A_{\text{high}} \times B_{\text{low}} + A_{\text{low}} \times B_{\text{high}} + A_{\text{low}} \times B_{\text{low}} > $$ > > Hence by rearranging terms, one can conclude that > > $$ > A_{\text{high}} \times B_{\text{low}} + A_{\text{low}} \times B_{\text{high}} = (A_{\text{high}} + A_{\text{low}}) \times (B_{\text{high}} + B_{\text{low}}) - A_{\text{high}} \times B_{\text{high}} - A_{\text{low}} \times B_{\text{low}} > $$ > > Based on conclusion above, $A \times B$ can be seen as: > > $$ > \begin{aligned} > A \times B &= (A_{\text{high}} \cdot 10^m + A_{\text{low}}) \times (B_{\text{high}} \cdot 10^m + B_{\text{low}}) \\ > &= A_{\text{high}} \times B_{\text{high}} \cdot 10^{2m} + A_{\text{high}} \times B_{\text{low}} \cdot 10^m + A_{\text{low}} \times B_{\text{high}} \cdot 10^m + A_{\text{low}} \times B_{\text{low}} \\ > &= A_{\text{high}} \times B_{\text{high}} \cdot 10^{2m} + (A_{\text{high}} \times B_{\text{low}} + A_{\text{low}} \times B_{\text{high}}) \cdot 10^m + A_{\text{low}} \times B_{\text{low}} \\ > &= A_{\text{high}} \times B_{\text{high}} \cdot 10^{2m} + \left(\left((A_{\text{high}} + A_{\text{low}}) \times (B_{\text{high}} + B_{\text{low}})\right) - \left(A_{\text{high}} \times B_{\text{high}}\right) - \left(A_{\text{low}} \times B_{\text{low}}\right)\right) \cdot 10^m + A_{\text{low}} \times B_{\text{low}}. > \end{aligned} > $$ > > The final rewritten form of $A \times B$ only requires three multiplication terms, namely $A_{\text{high}} \times B_{\text{high}}, A_{\text{low}} \times B_{\text{low}}, (A_{\text{high}} + A_{\text{low}}) \times (B_{\text{high}} + B_{\text{low}})$ > > Use the observation to construct a recursive multiplication `SMARTMATHSMULTIPLY(A, B)` that only perform three recursive multiplications. Argue why `SMARTMATHSMULTIPLY(A, B)` is correct.

"\\begin{algorithm}\n\\caption{SMARTMATHSMULTIPLY(A, B)}\n\\begin{algorithmic}\n\\INPUT $A \\text{ and } B \\text{ have } n=2m \\text{ digits}$\n\\IF{$n = 1$}\n \\RETURN $a_{1} \\times b_{1}$\n\\ELSE\n \\STATE $hh \\coloneqq \\text{SMARTMATHSMULTIPLY}(A_{\\text{high}}, B_{\\text{high}})$\n \\STATE $ll \\coloneqq \\text{SMARTMATHSMULTIPLY}(A_{\\text{low}}, B_{\\text{low}})$\n \\STATE $mid \\coloneqq \\text{SMARTMATHSMULTIPLY}(A_{\\text{high}} + A_{\\text{low}}, B_{\\text{high}} + B_{\\text{low}})$\n \\RETURN $hh \\cdot 10^{2m} + (mid - hh - ll) \\cdot 10^m + ll$\n\\ENDIF\n\\RETURN $A \\times B$\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 22 SMARTMATHSMULTIPLY(A, B)

Input: $A \text{ and } B \text{ have } n=2m \text{ digits}$

1:if $n = 1$ then

2:return $a_{1} \times b_{1}$

3:else

4: $hh \coloneqq \text{SMARTMATHSMULTIPLY}(A_{\text{high}}, B_{\text{high}})$

5: $ll \coloneqq \text{SMARTMATHSMULTIPLY}(A_{\text{low}}, B_{\text{low}})$

6: $mid \coloneqq \text{SMARTMATHSMULTIPLY}(A_{\text{high}} + A_{\text{low}}, B_{\text{high}} + B_{\text{low}})$

7:return $hh \cdot 10^{2m} + (mid - hh - ll) \cdot 10^m + ll$

8:end if

9:return $A \times B$

The proposed `SMARTMATHSMULTIPLY(A, B)` is _the basis_ of Karatsuba’s algorithm. Base case: $n=1$, which implies $A \times B$ are correct (multiplication of two single digit number). Assume that `SMARTMATHSMULTIPLY(A, B)` correctly computes the product of $A \times B$ for $A, B$ with lest than $n$ digits. The following invariants hold per recursive call: - $A = A_{\text{high}} \cdot 10^m + A_{\text{low}} \land B = B_{\text{high} \cdot 10^m + B_{\text{low}}}$ where $m = \frac{n}{2}$ (true from problem statement and $n=2^k$) - recursive call computes $P_{1}, P_{2}, P_{3}$ correctly, where $P_{1} = A_{\text{high}} \times B_{\text{high}}, P_{2} = A_{\text{low}} \times B_{\text{low}}, P_{3} = (A_{\text{high}} + A_{\text{low}}) \times (B_{\text{high}} + B_{\text{low}})$ for numbers fewer than $n$ digits (from induction hypothesis) - combination invariants: $P_{4} = P_{3}-P_{2}-P_{1} \land A \times B = P_{1} \cdot 10^{2m} + P_{4} \cdot 10^m + P_{2}$ (true from previous statement) Thus, the algorithm is correct. > \[!question\] 1.6 > > Give a recurrence $T(n)$ for the runtime complexity of `SMARTMATHSMULTIPLY(A, B)` Explain each term in the recurrence. > > Solve the recurrence $T(n)$ by proving that $T(n) = \Theta (f(n))$ for some function $f(n)$. Use any methods that you find comfortable with. > > What is the runtime complexity of `SMARTMATHSMULTIPLY(A, B)`? Do you expect this algorithm to be faster than the pen-and-paper multiplication algorithm? > _Hint: Feel free to assume that $n = 2^k, k \in \mathbb{N}$. Feel free to assume that we can add two $v$-digit number in $\Theta(v)$ (e.g., using `ADD`) and that we can multiply a $v$-digit number with $10^w$ in $\Theta (v+w)$._ For two $n$ digits number $A$ and $B$, the recurrent $T(n)$ is: $$ T(n) = \begin{cases} \Theta(1) & \text{if } n = 1 \\\ 3T(n/2) + \Theta(n) & \text{if } n > 1 \end{cases} $$ - The base case when $n=1$ is $\Theta(1)$, as it only performs a single digit multiplication, without no recursive calls. - The recursive case when $n>1$ performs 3 recursive calls, each with $n/2$ digits, each on number half the size of original input (since $n=2m$), hence $3T(n/2)$. - $\Theta(n)$ is the linear time complexity adding the products of the recursive calls, per our assumption that we can multiply a $v$-digit number with $10^w$ in $\Theta(v+w)$. Using `Master Theorem`, we can solve for $T(n)$, with $a=3, b=2, f(n)=\Theta (n) = n^{\log_2 3}$. > The master theorem states that if $f(N) = \Theta (N^{\log_b a} \log^{k}(N))$, with $k>0$, then $T(N) = \Theta (N^{\log_b a} \log^{k+1} N)$. Thus $T(n) = \Theta(n^{\log_2 3} \log(n)) = \Theta (n^{\log_2 3})$ > \[!tip\] Runtime complexity of `SMARTMATHSMULTIPLY(A, B)` > `\Theta(n^{\log_2 3}) \approx \Theta (n^1.585)` > > This algorithm is expected to be faster than the pen-and-paper multiplication algorithm, which also takes $\Theta(n^2)$ time.