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.
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
And what is 1 + 2 + ... + N? It’s N(N+1)/2. So we have which we might as well estimate to be 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
operations to do the multiplication, perhaps off by some fixed, constant factor.