[dalke]

The Karatsuba algorithm page says "The Toom–Cook algorithm is a faster generalization of [the Karatsuba algorithm]]", and the Toom-Cook page links to the GMP document, which says:

"Toom-3 is asymptotically O(N^1.465), the exponent being log(5)/log(3), representing 5 recursive multiplies of 1/3 the original size each. This is an improvement over Karatsuba at O(N^1.585), though Toom does more work in the evaluation and interpolation and so it only realizes its advantage above a certain size."

Reading http://gmplib.org/manual/Multiplication-Algorithms.html, it appears that GMP implements: Karatsuba, Toom-3, Toom-4, Toom-6.5, Toom-8.5, FFT -based multiplication methods, which I interpret to mean that Toom-Cook is useful for ranges between where Karatsuba and FFT are most useful.

[kurlberg]

The answer to "Who's fastest when?" is a bit complicated - you can find a nice picture of the "champion algorithm" for different ranges at

http://gmplib.org/devel/log.i7.1024.png

More context and explanation can be found at: http://gmplib.org/devel/

Short summary: Toom-Cook is nice because you have many parameters to play with.

[dalke]

Pretty! Since I never manually multiply n>10 digit numbers together, it looks like I can keep doing that the schoolbook way.

[jheriko]

i still don't consider this news - i stumbled upon this the first time i had to implement multi-precision multiplication - its a standard technique. if someone posts linked list wiki article is that news because for some situations arrays are faster and in others trees are?

[dalke]

I also don't consider it news. Unfortunately, it's hard to tell if something is news to everyone, news to most people on HN, and news to a few people.

For me this falls into the category of "new to me, but it's old news if you're in the field."