Hi,
At 05:19 AM 10/25/99 +0200, Robert van der Peijl wrote:
>> Why is there a difference in iteration time between the LL test and a
>> double test.
There isn't - other than double-checking is working on smaller exponents.
>For the same FFT-size, the double checking code has to perform a bit
>extra work per iteration:
>it multiplies by 2 before the DWT, and divides by 4 afterward.
This isn't quite how double-checking works. What happens is the initial
Lucas value, 4, is shifted left a random number of bits. We remember this
shift count in the variable called units_bit.
Each iteration does a squaring, then computes the new location of the
units bit (old_units_bit * 2 modulo exponent_being_tested). Now that
we know where the units bit is, it is easy to subtract two.
This has the same property of having the FFT deal with different data, but
without the cost of a multiply by 2 and divide by 4 on every iteration.
BTW, the above is done on first-time tests too.
Regards,
George
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
