Graph of results (Note the logarithmic axes)
In January 1999, I measured the program on a Sun SPARCstation 4 using g++ with optimization level 4. (It was an antiquated computer even at that time.) The below results are the results for pairs of random n-digit numbers. (Yes, digits. I implemented it in decimal.) All times are in milliseconds,
| # digits | Karatsuba | grade school |
|---|---|---|
| 8 | 0.059923 | 0.063902 |
| 16 | 0.106360 | 0.121773 |
| 32 | 0.278862 | 0.414594 |
| 64 | 0.798085 | 1.481481 |
| 128 | 2.325581 | 5.780347 |
| 256 | 6.944444 | 22.727273 |
| 512 | 21.276596 | 88.333333 |
| 1024 | 63.750000 | 370.000000 |
| 2048 | 195.000000 | 1650.000000 |
More recently (November 2000), I compiled the program using g++ (highest optimization level) on a 700MHz Pentium III Linux box. (Here I set the KARAT_CUTOFF constant - the point at which the recursive Karatsuba function just does grade-school multiplication - to 16.) Results gained here indicate a significantly better algorithm only once gets to 64 digits. Again, all times are in milliseconds.
| # digits | Karatsuba | grade school |
|---|---|---|
| 8 | 0.002838 | 0.002703 |
| 16 | 0.006230 | 0.006141 |
| 32 | 0.016622 | 0.017437 |
| 64 | 0.048354 | 0.058411 |
| 128 | 0.140272 | 0.212314 |
| 256 | 0.437445 | 0.808407 |
| 512 | 1.317523 | 3.164557 |
| 1024 | 4.016064 | 12.048193 |
Of course, this begs the question: Why would one want to multiply 100-digit numbers with exact precision? One response is cryptographic applications: Some protocols (including RSA) involve many multiplications of keys with hundreds of digits. (Another application is to breaking mathematical records (largest prime, whatever), but it's not clear how practical this is.)