mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > Prime Cullen Prime

 
 
Thread Tools
Old 2006-12-01, 22:08   #12
Siemelink
 
Siemelink's Avatar
 
Jan 2006
Hungary

26810 Posts
Default

I am currently sieving with Multisieve Woodall numbers. I use the range from 1.3 million to 2 million. I still have 30,000 candidates left. Do I understand this discussion correctly that Multisieve is not really meant for such a range?
If this is so, how can I sieve quicker? Citrix, would your sieve be amendable to do Woodalls? Or should I stick with Multisieve but switch to short ranges (10,000) containing 500 candidates?

Have a nice day, Willem.
Siemelink is offline  
Old 2006-12-01, 23:58   #13
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2×3×983 Posts
Default

Quote:
Originally Posted by Siemelink View Post
I am currently sieving with Multisieve Woodall numbers. I use the range from 1.3 million to 2 million. I still have 30,000 candidates left. Do I understand this discussion correctly that Multisieve is not really meant for such a range?
If this is so, how can I sieve quicker? Citrix, would your sieve be amendable to do Woodalls? Or should I stick with Multisieve but switch to short ranges (10,000) containing 500 candidates?

Have a nice day, Willem.
MultiSieve is fine for that range since you are sieving all n in that range. If you were only sieving where n is a prime, then Citrix's code would have the advantage.
rogue is online now  
Old 2006-12-02, 05:04   #14
maxal
 
maxal's Avatar
 
Feb 2005

22·32·7 Posts
Default

Quote:
Originally Posted by maxal View Post
P.P.S. There is another speed up possible if we replace p-1 with the multiplicative order of 2 modulo p (that is a divisor of p-1). So, instead of letting k go from 0 to p-2, we compute incrementally and store values u[i]=2^i mod p, i=1,2,... until we get u[z]=1, meaning that z is the multiplicative order of 2 modulo p. Then we let k go from 0 to z-1, compute
r = ((z-k) * p + u[k] * z) mod (p*z), and eliminate candidates r, r + (p*z), r + 2*(p*z), ..., up to selected upper bound.
Correction: r = ((z-k) * p + u[k] * (p-1)) mod (p*z)
maxal is offline  
Old 2006-12-26, 05:42   #15
Citrix
 
Citrix's Avatar
 
Jun 2003

2·5·157 Posts
Default

@ rouge.

I was able to modify your program yesterday, to suit my needs, but it did not become as fast as we thought it would have become. I just increased the size of the array that stores all the values of 2^1, 2^2... (mod p). Though I did see some speed up.

I am not sure how to speed up the program further. Any thoughts.

Also something is wrong with the time function. The time per candidate keeps on jumping between 15 sec and 60 secs. (I did not modify this code, so its not me)
Citrix is offline  
Old 2006-12-26, 13:39   #16
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2×3×983 Posts
Default

Quote:
Originally Posted by Citrix View Post
@ rouge.

I was able to modify your program yesterday, to suit my needs, but it did not become as fast as we thought it would have become. I just increased the size of the array that stores all the values of 2^1, 2^2... (mod p). Though I did see some speed up.

I am not sure how to speed up the program further. Any thoughts.

Also something is wrong with the time function. The time per candidate keeps on jumping between 15 sec and 60 secs. (I did not modify this code, so its not me)
Is as fast as your code? If not, is there anything you see that could be modified to help? I wonder if the compiler you are using is smart enough to optimize the code correctly so that the ASM routines I have written do not provide any benefit (and might actually hurt performance). The code was written to be fairly generic, so it doesn't take advantage of any CPU specific optimizations. I would expect that you would see the biggest benefit for p > 2^31.

I'm not aware of any issues with the timing code. If you find something let me know.
rogue is online now  
Old 2006-12-26, 19:56   #17
Citrix
 
Citrix's Avatar
 
Jun 2003

2·5·157 Posts
Default

Quote:
Originally Posted by rogue View Post
Is as fast as your code? If not, is there anything you see that could be modified to help? I wonder if the compiler you are using is smart enough to optimize the code correctly so that the ASM routines I have written do not provide any benefit (and might actually hurt performance). The code was written to be fairly generic, so it doesn't take advantage of any CPU specific optimizations. I would expect that you would see the biggest benefit for p > 2^31.

I'm not aware of any issues with the timing code. If you find something let me know.
It is about as fast as my program. My program only computes upto 2^31, so there is no way to compare on speeds after that. As for the compiler, I am using VC++ 6.0. Is there a better compiler I could use? I am testing both programs on a 1.4 Ghz intel celeron processor.

Currently I have only sieved upto 350M. (The sieve is quite slow, about 80M/hr. Not sure if this series will be worth testing.) So, it will be a long time before I cross 2^31, and if the program gets slower after that....

For the timing issue I think it depends on the distribution of factors. Sometimes 10 factors are found in a min and then no factors for 5+ mins. I think this would screw up the timing?
Citrix is offline  
Old 2007-01-31, 08:26   #18
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

3·977 Posts
Default

I sieved cullen numbers from n=1 to n=5,000,000 up to 2.5G (2.5 * 109). I found 4,847,529 factors so that leaves 152,457 unknowns plus the 14 known cullen primes.

Here is all 5 million n's with factors:

cullenfactors.zip (18 Mb).

The 14 primes have "PRIME" instead of a factor, and the 152,457 unknowns have "?" instead of a factor.

Here is ABC format file for the 109,042 unknowns between n=1,500,000 (current progress according to http://www.prothsearch.net/cullenrange.html ) and n=5,000,000:

cullen1.5M-5M.zip
ATH is offline  
Old 2007-01-31, 19:22   #19
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

52A16 Posts
Default

p*2p+1 cannot be prime if p>3 is a prime twin.

First suppose p=1 (mod 3) and let p=2q+1 (because p is odd). Operating modulo 3 we find:

p*2p+1 = 1*22q+1+1 = 22q*2+1 = (22)q*2+1 = 1q*2+1 = 2+1 = 0 (mod 3)

The other possibility is p=2 (mod 3) and p+2 also a prime. Operating modulo p+2 we find:

p*2p+1 = (-2)*2p+1 = -2p+1+1 = -1+1 = 0 (mod p+2)

So in both cases p*2p+1 is composite.
alpertron is offline  
Old 2007-02-01, 01:17   #20
brunoparga
 
brunoparga's Avatar
 
Feb 2006
Brasília, Brazil

3×71 Posts
Default

Dario,

Modular arithmetic still looks like a strange realm to me. So, I'm not sure if I understand what you've written:
Quote:
Originally Posted by alpertron View Post
p*2p+1 = 1*22q+1+1 = 22q*2+1 = (22)q*2+1 = 1q*2+1 = 2+1 = 0 (mod 3)
In short, does this mean no prime p = 1 (mod 3) can generate a Cullen prime? Even if this p isn't a prime twin?

Quote:
Originally Posted by alpertron View Post
p*2p+1 = (-2)*2p+1 = -2p+1+1 = -1+1 = 0 (mod p+2)
I can't understand the part I've put in bold. Since both sides have a "+1" term, I assume I can change that particular equality to:

-2p+1 = -1 (mod p+2)

I still can't understand it even if I multiply both sides by (-1) (can I do that?), giving:

2p+1 = 1 (mod p+2)

Testing with small primes, I can see it works. But why?

Thanks a lot,
Bruno
brunoparga is offline  
Old 2007-02-01, 03:59   #21
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

3·977 Posts
Default

Quote:
Originally Posted by brunoparga View Post
2p+1 = 1 (mod p+2)
This is just Fermat's Little Theorem with p+2 = prime (p being twin prime) and a=2.
ATH is offline  
Old 2007-02-01, 12:14   #22
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

101001010102 Posts
Default

Quote:
Originally Posted by brunoparga View Post
In short, does this mean no prime p = 1 (mod 3) can generate a Cullen prime? Even if this p isn't a prime twin?
In that case p does not need to be prime. When p=1 (mod 3) the argument shown above demonstrates that p*2p+1 is multiple of 3.

Last fiddled with by alpertron on 2007-02-01 at 12:15
alpertron is offline  
 

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Generalized Cullen and Woodall Searches rogue And now for something completely different 29 2019-11-20 14:01
Cullen and Woodall altering on Prime Pages jasong jasong 9 2008-01-25 01:51
Can we add Cullen and Woodall p-1ing here? jasong Marin's Mersenne-aries 1 2007-11-18 23:17
Prime Cullen Prime, Rest in Peace hhh Prime Cullen Prime 4 2007-09-21 16:34
Smallest floor of k for cullen prime Citrix Prime Cullen Prime 12 2007-04-26 19:52

All times are UTC. The time now is 21:11.

Fri Sep 18 21:11:28 UTC 2020 up 8 days, 18:22, 1 user, load averages: 1.50, 1.92, 1.82

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.