Re: Mersenne: difference between LL and double check
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
Re: Mersenne: difference between LL and double check
Paul van Grieken asked on 21 Oct 1999 at 17:16 h Why is there a difference in iteration time between the LL test and a double test. 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 guarantees totally different data during the convolutions. This allows to use the same starting value L[1], thus generating (if nothing went wrong in the hardware) the same residue as the first test. (This is a translation of my reply in Dutch to Paul van Grieken) How much slower (in percentage) does this make double checking compared to a first-time LL test? Robert van der Peijl [EMAIL PROTECTED] _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: difference between LL and double check
On 21 Oct 99, at 17:16, Grieken, Paul van wrote: But I thought it only took longer to complete not that the iteration take longer. So I can say if the number doubles it takes 4x more time to complete. Very roughly, yes. There are (p-2) iterations to do for a test of exponent p. The computer work per iteration is proportional to N log N, where N is the FFT run length. The complication here is that as the run length increases, the effectiveness of the computer's cache reduces, so there are also more "wasted" cycles when the CPU cannot work as it's waiting for operands to be fetched from memory. Another small complication is that you can't _quite_ cover double the range with double the FFT size. The larger FFT needs an extra bit precision, so the range of exponents which can be covered with FFT run length 2N is not quite twice as large as the range of exponents which can be covered with FFT run length N. These effects (p-2 not p, the log N factor and the FFT run length complication) are really quite small, but the CPU cache effectiveness fall-off _does_ have quite a noticeable effect. George's V19 code has managed to reduce the cache fall-off somehow, this is probably the main reason for the increase in speed over V18. Regards Brian Beesley _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: difference between LL and double check
Why is there a difference in iteration time between the LL test and a double test. The double test took about 0.115sec and a LL test 0.254sec for the same amount of iterations. bye, Paul van Grieken Alcatel telecom Nederland Afd: TTAC Netwerk Elementen Tel: 070-3079353 email: [EMAIL PROTECTED] marklin collector _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: difference between LL and double check
The exponent you are using to LL test is probably significantly larger than the exponent your are using to double test. It's doing the same operation on both but on the LL test it is using a larger FFT (AFIK). Larger FFT requires more memory. More memory requires more time to juggle all of that data. -Chuck On Thu, 21 Oct 1999, Grieken, Paul van wrote: Why is there a difference in iteration time between the LL test and a double test. The double test took about 0.115sec and a LL test 0.254sec for the same amount of iterations. bye, Paul van Grieken Alcatel telecom Nederland Afd: TTAC Netwerk Elementen Tel: 070-3079353 email: [EMAIL PROTECTED] marklin collector _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers -- ~~~ : WWW: http://www.silverlink.net/poke : : E-Mail: [EMAIL PROTECTED] : ~~ : Ask Mike! Aviation's response to Dear : : Abby. http://www.avstarair.com: ~~~ _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
