You learned how to multiply numbers in school, using a simple
quadratic time algorithm that I'll call the "standard grade-school"
multiplication algorithm.  (We say that it's quadratic time because
it takes O(n^2) time to multiply two n-digit numerals.)

In fact, multiplication can be done much faster, although the faster
algorithms are mostly harder to understand.  Asymptotically, how much
time do you think it really takes to multiply two n-digit numerals?

Suppose that X and Y are numbers written in base b with at most 2n digits
each.  Then we can write X = A + B*b^n and Y = C + D*b^n, where A, B, C,
and D can each be written with at most n digits.  Now, note that

X*Y = A*C*b^(2n) + (A*D + B*C)*b^n + B*D.

Note also that n-digit numerals can be added in O(n) time.

Let T(n) be the time required to multiply two n-digit numerals.  Using
the above equation, we get the recurrence:

T(2n) <= 4*T(n) + O(n)

Which gives us that T(n) = O(n^2).   But we knew this already, so we've
gained nothing!

Let's consider the following game.  Suppose you know how to add and
subtract very quickly, but never learned the multiplication table.  A
friend offers to help you over the telephone, but it will cost you $1
for every multiplication fact he gives you.  How do you multiply two
2-digit numbers at minimum cost?

For example, suppose that you are supposed to multiply 95 by 36.  Using
the standard grade school method, you would have to ask your friend the
following multiplication problems: 9*3, 9*6, 5*3, and 5*6, at a cost of $4.

But you can do it for only $3 as follows:  Compute 9 - 5 = 4, and 6 - 3 = 3.
(Remember, your'e a whiz at subtraction.)  Then obtain the following number
facts from your friend:  9*3 = 27, 4*3 = 12, and 5*6 = 30.  Then do the
following addition problem.  (A, B are the digits of the first number,
and C, D are the digits of the second number.)

 27	product of the first digits (A*C)
  27	product of the first digits (A*C)
  12    (A-B)*(D-C)
  30	product of the second digits (B*D)
   30	product of the second digits (B*D)
 ----
 3420

Note that the answer is 95*36.

We will now show how to multiply n-digit numbers at cost O(n^{log_3(2)}),
by extending this algorithm.  (Note that log_3(2) is less than 2.)

 ----------------------

An even faster method of multiplication uses the Fast Fourier Transform.
See: http://www.math.ubc.ca/~cass/programs/fft.html