Integer - Multiplication (Product)

Third grade School

<MATH> \begin{array}{rrrrr} & & 1 & 2 & 3 \\ & & 4 & 5 & 6 \\ \hline & & 7 & 3 & 8 \\ & 6 & 1 & 5 & - \\ 4 & 9 & 2 & - & - \\ \hline 5 & 6 & 0 & 8 & 8 \end{array} </MATH> To form a partial products, we need

• <math>n</math> operations for the multiplications. We multiplies 3 times each of the numbers 1, 2, and 3.
• <math>n</math> operations (at most) for the carries. Carries are at most twice times the number of digits in the first number.

We need then at most <math>2n</math> operations.

If we have <math>n</math> partial products (The number of digits in the second number), the total is at most <math>2n^2</math> operations to form all of them.

The final addition requires at most a comparable number of operations. <math>2n^2</math> .

The number of operations for this Algorithm performs roughly <math>4n^2</math> It's quadratic function in the input of length n.

Karatsuba Multiplication

A Recursive Algorithm

Assumption: n is an even integer. If n is an odd integer, you can apply this exact same recursive approach to integer multiplication. If n was 9, the input numbers would be decomposed into a first five digits and a later four digits and you would proceed in exactly the same way.

<MATH> \begin{array}{rrl} x & = & 10^{n/2} a + b \\ y & = & 10^{n/2} c + d \end{array} </MATH> where:

• a,b,c,d are <math>n/2</math> digit numbers. example: a=56, b=78, c=12, d=34

Then

<MATH> \begin{array}{rrl} x.y & = &(10^{n/2} a + b)(10^{n/2} c + d) \\ & = & 10^{n} ac + 10^{n/2}(ad+bc) + bd \end{array} </MATH> Idea :

• recursively compute ac, ad, bc, bd,
  1. Recursively compute ac
  2. Recursively compute bd
  3. Recursively compute (a+b)(c+d) = ac + bd + ad + bc.
  4. Then Gauss’Trick: (3)–(1)–(2)= ad + bc

Recursivity base case: If the input (n) is sufficiently small (one digit), then compute the answer rather than recursing further.

• then compute <math>x.y</math>