On 8 Jul 99, at 23:33, Lucas Wiman wrote:
> >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.
This is all true for numbers with many times the number of bits that
can be stored in a computer register. However, find a recursive
method for triple-precision arithmetic that beats the "classic" long
multiplication method, and you'll definitely have earned whatever
carrot may be dangled!
>
> Well, I wasn't talking about the massive scale of numbers used in LL tests.
> I was speaking of the < 95 bit integers used in factoring, and using Head's
> algorithm in the calculation of 2^p mod f. I doubt that FFT would be
> worthwhile here, and would probably slow it down considerably.
Too right!
> Chris Nash writes:
> >But enough already. One thing I'm surprised nobody has mentioned yet - is it
> >even in Lucas' FAQ? - is that modular reduction in the Mersenne case is
> >sinfully inexpensive. Even with a pure integer, no FFT implementation,
> >reduction mod 2^p-1 is very quick - take the lower p bits, take the rest of
> >the number shifted down by p bits, add them together. The size of the
> >original number is usually around 2p bits, so one iteration of the
> >shift-and-add will get the result correct to within 1 extra subtraction at
> >most.
This is also true, but we don't (often) want to check if 2^p-1 is a
factor of anything ... in this case, we're trying to find factors of
2^p-1.
For reasonably small multi-precision numbers, Head's method is
actually very good, if you're working on a true RISC processor with
no integer multiply instruction.
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
