mersenneforum.org  

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

Reply
 
Thread Tools
Old 2011-09-07, 12:53   #34
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×7×461 Posts
Default 102..110 graph

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.
Attached Thumbnails
Click image for larger version

Name:	9.png
Views:	185
Size:	36.0 KB
ID:	6967  
fivemack is offline   Reply With Quote
Old 2011-09-07, 12:58   #35
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

645410 Posts
Default 110..111 i=2e7 graph

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
Attached Thumbnails
Click image for larger version

Name:	interval-2e7.png
Views:	157
Size:	53.1 KB
ID:	6978  

Last fiddled with by fivemack on 2011-09-08 at 09:08
fivemack is offline   Reply With Quote
Old 2011-09-07, 16:46   #36
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

3·17·23 Posts
Default

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: http://gilchrist.ca/jeff/factoring/wilsontest_win64.zip

MPIR: http://gilchrist.ca/jeff/factoring/w...win64_mpir.zip

Try running the same small range with the same parameters and please let me know if there is a big speed difference.
Jeff Gilchrist is offline   Reply With Quote
Old 2011-09-07, 17:33   #37
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

34038 Posts
Default

Quote:
Originally Posted by fivemack View Post
I've split this into algorithm-discussion and practicalities threads; am happy to rearrange if it becomes unwieldy again
I said to find a FUNNY thread title!!!
Christenson is offline   Reply With Quote
Old 2011-09-07, 17:54   #38
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

112×13 Posts
Default

I have a slightly improved code: https://sites.google.com/site/robertgerbicz/wilson (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.

Last fiddled with by R. Gerbicz on 2011-09-07 at 17:54
R. Gerbicz is offline   Reply With Quote
Old 2011-09-07, 19:12   #39
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

3·17·23 Posts
Default

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
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
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
If that is normal, that is fine, but if not, there might be a bug in there somewhere.
Jeff Gilchrist is offline   Reply With Quote
Old 2011-09-07, 19:15   #40
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

3·17·23 Posts
Default

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
Using the work file:
Code:
st=70000000000-en=71000000000
S[0]=70000000003
S[1]=70000000001
S[2]=70000000007
interval=50000256
printtofile=0
Jeff Gilchrist is offline   Reply With Quote
Old 2011-09-07, 19:27   #41
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

110001001012 Posts
Default

Quote:
Originally Posted by Jeff Gilchrist View Post
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
If that is normal, that is fine, but if not, there might be a bug in there somewhere.
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).

Last fiddled with by R. Gerbicz on 2011-09-07 at 19:28
R. Gerbicz is offline   Reply With Quote
Old 2011-09-07, 19:33   #42
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

3×17×23 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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).
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.

Last fiddled with by Jeff Gilchrist on 2011-09-07 at 19:39
Jeff Gilchrist is offline   Reply With Quote
Old 2011-09-07, 19:40   #43
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

3×17×23 Posts
Default

Quote:
Originally Posted by Jeff Gilchrist View Post
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?
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:

http://gilchrist.ca/jeff/factoring/wilsontest_win64.zip
Jeff Gilchrist is offline   Reply With Quote
Old 2011-09-07, 19:40   #44
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

30458 Posts
Default

Quote:
Originally Posted by Jeff Gilchrist View Post
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?
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)

Last fiddled with by R. Gerbicz on 2011-09-07 at 20:32
R. Gerbicz 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 08:19.


Mon Aug 8 08:19:30 UTC 2022 up 32 days, 3:06, 1 user, load averages: 1.31, 1.02, 0.97

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔