caption

Karatsuba’s Multiplication Trick Summarised in 1 Minute

Our standard algorithm for multiplication is not the fastest. Normally we multiply numbers by pairing up the digits, multiplying and adding up. Here we did 4 multiplications and in general, if the numbers have N digits, we have N*N pairs, so the total number of calculation steps is proportional to N². But in 1960 a student named Karatsuba found a faster algorithm that only uses 3 multiplications. His trick: By adding and multiplying out, he gets all 4 pairs in one sum. Then he computes the first and last digit and gets the middle digit by subtracting both from the sum. Despite the extra additions and subtractions, his runtime in general turns out to be proportional to N¹·⁵⁹, which is faster than our N²..

Leave a Reply