mersenneforum.org  

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

Reply
 
Thread Tools
Old 2011-08-29, 15:33   #56
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3×17×131 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
I have some really new ideas in my latest code, with it I can test all primes for the Wilson problem up to 5*10^7 in 671 seconds. I will release my code in about 4 days. Now I am at 4billions and I will reach 10billions in less than 4 days, not much chances for a Wilson prime (and indeed so far I have not found a new one).
So interestingly with a single computer it was possible to beat a boinc project, their goal was to test all primes up to 4billions, and as I can see they are at ~2.3billions.
Very interesting, although I don't know what BOINC project you are referring to. I am aware of unpublished results on the Wilson search up to 1.2e11.

How much memory does your program use?
rogue is offline   Reply With Quote
Old 2011-08-29, 16:12   #57
axn
 
axn's Avatar
 
Jun 2003

2·2,693 Posts
Default

Quote:
Originally Posted by rogue View Post
although I don't know what BOINC project you are referring to.
Up thread. Initial few posts.
axn is offline   Reply With Quote
Old 2011-08-29, 16:33   #58
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

1A1916 Posts
Default

Quote:
Originally Posted by axn View Post
Up thread. Initial few posts.
That project is such a waste of computing resources that I forgot it.
rogue is offline   Reply With Quote
Old 2011-08-29, 16:45   #59
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

157310 Posts
Default

Quote:
Originally Posted by rogue View Post
Very interesting, although I don't know what BOINC project you are referring to. I am aware of unpublished results on the Wilson search up to 1.2e11.

How much memory does your program use?
Thanks, now done some search using my largest result, that p=4296847931 is a near miss: (p-1)!==-1+41*p mod p*p, there are some hits: http://www.enotes.com/topic/Wilson_prime (in fact you can see this also at http://en.wikipedia.org/wiki/Wilson_prime), so the "known" wilson search is complete up to 6*10^9. So far my code found all these solutions, except the largest two.

My code finds (p-1)! mod p*p in polynomial time, this is achieved with that we determine for lots of primes at once (p-1)! mod p*p. But for p~10^10 we don't have enough memory, there is a slowdown for (very) large primes. It doesn't really matter how much memory you have got, but with more memory it runs faster. I have choosen a parameter that it will use approx 1GB RAM for p~10^10. Determining for 10 million primes in a single search (p-1)! mod p*p.

Last fiddled with by R. Gerbicz on 2011-08-29 at 16:52
R. Gerbicz is offline   Reply With Quote
Old 2011-08-29, 18:05   #60
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3·17·131 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
Thanks, now done some search using my largest result, that p=4296847931 is a near miss: (p-1)!==-1+41*p mod p*p, there are some hits: http://www.enotes.com/topic/Wilson_prime (in fact you can see this also at http://en.wikipedia.org/wiki/Wilson_prime), so the "known" wilson search is complete up to 6*10^9. So far my code found all these solutions, except the largest two.

My code finds (p-1)! mod p*p in polynomial time, this is achieved with that we determine for lots of primes at once (p-1)! mod p*p. But for p~10^10 we don't have enough memory, there is a slowdown for (very) large primes. It doesn't really matter how much memory you have got, but with more memory it runs faster. I have choosen a parameter that it will use approx 1GB RAM for p~10^10. Determining for 10 million primes in a single search (p-1)! mod p*p.
I hadn't realized that Toshio took my results and published them.

Either your algorithm is vastly different from mine (although it sounds similar) or you have written better optimized code.
rogue is offline   Reply With Quote
Old 2011-08-29, 18:05   #61
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

5·709 Posts
Default

Quote:
Originally Posted by Gammatester View Post
Are there any references that multiply with 0 and dividing a zero is optimized on recent processors?
Core 2 processors do have fast paths for multiplication when one of the numbers being multiplied is zero or a power of two. Not sure about division.
jasonp is offline   Reply With Quote
Old 2011-08-30, 12:09   #62
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

112×13 Posts
Default

Mark, you missed p=3542985241 as a near-Wilson prime: (p-1)!==-1-74p mod p^2. Now I am at 6 billions.
R. Gerbicz is offline   Reply With Quote
Old 2011-08-30, 12:30   #63
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3·17·131 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
Mark, you missed p=3542985241 as a near-Wilson prime: (p-1)!==-1-74p mod p^2. Now I am at 6 billions.
I'll have to take a look. Either it is a code bug or the person who ran that range made a mistake. There were a number of ranges above 3e9 that I did not run and that was in one of them.
rogue is offline   Reply With Quote
Old 2011-09-01, 16:13   #64
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

112×13 Posts
Default

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.
R. Gerbicz is offline   Reply With Quote
Old 2011-09-01, 17:05   #65
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

150318 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.
Thanks. You should consider updating the wiki with the new near-Wilson primes.
rogue is offline   Reply With Quote
Old 2011-09-01, 18:23   #66
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

11010000110012 Posts
Default

I d/l'd your code, but haven't looked at it in detail. I did see that you use GMP, so your speed is rather surprising considering GMP overhead.
rogue is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
World Record Factorial Prime Found rogue Lounge 8 2012-03-02 16:41
square root modulo prime Raman Math 1 2010-02-16 21:25
Order of 3 modulo a Mersenne prime T.Rex Math 7 2009-03-13 10:46
Period of Lucas Sequence modulo a prime T.Rex Math 7 2007-06-04 21:30
Conjecture about multiplicative order of 3 modulo a Mersenne prime T.Rex Math 9 2007-03-26 17:35

All times are UTC. The time now is 00:38.


Fri Aug 12 00:38:08 UTC 2022 up 35 days, 19:25, 2 users, load averages: 0.83, 1.09, 1.20

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.

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