Click the link below the picture
.
Elementary school students might memorize their times tables for single-digit numbers, but memorization won’t cut it when the teacher asks for three-digit multiplication. This requires an algorithm: students are taught to stack one number atop another and multiply each digit of the bottom number by each digit of the top one. For millennia, mathematicians believed this to be the fastest multiplication method, until a 23-year-old made a shocking discovery in 1960, which led to a mystery that remains unsolved to this day.
This mystery is critical to anyone who partakes in the digital world because multiplication is a foundational operation for computers. Encryption, robotics, artificial intelligence, audio processing, and pretty much everything else we task silicon chips with involves multiplication, sometimes of huge numbers many times over. At this scale, even a simple operation becomes a bottleneck, and any extra efficiency has global economic consequences.
To understand the nature of that bottleneck, observe how the grade-school algorithm handles growth. When you multiply two two-digit numbers, you perform four single-digit multiplications. If you bump that up to a three-digit pair of numbers, you do nine single-digit multiplications. The workload scales with the square of the number of digits (n2, where n is the number of digits in the numbers being multiplied). When analyzing an algorithm like this, computer scientists don’t measure speed in seconds, because that depends on the hardware.
Instead, they count the computational steps. They also ignore minor bookkeeping details, such as the time it takes to carry a one when multiplying. When numbers get large enough, those lower-level operations cease to matter, entirely eclipsed by the more intensive operations involved. Computer scientists denote the number of steps using what’s called Big O notation: the grade-school algorithm, for example, takes O(n2) steps, which is read as “order n squared.” Broadly speaking, if the numbers are twice as long, the algorithm takes four times as much computational work to execute. If the numbers are a thousand times as long, it takes a million (1,000 squared) times as much work.
Since antiquity, mathematicians have suspected that O(n2) was an inherent speed limit for multiplication. The celebrated Soviet math professor Andrey Kolmogorov posed the O(n2) speed limit as a formal conjecture and mentioned it during a 1960 seminar at Moscow State University. Whenever mathematicians propose a conjecture, they are planting a flag of sorts and waiting for others to either prove or disprove them. It took just a week for Anatoly Karatsuba, then a 23-year-old student in the audience, to return and prove Kolmogorov wrong. Kolmogorov was stunned. The result was published in the prestigious Proceedings of the USSR Academy of Sciences, but amusingly, Karatsuba didn’t write it. Kolmogorov wrote the formal proof himself and submitted it for publication with Karatsuba listed as the lead author. Karatsuba only found out about the paper when he received the reprints in the mail.
Karatsuba’s genius was realizing that you can trade expensive, time-consuming multiplications for cheap, fast additions. Adding two n-digit numbers takes only O(n) time because it entails a single sweep through the digits rather than a complete sweep through the top number for every digit of the bottom number, as in multiplication. To see how Karatsuba traded multiplication for addition, let’s look at a small example. The method would be overly complicated for such a simple problem, but it saves a meaningful amount of time when numbers get larger.
First, we split both numbers into their tens and ones digits. Assign a = 1 and b = 2 (for 12), and c = 3 and d = 4 (for 34). Algebraically, we can rewrite 12 × 34 as (10a + b) × (10c + d).
Expanding this gives 100(ac) + 10(ad + bc) + (bd).
To solve the equation in the traditional way, one must perform four distinct multiplications: ac = 3, ad = 4, bc = 6 and bd = 8, which is exactly what the grade-school stacking method entails. (Note that we don’t count the multiplications by 100 or by 10 because those only involve plopping zeroes at the ends of numbers.) Karatsuba noticed a brilliant algebraic trick. Once you compute the first and last terms, ac and bd, you can figure out that pesky middle term (ad + bc) with one more multiplication step rather than two. You don’t need to calculate ad and bc individually:
(ad + bc) = ((a + b) × (c + d)) – ac – bd,
Or with our concrete numbers:
((1 × 4) + (2 × 3)) = ((1 + 2) × (3 + 4)) – 3 – 8 = 10.
Pause to notice the weirdness in the equation above. It suggests that to multiply 12 × 34 quickly, you should add the 1 and the 2 in 12 and the 3 and the 4 in 34. This is hardly a natural thing to do. No wonder it took so long for someone to figure it out. It ends up reducing the workload, however: because we’ve already computed ac and bd, the right-hand side only contains one more multiplication, plus some additions and subtractions.
.
Justin Lewis/Getty Images
.
.
Click the link below for the complete article:
.
__________________________________________
Leave a Reply