Integer Multiplication

From Wikibooks, the open-content textbooks collection

The Karatsuba method for fast multiplication is sometimes also called Divide-and-Conquer method, although it is evident that the problems of fast calculation of the functions are very far from the problems involving searching. It is the same as if you make something using both your hands it doesn´t mean that you invent the binary system. That is why to consider a method of fast computation of a function and a method of searching as a similar processes is a great mistake.

The (2n)-digit decimal representation of the product x * y.

Note: The algorithm below works for any number base, e.g. binary, decimal, hexadecimal, etc. We use decimal simply for convenience.

The classical primary school algorithm for multiplication requires O( n^2 ) steps to multiply two n-digit numbers.

A step is regarded as a single operation involving two single digit numbers, e.g. 5+6, 3*4, etc.

In 1960, A.A. Karatsuba discovered an asymptotically faster algorithm for multiplying two numbers by inventing a method which was later called the divide-and-conquer method.

From this we also know that the result of multiplying x and y (i.e. z) is

The terms ( a*c ), ( a*d ), ( b*c ), and ( b*d ) are each products of

2 (n/2)-digit numbers.

Thus the expression for the multiplication of x and y in terms of the numbers a, b, c, and d tells us that:

   * Two single digit numbers can be multiplied immediately. (Recursive base: 1 step)
   * If n > 1 then the product of 2 n-digit numbers can be expressed in terms of 4 products of 2 
     (n/2)-digit numbers (Divide-and-Conquer stage)
   * To calculate the result of multiplying x and y given the four products returned involves only addition
     (can be done in O( n ) steps) and multiplying by a power of 10 (also can be done in O( n ) steps,
     since it only requires placing the appropriate number of 0s at the end of the number). 
     (Combine stage). 

(1-3) therefore describe a Divide-&amp-Conquer algorithm for multiplying two n-digit numbers represented in decimal. However,

Moderately difficult: How many steps does the resulting algorithm take to multiply two n-digit numbers?

Karatsuba discovered how the product of 2 n-digit numbers could be expressed in terms of three products each of 2 (n/2)-digit numbers - instead of the four products that a naive implementation of the Divide-and-Conquer schema above uses.

This saving is accomplished at the expense of slightly increasing the number of steps taken in the `combine stage' (Step 3) (although, this will still only use O( n ) operations).

Suppose we compute the following 3 products (of 2 (n/2)-digit numbers):

function Karatsuba (xunder, yunder : n-digit integer;

                          n : integer) 
                          return (2n)-digit integer is

a, b, c, d : (n/2)-digit integer U, V, W : n-digit integer; begin

  if n = 1 then
     return x(0)*y(0);
  else
     a := x(n-1) ... x(n/2);
     b := x(n/2-1) ... x(0);
     c := y(n-1) ... y(n/2);
     d := y(n/2-1) ... y(0);
     U := Karatsuba ( a, c, n/2 );
     V := Karatsuba ( b, d, n/2 );
     W := Karatsuba ( a+b, c+d, n/2 );
     return U*10^n + (W-U-V)*10^n/2 + V;
  end if;
end Karatsuba;