Let’s multiply in quasi-linear time!

Writing an integer A in base N is much like writing a polynomial:

A = a + bN + cN ² +… where a, b, c… are integers between 0 and N – 1. To add two n-digit numbers using the standard algorithm taught in elementary school, we perform n additions of single-digit numbers, together with, potentially, n additions for the carries. Computer tests confirm that, for very large numbers, the computation time is proportional to n. More precisely, it is bounded above by a constant times n, written O(n) ("big O of n"). Its complexity—the mathematical model we use for computation time—is linear.

With the standard algorithm taught in schools, multiplication is not linear but quadratic: its complexity is O(n²), since it requires n ² multiplications of single-digit numbers, followed by about n additions. Computer tests confirm that, for large numbers, the computation time is proportional to n ².

Computers have become so powerful that these differences can only be observed with numbers containing several thousand digits. But doubling the number of digits quadruples the computation time. With addition, it merely doubles the computation time; that is the crucial difference between linear and quadratic complexity.

Strassen’s algorithm ============================