I thought it would be fun to program up Karatsuba's multiplication to see how it really performs compared to the grade-school method. Sometimes these techniques to optimize big-O bounds don't work well for reasonably sized problems; the best way to check is to run some experiments.
So I wrote an implementation of both grade-school and Karatsuba multiplication. I think my implementation is reasonably efficient. Check out the source. (No, really. I think it's a pretty solid implementation.)
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, measured on a Sun SPARCstation 4 using g++ with optimization level 4. (Not a great computer, but that's beside the point.)
| # 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 |
A graph is also available.
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.)
