From: "James A. Donald" <jamesd@echeque.com>
Date: Tue, 11 Jul 95 18:42:01 PDT
To: Ray Cromwell <jim@acm.org
Subject: Re: Moby ints [Re: Num Rat]
Message-ID: <199507120139.SAA07236@shell1.best.com>
MIME-Version: 1.0
Content-Type: text/plain


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