Can Karatsuba help professor Arthur Benjamin?

The mathemagic of Arthur Benjamin#

Arthur Benjamin performs a spectacular trick: he multiplies two numbers in his head! By performing his trick out loud, he also lets us in on his secret: there are no secrets. He is very good at mental arithmetic. His method is a straightforward application of the elementary school identity:

$$(a + b)(c+d) = ac + ad + bc+ bd.$$

A careful examination of his videos reveals that he is using a shortcut. He does multiply two different 2-digit numbers. However, when he does the trick for 3,4, or 5-digit numbers, he only squares them. Multiplying two unequal 4-digit numbers is quite hard using his method. He has to split each number into two 2-digit numbers and performs four multiplications of two 2-digit numbers. The final answer will be produced by doing shifts and additions. By choosing to square, he can cut the number of calculations drastically.

Let’s carefully examine his method and see how we can tackle the problem of multiplying two 4-digit numbers in our heads. Let’s first look at the general representation. We are given a $d$-digit number, $a$, by specifying its digits $a_{d-1}, \ldots, a_0$. We let $\mathbf{a} = (a_{d-1}, \ldots, a_0)$ denote its representation and $a$ denote its value. Thus, we have the following:

$$a = \sum_{i = 0}^{d-1} 10^i a_i.$$

Typically, when writing a concrete number, we dispense with parentheses and commas. We write $9738$ instead of $(9,7,3,8)$. A 4-digit number $\mathbf{a} = (a_3, a_2, a_1, a_0)$ can be split into two 2-digit numbers, by setting $\mathbf{a}_h = (a_3, a_2),$ and $\mathbf{a}_l = (a_1, a_0),$ where $\mathbf{a}_h$ consists of the higher two digits and $\mathbf{a}_l$ consists of the lower two digits. Hence $a = 10^2a_h + a_l$. For example, if $\mathbf{a} = 9738$ then $\mathbf{a}_h = 97$ and $\mathbf{a}_l = 38$. Similarly, if $\mathbf{b} = 4737$ then $\mathbf{b}_h = 47$ and $\mathbf{b}_l = 37$. The product of two numbers $a$ and $b$ is given by:

$$a b = 10^4 a_h b_h + 10^2(a_h b_l + a_l b_h) + a_l b_l. \:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\: (1)$$

In our example, the product will be as follows:

$$9738 \times 4737 = 10^4 (97 \times 47) + 10^2 (97 \times 37 + 38 \times 47) + 38 \times 37.$$

To perform this calculation, we’ll compute $a_h b_h, a_h b_l , a_l b_h,$ and $a_l b_l.$ Now we can calculate $ab$ by performing some shifts (which are multiplications by powers of ten) and additions. For this trick to work, we must be able to multiply two 2-digit numbers in our heads and be good at shifting and adding.

Let’s see what happens if we square a number, as Prof. Benjamin does. To compute $a^2$ we have,

$$a ^2 = 10^4 a_h^2 + 200 a_h a_l + a_l^2.$$

In our example,

$$9738^2 = 10^4\times 97^2 + 200 (97\times 38) + 38^2.$$

This reduces our work considerably. We have performed three multiplications instead of four. But it is better than that: two of the multiplications are squarings. It seems that Prof. Benjamin has memorized all 2-digit squares. Hence, the only difficult part for him is to do a 2-digit multiplication; that is, compute $97 \times 38.$

We’ll have to develop the following skills to perform the trick:

1. Memorize the squares of all $2$-digit numbers.
2. Multiply two $2$-digit numbers quickly.
3. Be able to double a $4$-digit number quickly.
4. Perform some shifts and additions quickly.

Many of our friends may agree that Step 1 is certainly doable. There are only 100 squares to remember and there are many bright people who don’t find this task very challenging. It is fun to read another paper by Prof. Benjamin on squaring and even try to develop our own shortcuts to acquire this skill.

Step 2 is the hardest. Brute force memorization is nearly impossible as the number of 2-digit pairs is 10,000. Therefore, it is wise to compute this step. Prof. Benjamin is very good at this; in fact, he can perform a multiplication of a 2-digit number with a 3-digit number in his head. This allows him to pull off his spectacular trick of squaring a 5-digit number in his head.

Karatsuba and the power of negative thinking#

We learn to multiply numbers in elementary school. The algorithm that we use is ancient and was widely used by Sumerians and Egyptians for at least four thousand years. Karatsuba suggests that “there is every reason to believe that it has existed for at least six millennia.”

To multiply a number $a$ with $b$ we multiply $a$ with each digit of $b$ thereby calculating a row of our computation. Each row is appropriately shifted by adding zeros. The task is completed by adding the rows. The amount of work to compute a row is proportional to the number of digits in $a$. Hence the total amount of work just to compute the rows is equal to the number of digits in $a$ times the number of digits in $b$. If both $a$ and $b$ are $n$-digit numbers then the total work required is (at least) proportional to $n^2$.

Some variations are used in different cultures to teach this algorithm. However, none of these variations reduces $\Theta(n^2)$ work. They essentially make it easier for children to learn the method and indicate some useful shortcuts.

A possible approach to find a faster algorithm is to use the divide and conquer paradigm. Suppose $n$ is even and we wish to multiply two $n$-digit numbers $a$ and $b$. Let $a_h, a_l$ (respectively $b_h,b_l$) be the numbers formed by taking $\frac{n}{2}$ high digits and $\frac{n}{2}$ low digits of $a$ (respectively $b$). A generalization of Equation (1) gives us:

$$ab = 10^n a_h b_h + 10^{\frac{n}{2}} (a_hb_l + a_lb_h) + a_lb_l.$$

This leads to a recursive divide-and-conquer algorithm. This equation converts the problem of multiplying two $n$-digit numbers to four problems of multiplying two $\frac{n}{2}$-digit numbers. Once the four subproblems have been solved the required value is computed by doing some shifts and additions. These shifts and additions are easier as they require $O(n)$ work. Unfortunately, this algorithm is no better than the classical method for multiplying. Multiplying two $n$-digit numbers this way also leads to an $\Theta(n^2)$ algorithm. Our first attempt to improve the classical algorithm is a failure.

Since all known algorithms for multiplication required $\Theta(n^2)$ time, the great mathematician Andrey Kolmogorov suggested in 1956, that mathematicians try to prove that an improved algorithm is impossible. His $n^2$-conjecture was perhaps based on the idea that “if a more economical method existed, it would have been already found”. After all, 6000 years have produced many brilliant minds.

Karatsuba, a 23-year old student, heard about the Kolmogorov $n^2$-conjecture from him, at a conference in Moscow State University in 1960. He decided to try exactly the opposite and attempted to find a faster algorithm! Within a week he showed Kolmogorov that a fundamentally faster algorithm was possible.

Karatsuba’s main idea is to somehow reduce the number of subproblems. He realized that if he uses subtractions then it is possible. Karatsuba computes $a_hb_h$, $a_l b_l$ and, the Karatsuba quantity,

$$K=(a_h+a_l)(b_h+b_l).$$

Computing $K$ requires us to add the high digits of $a$ to its lower digits (and the same for $b$). This may seem very unusual (and it certainly is) as we add the high and low digits of one number without looking at the digits of the other number!

Observe that,

$$K = a_hb_h + a_lb_h + a_hb_l + a_lb_l$$

and to our delight we realize that $a_hb_l + a_lb_h = K - a_h b_h - a_l b_l$ and therefore, we have

$$ab = 10^n a_h b_h +10^{\frac{n}{2}}(K - a_hb_h - a_lb_l) + a_l b_l.\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\: (2)$$

Thus the problem of multiplying two $n$-digit numbers has been converted to the problem of computing $a_hb_h, a_l b_l$ and $K$: only three smaller multiplications involving numbers (approximately) half the size. The product $ab$ can now be calculated by performing some subtractions, additions, and shifts.

Equation (2) can be repeated to amplify these dividends. At the second level of recursion there are only $9$ subproblems instead of $16$, at the third level there are only $27$ subproblems instead of $64$ and so on. Hence two $2^k$-digit numbers can be multiplied by doing $\Theta(3^k )$ operations instead of $\Theta(4^k)$ operations used by the classical method. Only $\Theta(n^{\log_2 3})$ steps are needed for multiplying two $n$-digit numbers. This is considerably faster than $\Theta(n^2)$ steps, needed for the classical method, as $\log_2 3 \approx 1.58.$

Karatsuba’s idea is truly revolutionary. His audacity as a 23-year old student to try exactly the opposite of what a legend had suggested, coupled with his use of subtraction is what we call “negative thinking.” All students should practice Karatsuba’s approach: mathematics and science progress by challenging the expert opinion.

Here, we do want to emphasize that denying a mathematical theorem, whose clear proof is available, or denying a well-established scientific theory without any evidence is not only unproductive but detrimental for the mental health of students.

In a week’s work, Karatsuba had improved upon the classical method that had reigned for thousands of years. Not only that, he had broken a psychological barrier. He showed the mathematical world that the problem of multiplying two $n$-digit numbers is a fertile area of research.

Initially, Kolmogorov was “agitated” at Karistuba’s discovery. But, mathematical truths are undeniable and soon Kolmogorov started lecturing about Karatsuba’s method and popularized it. After a couple of years, Karatsuba received a reprint of a paper he had never written! The paper contained his method and gave full credit to him. It also contained a result of another mathematician Ofman. The only authors of the paper were Karatsuba and Ofman, with proper credit given to each respective author -Kolmogorov’s name did not appear as an author.

The story of Karatsuba and Kolmogorov is extremely moving in today’s competitive world. Kolmogorov must have realized that Karatsuba had changed the course of history on a fundamental problem like multiplication. Despite his initial agitation, he acted conscientiously as a great promoter of mathematics. This story is a timeless tale of a young mathematician teaching a legend and the legend accepting to learn.

Karatsuba’s idea can be generalized to obtain an $O(n^{1+\epsilon})$-time algorithm for any $\epsilon > 0.$ The mathematical community gained confidence and another breakthrough lead to the development of an $O(n \log n \log \log n)$ algorithm that uses the Fourier Transform. More improvements followed leading to an algorithm that requires $O( 4^{\log_* n}n \log n )$ time by Harvey and van der Hoeven.

$\log_* n$ is the inverse of the tower function, $T (k)$, which is defined as: $T(0) = 1$ and $T(k) = 2^{T(k-1)}$. $\log_* n$ is the smallest $k$ such that $T(k) \geq n$.

Recently, they have developed an $O(n \log n)$-algorithm. Many computer scientists believe that we have reached the ultimate time complexity for this problem.

Karatsuba’s method and multiplying in the head#

Karatsuba’s method requires us to perform subtractions. Most people are far more comfortable with adding numbers than they are with subtracting them. This bias does not have a sound scientific basis: algorithms for subtractions are very similar to those for adding numbers. Those who are familiar with 2’s complement know that computers perform addition and subtraction using the same hardware. Thus, learning to subtract quickly is as easy as learning to add: we just have to practice. With this observation in mind, we apply Karatsuba’s method to the problem of squaring 4-digit number $a$ in our head. The Karatsuba quantity is given by

$$K = (a_h +a_l)^2 =a_h^2 +2a_ha_l +a_l^2$$

and we have,

$$a^2 = 10^4 a_h^2 + 10^2 (K - a_h^2 - a_l^2) + a_l^2.$$

Look at what we have achieved: we have dispensed with the problem of multiplying altogether! We have to compute $a_h^2,a_l^2,$ and the Karatsuba quantity which itself is a square. So, what are the skills needed to pull off this trick?

1. Square $a_l$ and $a_h$.
2. Compute the Karatsuba quantity by squaring the sum of $a_h$ and $a_l$.
3. Perform some subtractions, shifts, and additions.

This method has a slight advantage of dispensing with the doubling also. Now, $a_h$ and $a_l$ are only 2-digit numbers for us. However, the Karatsuba quantity is a sum of two 2-digit numbers and can be as large as 198. So, we will have to memorize the squares of numbers up to $198$. That’s a bummer! Can we reduce the work and not overload ourselves? The answer is yes. Let us define the modified Karatsuba quantity, $K_m$, by squaring the difference of $a_h$ and $a_l$. We have,

$$K_m = (a_h - a_l)^2 = (a_l - a_h)^2 = |a_h - a_l|^2 = a_h^2 - 2 a_h a_l + a_l^2.$$

We now have a lovely equation:

$$a^2 = 10^4 a_h^2 + 10^2 (a_h^2 + a_l^2 - K_m) + a_l^2.$$

We can base our method on this equation and the skills needed to perform a 4-digit squaring in our head are:

1. Memorize the squares of all 2-digit numbers.
2. Compute $a_h^2, a_l^2,$ and $K_m = |a_h - a_l|^2.$
3. Perform some subtractions, shifts, and additions.

Let’s assume we have all the 2-digit squares memorized and work out a concrete example by squaring $a = 9738$. We have $a_h = 97, a_l = 38,$ and $K_m = 97-38 = 59.$ Now we recall their squares from the memory.

From these three squares we compute:

The final answer is computed by adding these quantities with appropriate shifts:

We are fairly confident that many people are capable of doing this feat by using the Karatsuba shortcut. In fact, we would not be surprised to see Prof. Benjamin square a 6-digit number in his head. He seems to remember (or compute them fast enough to create that impression) all the squares of 3-digit numbers. With the Karatsuba’s trick at his disposal, it would be interesting to see what he can achieve. Perhaps, the only reason we might not see Prof. Benjamin squaring a 7 or 8-digit number in his head is because, he is involved in doing other work.

Multiplication vs. squaring#

An interesting question arises by studying the problem above. Is it strictly easier to square an $n$-digit number than multiply two arbitrary $n$-digit numbers? After all, using Karatsuba’s method, we were able to reduce the work considerably. Yet, the answer in general (or for large numbers) is no. Observe that:

$$ab = \frac{(a+b)^2 - (a-b)^2}{4}.\: \: \: \:\: \: \: \:\: \: \: \:\: \: \: \: (3)$$

This equation tells us that if we could develop a fast method for squaring, then it can be used to multiply two different numbers fast also. Equation (3) serves to prove a negative fact: the seemingly simpler task of squaring is at least as hard as multiplying two different numbers.

Despite this, Equation (3) has a positive application in mathemagic. Suppose Prof. Benjamin decides to multiply two arbitrary 3-digit numbers. He can compute $(a-b)^2$, which is a squaring of a 3-digit number and he is very good at it. He also has to compute $(a+b)^2$, which might be a 4-digit number. Although he is also capable of squaring a 4-digit number with some effort, we note that this 4-digit number is at most $1998$. This fact can allow him to speed up that calculation too. He will have to subtract and then divide the answer by $4$. We believe with a little practice he can accomplish this feat as well.

Conclusion#

This blog highlighted how Karatsuba’s method reduces so much effort in squaring a number in the head. It will be interesting to see what improvements this approach and other similar observations bring to mathemagic. We can only wait and see what new feats the future mathemagicians can accomplish.