Pierre Abbat writes:
>>> In the book _Primes and Programming_ Head's method of multiplying
>>> two numbers mod n is mentioned. Is this actually more efficient
>>> 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.
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.
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.
I think I might split off the parts about modular arithmetic into their
own section, or in the beginning stuff section. I'll probably add this
question sometime tomorrow.
-Lucas Wiman
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
