On Thu, 08 Jul 1999, Brian J. Beesley wrote:
> On 8 Jul 99, at 6:19, Lucas Wiman wrote:
>
> > In the book _Primes and Programming_ Head's method of multiplying
> > two numbers mod n is mentioned. Is this actually more effiecient
> > than simply multiplying the two numbers and taking the modulus?
>
> Look at it this way. Head's method is essentially binary long
> multiplication, with the "wrinkle" that you take the remainder modulo
> n after each shift & add operation.
That is going to be a *lot* slower than FFT convolution, for numbers the size
of the Mersenne numbers we're testing! FFT is O(n*log(n)) where n is the number
of limbs in the numbers being multiplied. Head's method is O(n^2), with O
being slightly smaller than for straight long multiplication. A recursive method
splitting the number in the middle, then doing a subtraction trick to make
three instead of four submultiplies, is O(n^y), where y is log(3)/log(2), which
is about 19/12.
phma
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
