In base 10, a number is written as a sum of powers of 10. Thus, 307 is written as 7 × 1 + 0 × 10 + 3 × 102. Similarly, in a base N (assumed to be "large"), an integer A is written as
A = a + b × N + c × N2 + ...
where a, b, c… are integers between 0 and N – 1. To multiply two n-digit numbers using the standard algorithm taught in elementary school, we perform n2 multiplications of single-digit numbers, followed by approximately n additions (which, in practice, is "negligible" compared with the preceding n2 multiplications). On a computer, the computation time is therefore proportional to n2. If you double the number of digits, you quadruple the computation time. Of course, this becomes "noticeable" only for numbers with several thousand digits.
This performance can, however, be improved considerably by means of the Fourier transform, whose definition involves complex numbers.
-
