Let's multiply!

One should think that elementary school taught us all that is to be known about basic operations on numbers: adding, substracting, multiplying and dviding. But there are still some surpises left! Here are three distinct ways to compute the product of two integers.

• The classical multiplication of the perfect pupil





• The lazy pupil's method (or Ancient egyptian multiplication)
 
The lazy man masters multiplication and division only by 2.



Instruction: In the left column take the half in each step; round-down if necessary. In the right column always double from one line to the next. Then erase all lines that begin with an even number (black) and add the remains on the right side (red).
 
 

• Method of Karatsuba (published in 1962)

Separate each factor on two halfs

and compute the following partial products:

The final result is obtained like this:

Remark
The up-shot of all this is the reduction of our computation to the products of one-digit numbers. On a computer the choice of an efficient algorithm can reduce considerably the time necessary to perform the program — when numbers with several milliards of digits are involved the saved time can be of the order of some days! Computing with such big numbers is not only interesting from a theoretical viewpoint, but has practical applications such as in cryptologie.
 
Exercices

1. Why does the lazy man's method work? Both factors play different roles; when you are given two numbers what casting do you propose?
2. With the help of the Karatsuba's multiplication compute the product 3116 x 1014. Explain in general, why the Karatsuba method works.
3. When you use the classical multiplication of the perfect pupil to compute the product of two n-digit integers, how many multiplications of one-digit numbers do you need to do?
4. By re-iteration of Karatsuba's method (separating the factors into, two, fours, eight, etc. parts) one constructs an slgorithm, the socalled Karatsuba-Algorithm. >When you apply it to the product of two n-digit intergers, how many single-digit products do you need? Compare the classical algorithm with the one of Karatsuba and show in particular, that the one of Karatsuba is much faster, being of the order .

Solutions
Here are the answers to this exercice in pdf-format.

Last but not least, a video about another multiplication method which produces a beautiful calligraphy — therefore we call it chinese multiplication!

The basic idea of the so-called chinese multiplication is this: a set of n parallel lines intersects another set of m parallel lines in nxm points. So there is nothing mysterious about that so-called chinese multiplication. Note that in the examples they always choose numbers with small digits like 112 or 2131 because with numbers like 89 or 897 there would be too many lines to draw!