CS3343/3341
 Analysis of Algorithms 
Weird Topic
   Fast Multiplication  
  Divide-and-Conquer   
  "Mental Arithmetic"   

Multiplication Faster Than O(n2): On this page we give a method of multiplication that is O(n1.585). All the examples on this page are presented in base 10, but for a normal binary machine, the algorithm should be dealing with bits, and instead of multiplying by a power of 10, we would be using shifting to multiply by powers of 2.

As a bonus, we get a way for a "calculating prodigy" to multiply 8-digit numbers in his head.

It turns out that even faster methods exist, up to O(n * log(n)), but we won't discuss them here.

Multiplication of 2-digit Numbers: As a first example, consider multiplication of 2-digit numbers, digit-at-a-time. Each 2-digit number is broken into two 1-digit numbers.

2-digit numbers:

a = a1 a0 = a1∙10 + a0
b = b1 b0 = b1∙10 + b0

We want:
c = a * b = (a1∙10 + a0) * (b1∙10 + b0)

Write:
c = c2 c1 c0 = c2∙100 + c1∙10 + c0
where
c2 = a1*b1
c0 = a0*b0
c1 = a1*b0 + a0*b1

But instead, we could write:
c1 = (a1 + a0) * (b1 + b0) - (c2 + c0)

This multiplies a and b, with only 3
low-level multiplications, instead of 4

Illustrating the Process: Here we are using 8-digit numbers which are each broken into two 4-digit numbers.

8-digit numbers:

c   =    a     *     b    =       c
      23456789 * 98765432 = 2316719898917848

Break up a and b into 4-digit pieces:

a   =   a1∙10e4 +   a0    =    a
       23450000 +  6789   = 23456789

b   =   b1∙10e4 +   b0    =    b
       98760000 +  5432   = 98765432

c = a * b = (a1∙10e4 + a0) * (b1∙10e4 + b0) =
   c2∙10e8 + c1∙10e4 + c0

c2 = a1  *  b1  =    c2
    2345 * 9876 = 23159220

c0 = a0  *  b0  =    c0
    6789 * 5432 = 36877848

Use the fancy method for c1:
c1 = (a1 + a0) * (b1 + b0) - (c2 + c0) =    c1
       9134   *   15308   -  60037068 = 79786204

c =  c2∙10e8     +    c1∙10e4   +    c0    =       c
2315922000000000 + 797862040000 + 36877848 = 2316719898917848

There is another arrangement of this scheme (described by D. Knuth):

"Curiously, this idea does not seem to have been discovered before 1962; none of the "calculating prodigies" who have become famous for their ability to multiply large numbers mentally have been reported to use any such method, although [the formula below] would seem to lead to a reasonably easy way to multiply eight-digit numbers in one's head."
Mental Arithmetic (the three dots are the three multiplies)

a ∙ b =
  (108+104)a1∙b1 + 104(a1-a0)∙(b0-b1) + (104+1)a0∙b0

In the example above, this would be:
23456789∙98765432 = 2316719898917848 =
  (108+104)2345∙9876 + 104(2345-6789)∙(5432-9876) + (104+1)6789∙5432 =
  (108+104)23159220 + 104((-4444)∙(-4444)) + (104+1)36877848 =
  108∙23159220 + 104∙23159220 + 104∙19749136 + 104∙36877848 + 36877848 =
  2315922000000000 + 231592200000 + 197491360000 + 368778480000 + 36877848 =
  2316719898917848

Asymptotic Results: An implementation can be faster for n as small as 8. Again, though, with a binary computer we would normally use bits rather than digits (because we can use shifting to multiply by a power of 2). In an implementation for multiplication of very large integers, you would switch to the hardware multiply for n = 32 bits. 

Recurrence normal:  T(n) = 4 T(n/2) + Θ(n)
   Master theorem: b = 2, a = 4, logb(a) = log2(4) = 2 > 1, so
   Case 1:  T(n) = Θ(nlogb(a)) = Θ(n2)

Recurrence special:  T(n) = 3 T(n/2) + Θ(n)
   Master theorem: b = 2, a = 3, logb(a) = log2(3) = 1.5849625 > 1, so
   Case 1:  T(n) = Θ(nlog2(3)) = Θ(n1.585)

Revision date: 2012-10-24. (Please use ISO 8601, the International Standard Date and Time Notation.)