Wilson-prime search practicalities

[R. Gerbicz]

Originally Posted by rogue

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.

[rajula]

Originally Posted by R. Gerbicz

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...

[MrRepunit]

Originally Posted by rajula

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

[R. Gerbicz]

Originally Posted by MrRepunit

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.

[fivemack]

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.

[MrRepunit]

Originally Posted by R. Gerbicz

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

[R. Gerbicz]

Originally Posted by fivemack

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.)

[fivemack]

OK, I'll take 5e10 to 6e10 (interval size 4e7 seems about right for that)

[MrRepunit]

Originally Posted by R. Gerbicz

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...

[CRGreathouse]

Originally Posted by MrRepunit

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

[MrRepunit]

Originally Posted by CRGreathouse

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.