On Thu, 03 Mar 2011 22:23:11 -0800 "Jeffrey Lee Hellrung, Jr." <jhellrung@ucla.edu> wrote:
[...] They only become faster for *really* large numbers, much larger than I generally work with -- on the order of tens of thousands of bits, if I remember correctly. For the more usual case of 4Kbit numbers at most, they have noticeably worse performance than the algorithm that's in there now. [...]
The wikipedia article on Karatsuba's method suggests a switch from the grade-school algorithm to Karatsuba at around 320 to 640 bits:
Curious. That's not my experience, though the implementation I was trying to get working may well have been buggy.
I don't consider an implementation of Karatsuba's method or any other asymptotically faster method to be necessary at present, but it might be surprising at what point the asymptotically faster methods are practically faster.
It might indeed. I'll take another look at that when I have the time, though it might be a few weeks by the look of things. -- Chad Nelson Oak Circle Software, Inc. * * *