mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2011-09-01, 17:55   #1
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

142810 Posts
Question Wilson-prime search practicalities

Quote:
Originally Posted by rogue View Post
Thanks. You should consider updating the wiki with the new near-Wilson primes.
Done on wikipedia. I observed that p=111310567 is also missed, (p-1)!==-1+22p mod p*p. But maybe this was a typo, since a close prime was duplicated on wiki. The table is now sorted.
R. Gerbicz is offline   Reply With Quote
Old 2011-09-03, 07:37   #2
rajula
 
rajula's Avatar
 
"Tapio Rajala"
Feb 2010
Finland

32·5·7 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
As I promised here you can download and use my code: https://sites.google.com/site/robertgerbicz/wilson

I've finished the search up to 1e10. There were two new near-Wilson prime.
Impressive speed! I felt tempted to leave one core running the code, but without coordination that would most likely be waste of computing resources.

Speaking about waste of resources: I checked what they are doing at the Ibercivis-project: The server gave 30 primes of size ~2e9 to check with a looong expected completion time. Needless to say, I didn't finish those.

I was surprised that Toshio wanted to have a source for the new near-Wilson primes (in Wikipedia) given that he did not provide a valid source for the previous near-Wilson primes found by rogue. Perhaps someone should put the up-to-date information to some other webpage...
rajula is offline   Reply With Quote
Old 2011-09-03, 08:29   #3
MrRepunit
 
MrRepunit's Avatar
 
Mar 2011
Germany

1308 Posts
Default

Quote:
Originally Posted by rajula View Post
Impressive speed! I felt tempted to leave one core running the code, but without coordination that would most likely be waste of computing resources.
Actually I am already running the range 1E10 to 5E10. We could coordinate the search here in the forum. Maybe in ranges of size 1E9 because the current version can not continue if aborted.

So far I found 3 near Wilson primes:

10242692519 -1-97p
11355061259 -1-45p
20042556601 -1+27p

Cheers,
Danilo
MrRepunit is offline   Reply With Quote
Old 2011-09-03, 10:27   #4
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

26248 Posts
Default

Quote:
Originally Posted by MrRepunit View Post
Actually I am already running the range 1E10 to 5E10. We could coordinate the search here in the forum. Maybe in ranges of size 1E9 because the current version can not continue if aborted.

So far I found 3 near Wilson primes:

10242692519 -1-97p
11355061259 -1-45p
20042556601 -1+27p

Cheers,
Danilo
Thanks, just checked with the slow function, these are really near Wilson primes.
I have modified the code, now it is possible to abort and continue it. It saves the progress after each block of primes that processed.

Last fiddled with by R. Gerbicz on 2011-09-03 at 10:27
R. Gerbicz is offline   Reply With Quote
Old 2011-09-03, 11:21   #5
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

11000111010012 Posts
Default

There is a tiny problem in the downloaded code when I use some compilers: the prototype for func() doesn't match the definition of func() because you've changed the first two parameters from mpz_t to lli. Trivial to fix.

Is it asymptotically better to run this on several cores using a small interval on each, or on one core using the largest interval that fits in memory? I have quite a large machine and can allocate 32GB to the process if that would help.

I am a little surprised that when I do

echo -e "100000000000\n100010000000\n10000\n1\n" | time ./a.out

I get

Testing p=100000000073...100001026973, p==5 mod 12, time=1 sec.

and then no further output for at least a thousand seconds; is there something in the implementation to make 5 mod 12 unusually quick? I tried 10^9 .. 10^9+10^8 and it worked fine, so I don't think it's hanging.

Last fiddled with by fivemack on 2011-09-03 at 11:23
fivemack is offline   Reply With Quote
Old 2011-09-03, 11:26   #6
MrRepunit
 
MrRepunit's Avatar
 
Mar 2011
Germany

5816 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
Thanks, just checked with the slow function, these are really near Wilson primes.
I have modified the code, now it is possible to abort and continue it. It saves the progress after each block of primes that processed.
Nice work, indeed! Now we can really go for a distributed search.
(Still I let the range 1E10 to 5E10 running by the older version.)

I found yet another "very near" Wilson prime, damn close:
11774118061 -1-1p
MrRepunit is offline   Reply With Quote
Old 2011-09-03, 12:11   #7
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

142810 Posts
Default

Quote:
Originally Posted by fivemack View Post
There is a tiny problem in the downloaded code when I use some compilers: the prototype for func() doesn't match the definition of func() because you've changed the first two parameters from mpz_t to lli. Trivial to fix.

Is it asymptotically better to run this on several cores using a small interval on each, or on one core using the largest interval that fits in memory? I have quite a large machine and can allocate 32GB to the process if that would help.

I am a little surprised that when I do

echo -e "100000000000\n100010000000\n10000\n1\n" | time ./a.out

I get

Testing p=100000000073...100001026973, p==5 mod 12, time=1 sec.

and then no further output for at least a thousand seconds; is there something in the implementation to make 5 mod 12 unusually quick? I tried 10^9 .. 10^9+10^8 and it worked fine, so I don't think it's hanging.
Thanks I will correct, in one of the first version of my code func used mpz_t type for n1,n2.

In fact when the code prints "Testing ..." it is still testing those primes, so they are not checked, but found all those type of primes from that interval and computed the product of these primes. The ratio of speed for different types are: 3:2:1 for large primes, so p==1 mod 3 is the fastest and p==11 mod 12 is the slowest.

It is better to run the largest interval on one core that fits in memory. That was the reason I've used only one core for my search. (running t cores and on each of them testing interval/t primes yield the same speed with 1 core and interval primes.)
R. Gerbicz is offline   Reply With Quote
Old 2011-09-03, 12:58   #8
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

7·911 Posts
Default

OK, I'll take 5e10 to 6e10 (interval size 4e7 seems about right for that)
fivemack is offline   Reply With Quote
Old 2011-09-03, 17:40   #9
MrRepunit
 
MrRepunit's Avatar
 
Mar 2011
Germany

23·11 Posts
Question Wilson-prime search practicalities

Quote:
Originally Posted by R. Gerbicz View Post
It is better to run the largest interval on one core that fits in memory. That was the reason I've used only one core for my search. (running t cores and on each of them testing interval/t primes yield the same speed with 1 core and interval primes.)
I am not sure about that. I made some benchmarks up to 5E7 using different intervals and found that the optimal interval size is always (about) 1/1000 of the upper boundary. Though I did not check for very large values, my guess here is that there should be also some optimal value which is not using the full memory. I will do some more testing with higher values...
MrRepunit is offline   Reply With Quote
Old 2011-09-03, 17:43   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,987 Posts
Default

Quote:
Originally Posted by MrRepunit View Post
I am not sure about that. I made some benchmarks up to 5E7 using different intervals and found that the optimal interval size is always (about) 1/1000 of the upper boundary. Though I did not check for very large values, my guess here is that there should be also some optimal value which is not using the full memory. I will do some more testing with higher values...
Your tests showed that memory (cache, etc.) size is irrelevant? :surprised
CRGreathouse is offline   Reply With Quote
Old 2011-09-03, 17:50   #11
MrRepunit
 
MrRepunit's Avatar
 
Mar 2011
Germany

23·11 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Your tests showed that memory (cache, etc.) size is irrelevant? :surprised
Not irrelevant, but there is an optimal value of the interval.
Here are my timings:

pmax interval seconds
50000000 2000000 1494
50000000 50000 1024
10000000 10000000 178
10000000 2000000 166
10000000 1000000 163
10000000 500000 168
10000000 10000 110
5000000 2000000 69
5000000 1000000 66
5000000 500000 64
5000000 100000 73
5000000 50000 61
5000000 10000 44
5000000 5000 42
5000000 1000 52
2000000 500000 19
2000000 200000 18
2000000 100000 17
2000000 2000 12
1000000 500000 7
1000000 200000 7
1000000 100000 6
1000000 1000 5

You can see that the optimal interval value is always 1/1000 of the upper boundary.
MrRepunit is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Twin prime search? MooooMoo Twin Prime Search 115 2010-08-29 17:38
k=51 or about coordinated prime search Kosmaj Riesel Prime Search 7 2007-07-13 22:15
Prime Search on PS-3? Kosmaj Riesel Prime Search 6 2006-11-21 15:19
Genetics and Wilson's theorem David John Hill Jr Science & Technology 2 2006-05-10 14:10
Generalized wilson's theorem bouayoun Math 3 2004-03-12 18:24

All times are UTC. The time now is 09:39.

Sat Jan 16 09:39:51 UTC 2021 up 44 days, 5:51, 0 users, load averages: 1.42, 1.36, 1.40

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.