News for hackers. Stuff that matters.
Re:Toom–Cook multiplication by jheriko on Sunday September 23, 2012 @02:14PM (#4561586)
this is not exactly news... there are fft methods which are even better for very large numbers and karatsuba is adequate for the most common ranges.
Re:Toom–Cook multiplication by dalke on Sunday September 23, 2012 @02:28PM (#4561620)
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.

Re:Toom–Cook multiplication by kurlberg on Sunday September 23, 2012 @02:51PM (#4561693)
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.

Re:Toom–Cook multiplication by dalke on Monday September 24, 2012 @10:54AM (#4564957)
Pretty! Since I never manually multiply n>10 digit numbers together, it looks like I can keep doing that the schoolbook way.
Re:Toom–Cook multiplication by jheriko on Sunday September 23, 2012 @03:15PM (#4561761)
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?
Re:Toom–Cook multiplication by dalke on Sunday September 23, 2012 @03:34PM (#4561804)
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."