I have a homework question that asks the following:
Consider an algorithm for integer multiplication of two n -digit numbers where each number is split into three parts, each with $n / 3$ digits.
(a) Design such an algorithm and clearly explain how it works. You should explain how to multiply two n-digits integers using only six multiplications of the $n/3$ -digits numbers (instead of the straightforward nine).
(b) Determine the asymptotic running time of your algorithm
I have an answer, but I am not sure how correct it is, because I am very new to this. Could someone provide any advice on my answer below:
- Multiplication of n-digit by 1-digit has a time of O(n)
- Additions of 2n-digit by n-digit max has a time of O(n)
Total time = $nO(n) + nO(n) = 2nO(n) = O(n^2)$
Using Divide-and-Conquer:
$I =$ first number, $J=$ second number.
$I_h=$ the left half of the first number, $I_l=$ the right half of the first number.
$J_h, J_l$ are left and right half of second number.
$I\cdot J = [(I_h \cdot 2^{n/3}) + I_l] \cdot [(J_h x 2^{n/3}) + J_l]$
$= I_h \cdot J_h \cdot 2^{2n/3} + (I_l \cdot J_h + I_h \cdot J_l) \cdot 2^{n/3} + I_l \cdot J_l$
Does this satisfy the condition of six multiplications?
This will give me a $T(n) = 6T(n/2) + \Theta(n)$
The Master theorem gives me a result of $\Theta(n^2)$, is that correct?
Any mistakes you saw? I am honestly very shaky on this....