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)

fivemack 2011-09-07 12:53

102..110 graph
 
1 Attachment(s)
This graph has the same axes as before, and covers one 1-mod-3 and one 5-mod-12 pass on 102G..110G with interval=8e8. For this huge interval the printout subphase does not use memory as flatly as before, and the sqrt-like behaviour in subphase 2 appears to be absent.

fivemack 2011-09-07 12:58

110..111 i=2e7 graph
 
1 Attachment(s)
It looks as if the really peaky memory usage is in part a function of the interval being much larger than the number of primes in the range: here's the graph from running 110..111 with i=2e7. Note that the 1-mod-3 section takes twice as much memory as the others, but less time.

[code]
Testing p=110000000003...110999999927, p==11 mod 12, time=312 sec.
Testing p=110000000041...110999999977, p==1 mod 3, time=52119 sec. about 20% slower than 1e8
Testing p=110000000189...110999999837, p==5 mod 12, time=79959 sec. 24% slower than 1e8
Done the st=110000000000-en=111000000000 interval. Time=107912 sec. 27% slower in total
97210.03user 1412.42system 29:58:31elapsed 91%CPU (0avgtext+0avgdata 7641440maxresident)k

Peak memory usage observed is 1.904G
[/code]

Jeff Gilchrist 2011-09-07 16:46

I just updated my mingw64 environment. The previous binary I posted was compiled with GMP 5.0.1 and this new one is with MPIR 2.4.0 which might be faster. Can someone please help me benchmark this to see which one is faster?

GMP5: [url]http://gilchrist.ca/jeff/factoring/wilsontest_win64.zip[/url]

MPIR: [url]http://gilchrist.ca/jeff/factoring/wilsontest_win64_mpir.zip[/url]

Try running the same small range with the same parameters and please let me know if there is a big speed difference.

Christenson 2011-09-07 17:33

[QUOTE=fivemack;271052]I've split this into algorithm-discussion and practicalities threads; am happy to rearrange if it becomes unwieldy again[/QUOTE]

:no: I said to find a FUNNY thread title!!! :smile:

R. Gerbicz 2011-09-07 17:54

I have a slightly improved code: [url]https://sites.google.com/site/robertgerbicz/wilson[/url] (wilsontest2.c). Doing the st=10000000033-en=11000000000 with interval=1e7 the first block (p==1 mod 3) done in 4514 sec. with 774MB Ram. The older code done the same block in 5499 sec. with 902MB Ram. So it seems both an improvement in speed and memory for large primes.

For smallish starting values it is possible that it uses more memory: say testing all primes less than 5e7, with interval=2e6, the time is 569 sec. but used more than 100MB Ram.

Jeff Gilchrist 2011-09-07 19:12

I haven't really looked at the algorithm you are using but if you re-do the same range with the same parameters should you get the same results?

Doing 3 runs, I get mostly the same values in wilson.txt but there are some entries are are in one but not the other and vice-versa.

For example with a wilsonwork.txt file of:
[CODE]st=5-en=10000000
S[0]=7
S[1]=5
S[2]=11
interval=2000192
printtofile=0
[/CODE]

I get mostly the same values but these values are in 1 run but not the other:
[CODE]1750901 -1+34p
1851953 -1-50p
2031053 -1-18p
1666403 -1+99p
2278343 -1+21p
2313083 -1+15p
[/CODE]

and these values are in the second run but not the first:
[CODE]780887 -1-1p
890231 -1+62p
898787 -1-53p
1308491 -1-55p
1638347 -1-45p
1640147 -1-88p[/CODE]

If that is normal, that is fine, but if not, there might be a bug in there somewhere.

Jeff Gilchrist 2011-09-07 19:15

Also, I'm wondering if I found another bug. One of my runs is producing a huge amount of results in wilson.txt but they don't seem of actual value.

I'm getting about 3.6MB so far with a ton of lines like:
[CODE]70039080617 -1+0p
70039083185 -1+0p
70039087061 -1+0p
70039088333 -1+0p
70039089617 -1+0p
70039091345 -1+0p
70039091669 -1+0p
70039092905 -1+0p
70039093649 -1+0p
70039094777 -1+0p
[/CODE]

Using the work file:
[CODE]st=70000000000-en=71000000000
S[0]=70000000003
S[1]=70000000001
S[2]=70000000007
interval=50000256
printtofile=0
[/CODE]

R. Gerbicz 2011-09-07 19:27

[QUOTE=Jeff Gilchrist;271096]I haven't really looked at the algorithm you are using but if you re-do the same range with the same parameters should you get the same results?

Doing 3 runs, I get mostly the same values in wilson.txt but there are some entries are are in one but not the other and vice-versa.

For example with a wilsonwork.txt file of:
[CODE]st=5-en=10000000
S[0]=7
S[1]=5
S[2]=11
interval=2000192
printtofile=0
[/CODE]
If that is normal, that is fine, but if not, there might be a bug in there somewhere.[/QUOTE]

I don't know know how you have gotten that, but interval%BR==0 should be true (the code modify interval a little to satisfy this), now I have inserted an assert to check this.
(and BR=128 in the code).

Jeff Gilchrist 2011-09-07 19:33

[QUOTE=R. Gerbicz;271098]I don't know know how you have gotten that, but interval%BR==0 should be true (the code modify interval a little to satisfy this), now I have inserted an assert to check this.
(and BR=128 in the code).[/QUOTE]

So it is supposed to produce the same results every time?

I just entered the start as 1, the end as 10000000 and put 2000000 as the interval. When it wrote the wilsonwork.txt file it created 2000192 as the interval all on its own.

Jeff Gilchrist 2011-09-07 19:40

[QUOTE=Jeff Gilchrist;271075]I just updated my mingw64 environment. The previous binary I posted was compiled with GMP 5.0.1 and this new one is with MPIR 2.4.0 which might be faster. Can someone please help me benchmark this to see which one is faster?[/QUOTE]

I was able to finish the testing myself, and the MPIR build is *much* faster. I have now re-compile the latest wilsontest and wilsontest2 with the fix Robert just made linked with MPIR and they are both available here:

[url]http://gilchrist.ca/jeff/factoring/wilsontest_win64.zip[/url]

R. Gerbicz 2011-09-07 19:40

[QUOTE=Jeff Gilchrist;271100]So it is supposed to produce the same results every time?

I just entered the start as 1, the end as 10000000 and put 2000000 as the interval. When it wrote the wilsonwork.txt file it created 2000192 as the interval all on its own.

You mean the code posted for wilson1 and 2 have been updated now?[/QUOTE]

I have just inserted an assert in the two codes.
Yes, the code saves the modified interval value, and use that if you stop the program and rerun. Moreover it would not be problem to modify this value after the stop. (as long as this is positive and divisible by 2*BR=256)


All times are UTC. The time now is 15:49.

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