mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Computer Science & Computational Number Theory (https://www.mersenneforum.org/forumdisplay.php?f=116)
-   -   Wilson-prime search practicalities (https://www.mersenneforum.org/showthread.php?t=16028)

R. Gerbicz 2011-09-01 17:55

Wilson-prime search practicalities
 
[QUOTE=rogue;270580]Thanks. You should consider updating the wiki with the new near-Wilson primes.[/QUOTE]

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 2011-09-03 07:37

[QUOTE=R. Gerbicz;270578]As I promised here you can download and use my code: [url]https://sites.google.com/site/robertgerbicz/wilson[/url]

I've finished the search up to 1e10. There were two new near-Wilson prime.[/QUOTE]

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 2011-09-03 08:29

[QUOTE=rajula;270707]Impressive speed! I felt tempted to leave one core running the code, but without coordination that would most likely be waste of computing resources.
[/QUOTE]

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 2011-09-03 10:27

[QUOTE=MrRepunit;270711]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[/QUOTE]
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 2011-09-03 11:21

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 2011-09-03 11:26

[QUOTE=R. Gerbicz;270720]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.[/QUOTE]

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 2011-09-03 12:11

[QUOTE=fivemack;270726]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.[/QUOTE]

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 2011-09-03 12:58

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

MrRepunit 2011-09-03 17:40

Wilson-prime search practicalities
 
[QUOTE=R. Gerbicz;270728]
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.)[/QUOTE]

I am not sure about that. I made some benchmarks up to 5E7 using different intervals and found that the optimal interval size is [B]always[/B] (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 2011-09-03 17:43

[QUOTE=MrRepunit;270746]I am not sure about that. I made some benchmarks up to 5E7 using different intervals and found that the optimal interval size is [B]always[/B] (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...[/QUOTE]

Your tests showed that memory (cache, etc.) size is irrelevant? :surprised

MrRepunit 2011-09-03 17:50

[QUOTE=CRGreathouse;270748]Your tests showed that memory (cache, etc.) size is irrelevant? :surprised[/QUOTE]
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.


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

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