There's a constraint that I as a civilian am missing. Could someone please put me out of my misery:
n.m (in integers) can be computed by starting with zero and adding m to it, n times. That's n operations. Errrrr cough , assuming that the computer can deal with an arbitrarily large n and m.
Numbers that exceed the machine's word size have a common representation whose length is O(lg N). So a simplistic upper bound for computing N×M would be O(min(N,M) × lg(N×M))
How much does each operation cost? Adding together two 5 digit numbers and two 5,000 digit numbers should be counted differently, don’t you agree? So perhaps we should count the number of single-digit operations required.
In that case, adding two five digit numbers will require 5 (or so) additions, and two 5,000 digit numbers will require 5,000 (or so) additions.
What about a 5,000 digit * 5,000 digit multiplication?
Just the very first “big” addition in your scheme will require 5,000 single-digit additions. But that result might now be 5,001 digits long (think of how 99+99 results in a 3 digit sum). Do it again, and if you have carries, it might be 5,002 digits long.
So you’ll have 5,000 + 5,001 + ... = 5000N + (1 + 2 + ... + N) operations. How many times does this repeat, that is, what is N? Well, however big your multiplier is! Your multiplier is around N = 10^5000. So you’ll need a total number of additions approximately equal to
5000 * 10^5000 + 1 + 2 + ... + 10^5000
And what is 1 + 2 + ... + N? It’s N(N+1)/2. So we have
5000 * 10^5000 + 10^5000*(10^5000 + 1) / 2
which we might as well estimate to be
(10^5000)^2.
That’s a _lot_ of operations. And that’s an _under_ estimate! Even grade school multiplication is a lot simpler (if you count single-digit multiplication to have a cost of 1): it only requires 5000^2 elementary operations.
The goal of these funny multiplication algorithms is to beat (number of digits)^2 single-digit operations. What the article shows is that of you have enough digits, you can do only
(number of digits) * (number of digits in the number of digits)
operations to do the multiplication, perhaps off by some fixed, constant factor.
Do it on paper using the method you learned in third grade. How many times above do you combine a single pair of digits? On the left it's 4 (0x0, 0x1, 1x0, and 1x1). Which is O[n^2] and n=2 above.
On the right it's 9 pairwise operations for the ones column plus 9 for the tens column (but it would usually be 10 if we had any carries) for a total of 18. A lot more than 4.
Oh but you say "the computer doesn't have to do those adds digit by digit. It can do all the digits in parallel." That's only true when the numbers fit into a register. If your numbers are not 64 bits wide but 64 thousand bits wide, the computer has to effectively do addition digit by digit. Which is why the left side above is quicker than the right, and the O[n logn] method in the article is better still.
n.m (in integers) can be computed by starting with zero and adding m to it, n times. That's n operations. Errrrr cough , assuming that the computer can deal with an arbitrarily large n and m.