At 07:31 PM 7/11/95 -0400, Ray Cromwell wrote:
However, it's only worthwhile for large numbers (>512 bits). At n=512, if your bigints are stored as polynomials with a 32-bit radix, then N=512/32=16. 16^1.5 = 64, 16 * lg(16) = 64 (so the FFT method and the Karatsuba method are equivalent for numbers of that size)
I conjecture that the constant factor is rather smaller for the Karatsuba method, so the turnover should be somewhat higher than 512 bits. Does anyone have any real experimental data on this question. I assume Schonage has real experimental data? -- ------------------------------------------------------------------ We have the right to defend ourselves | http://www.jim.com/jamesd/ and our property, because of the kind | of animals that we are. True law | James A. Donald derives from this right, not from the | arbitrary power of the omnipotent state.| jamesd@echeque.com