Karatsuba measurements

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.)
# digitsKaratsubagrade school
80.0599230.063902
160.1063600.121773
320.2788620.414594
640.7980851.481481
1282.3255815.780347
2566.94444422.727273
51221.27659688.333333
102463.750000370.000000
2048195.0000001650.000000
What we see is that Karatsuba, properly implemented, beats grade-school multiplication even for 16-digit numbers. It is significantly better at 32 digits, and of course after that it just blows grade-school away.

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.)