Factorial modulo a prime - Page 6

rogue · 2011-08-29, 15:33

Quote:

Originally Posted by R. Gerbicz

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?

axn · 2011-08-29, 16:12

Quote:

Originally Posted by rogue

although I don't know what BOINC project you are referring to.

Up thread. Initial few posts.

rogue · 2011-08-29, 16:33

Quote:

Originally Posted by axn

Up thread. Initial few posts.

That project is such a waste of computing resources that I forgot it.

R. Gerbicz · 2011-08-29, 16:45

Quote:

Originally Posted by rogue

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.

rogue · 2011-08-29, 18:05

Quote:

Originally Posted by R. Gerbicz

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.

jasonp · 2011-08-29, 18:05

Quote:

Originally Posted by Gammatester

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.

R. Gerbicz · 2011-08-30, 12:09

Mark, you missed p=3542985241 as a near-Wilson prime: (p-1)!==-1-74p mod p^2. Now I am at 6 billions.

rogue · 2011-08-30, 12:30

Quote:

Originally Posted by R. Gerbicz

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.

R. Gerbicz · 2011-09-01, 16:13

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.

rogue · 2011-09-01, 17:05

Quote:

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.

Thanks. You should consider updating the wiki with the new near-Wilson primes.

rogue · 2011-09-01, 18:23

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.

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

2011-08-30, 12:09	#62
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 3045₈ Posts	Mark, you missed p=3542985241 as a near-Wilson prime: (p-1)!==-1-74p mod p^2. Now I am at 6 billions.

2011-09-01, 16:13	#64
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 11²·13 Posts	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.

2011-09-01, 18:23	#66
rogue "Mark" Apr 2003 Between here and the 3×17×131 Posts	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.