Toom–Cook multiplication • Hacker News Board

Re: Toom–Cook multiplication

#11

Post by wbhart » Sun, Sep 23, 2012, 11:31 PM UTC

carterschonwald wrote: post #10

For an even faster algorithm, http://arxiv.org/pdf/0801.1416v3.pdf and its prequel http://www.cse.psu.edu/~furer/Papers/mult.pdf both beat strassen.

I don't think this is terrible practical. Just as SSA wasn't efficient until the advent of modern computers and for integers of about millions of bits, so Furer's algorithm probably isn't efficient until integers are so large that their number of bits takes million of bits to write down. I won't say never, but it isn't going to be practical any century soon.

The multimodular version is likewise pretty useless in practice.

Re: Toom–Cook multiplication

#12

Post by dalke » Mon, Sep 24, 2012, 2:54 PM UTC

kurlberg wrote: post #4

dalke wrote: post #3

Earlier quoted context omitted.

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…

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.

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

#13

Post by carterschonwald » Thu, Sep 27, 2012, 9:04 PM UTC

wbhart wrote: post #11

carterschonwald wrote: post #10

For an even faster algorithm, http://arxiv.org/pdf/0801.1416v3.pdf and its prequel http://www.cse.psu.edu/~furer/Papers/mult.pdf both beat strassen.

I don't think this is terrible practical. Just as SSA wasn't efficient until the advent of modern computers and for integers of about millions of bits, so Furer's algorithm probably isn't efficient until integers are so large that their number of bits takes million of bits to write down. I won't say never, but it isn't going to be practical any century soon. The multimodular version is likewise pretty useless in prac…

in practice, certainly! The devil's in those constant factors etc :)