Alan Eliasen wrote: > Andrew Haley wrote: >> You give examples of the speedup for very large bignums, but you >> don't say the size of numbers at which your approach becomes faster >> than the current code. Of course any asymptotic improvement helps >> with numbers that are half a million decimal digits long, but >> where's the crossover? > > Good question. Like most Karatsuba and Toom-Cook > implementations, the optimal crossover point is vague, as it can > depend on the size of both operands, and the curves don't separate > fast at that point. If you look at the updated file (again, at > http://futureboy.us/temp/BigInteger.java ) you'll see the crossover > points: > > Thus, the first crossover for Karatsuba multiplication is at 50*32 > bits (1600 bits), or about 482 decimal digits. Toom-Cook at 2400 bits.
OK, that's a little more encouraging. The measures you posted before were for nubers about half a million decimal digits long, which is well into FFT multiplication territory. That we can see some improvement for ~ 500-digit numbers is good to see. > These crossovers are determined experimentally, of course, and > constants are chosen that work well for a variety of number forms and > operand combinations. These numbers were found to work well after a lot > of timing runs with a lot of different number sizes and forms. Of > course, it's possible that different thresholds can work better on > different architectures and VM settings. I'm not proposing we tune for > each architecture, but rather choose conservative crossover thresholds > which work well, which I believe these are. > > It generally isn't damaging if you're just "in the ballpark" when > setting your thresholds; the algorithms will still work fine, and > performance will still be very similar for most operands. Sure, that makes sense. Andrew.
