mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > 15k Search

 
 
Thread Tools
Old 2005-09-16, 13:49   #12
Cruelty
 
Cruelty's Avatar
 
May 2005

65216 Posts
Default

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
Cruelty is offline  
Old 2005-09-16, 15:27   #13
Jean Penné
 
Jean Penné's Avatar
 
May 2004
FRANCE

24·5·7 Posts
Default 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
Jean Penné is offline  
Old 2005-09-18, 19:11   #14
Citrix
 
Citrix's Avatar
 
Jun 2003

2·33·29 Posts
Default

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
Citrix is offline  
Old 2005-09-19, 07:40   #15
Jean Penné
 
Jean Penné's Avatar
 
May 2004
FRANCE

24×5×7 Posts
Default

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
Jean Penné is offline  
Old 2005-09-19, 07:43   #16
Citrix
 
Citrix's Avatar
 
Jun 2003

2×33×29 Posts
Default

The smaller the k the faster it will be? Did I get it right?

Citrix
Citrix is offline  
Old 2005-09-19, 08:25   #17
Jean Penné
 
Jean Penné's Avatar
 
May 2004
FRANCE

24·5·7 Posts
Default

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 !
Jean Penné is offline  
Old 2005-11-26, 21:39   #18
Ken_g6
 
Ken_g6's Avatar
 
Jan 2005
Caught in a sieve

2·197 Posts
Default

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.
Ken_g6 is offline  
 

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
LLR Version 3.8.5 is available! Jean Penné Software 11 2011-02-20 18:22
LLR Version 3.8.1 is now available! Jean Penné Software 30 2010-09-21 16:43
Which version for P-III's? richs Software 41 2009-01-07 14:40
LLR - new version Cruelty Riesel Prime Search 8 2006-05-16 15:00
Version 24.14 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.