1
$\begingroup$

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:

  1. Multiplication of n-digit by 1-digit has a time of O(n)
  2. 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....

$\endgroup$
  • $\begingroup$ You do not split into three parts! And normally multiplications by powers of $2$ do not count, they are simple shift operations. If you split into three parts you get basically $3\times 3=9$ shorter products. The key to reduce the complexity is to organize these $9$ products more efficiently. See en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication, the resulting complexity is $\Theta(n^{1.465})$ $\endgroup$ – gammatester Jan 24 '18 at 9:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.