mersenneforum.org LLR / Gwnums version
 Register FAQ Search Today's Posts Mark Forums Read

 2005-09-16, 13:49 #12 Cruelty     May 2005 65216 Posts So testing k*2^n-b for k=736320585 is not the optimal way to use LLR? Last fiddled with by Cruelty on 2005-09-16 at 13:49
2005-09-16, 15:27   #13
Jean Penné

May 2004
FRANCE

24·5·7 Posts
Using LLR with big k's

Quote:
 Originally Posted by Cruelty So testing k*2^n-b for k=736320585 is not the optimal way to use LLR?
If b != 1, LLR will do a PRP test...
If b == 1, LLR will do a proving test ; k being large, gwnum will work in generic mode in both cases, so you will not get the IBDWT performances, but I don't know if a faster program is presently available (try Openpfgw, but it also uses the gwnum code...).

Jean

 2005-09-18, 19:11 #14 Citrix     Jun 2003 2·33·29 Posts Jean, which is the fastest k to test, in terms of speed. Are all k under 2^20 the same speed? What is the difference in speed between a k under 2^20 and a k between 2^20 and 2^21? Citrix
2005-09-19, 07:40   #15
Jean Penné

May 2004
FRANCE

24×5×7 Posts

Quote:
 Originally Posted by Citrix Jean, which is the fastest k to test, in terms of speed. Are all k under 2^20 the same speed? What is the difference in speed between a k under 2^20 and a k between 2^20 and 2^21? Citrix
It is rather more complicated... and it requires to give precisions about how the gwnum code proceeds to do multiplications modulo N = k*2^n+-b numbers (surely, George Woltman would do that better than me...).
1) The speed is determined by the FFT length necessary to process a number N of given bit length.
2) According to the k size, the gwnum code uses three different algorithms to do multiplications : pure IBDWT, Zero paded IBDWT, generic mode.
3) The pure IBDWT algorithm can only be used with k values from 1 to around 2^20 ; it is the most efficient, because it requires the smallest FFT length, and makes the modular reduction totally free. Nevertheless, the FFT length for a given size of N increases smoothly by a factor of 2 when k goes from 1 to 2^20, then, the Zero padded algorithm becomes the better.
4) The Zero padded IBDWT can be used for k values up to around 2^48, and the performances continue to decrease smoothly.
5) For higher k values, the generic mode is used, and the speed for given size of N is around three times smaller than the IBDWT one.

I hope this rather involved explanation will satisfy you.

Jean

 2005-09-19, 07:43 #16 Citrix     Jun 2003 2×33×29 Posts The smaller the k the faster it will be? Did I get it right? Citrix
2005-09-19, 08:25   #17
Jean Penné

May 2004
FRANCE

24·5·7 Posts

Quote:
 Originally Posted by Citrix The smaller the k the faster it will be? Did I get it right? Citrix
Yes, for a given bit length of the number to test !

 2005-11-26, 21:39 #18 Ken_g6     Jan 2005 Caught in a sieve 2·197 Posts I've been trying to find a generic top-5000 prime with LLR 4.62 recently. I chose Proth tests with n=409600, k increasing from 600 to 1000000, since 2^20 is 1048576. But around k=65487, running on a P4 2.8GHz non-hyperthreaded, I noticed that LLR said I was using a zero-padded FFT. Which according to the thread above shouldn't happen, right? Looking through the log, there seems to have been a big jump in time taken between 60000 and 62000. While I can't completely rule out other processes for this jump, considering the size of the k, that zero-padded message is weird.

 Similar Threads Thread Thread Starter Forum Replies Last Post Jean Penné Software 11 2011-02-20 18:22 Jean Penné Software 30 2010-09-21 16:43 richs Software 41 2009-01-07 14:40 Cruelty Riesel Prime Search 8 2006-05-16 15:00 Prime95 Software 13 2006-02-15 16:32

All times are UTC. The time now is 07:31.

Wed Aug 12 07:31:40 UTC 2020 up 26 days, 3:18, 1 user, load averages: 1.71, 1.46, 1.44