# Designing an algorithm for integer multiplication

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....

• 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})$ – gammatester Jan 24 '18 at 9:51
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://math.stackexchange.com/questions/2618424/designing-an-algorithm-for-integer-multiplication", "fetch_time": 1563789619000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2019-30/segments/1563195527907.70/warc/CC-MAIN-20190722092824-20190722114824-00225.warc.gz", "warc_record_offset": 474429318, "warc_record_length": 35076, "token_count": 532, "char_count": 1893, "score": 4.34375, "int_score": 4, "crawl": "CC-MAIN-2019-30", "snapshot_type": "longest", "language": "en", "language_score": 0.8291276097297668, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00057-of-00064.parquet"}