Wilson-prime search practicalities - Page 5

R. Gerbicz · 2011-09-07, 19:46

Quote:

Originally Posted by Jeff Gilchrist

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

What I don't know understand, that all of those numbers are composites, some of them are divisible by 5, so surely they are composites by mpz_probab_prime_p function also. Have you got about 5 GB Ram on that machine? (interval=5e7 requires appprox. that amount for large primes).

When I put a code, that means it survived thousands of different runs for different st,en,interval inputs for en<10^5, and passed a large test, where en~1e10, just to check there is no int/long long int problem in the code.

Jeff Gilchrist · 2011-09-07, 19:58

Quote:

Originally Posted by R. Gerbicz

What I don't know understand, that all of those numbers are composites, some of them are divisible by 5, so surely they are composites by mpz_probab_prime_p function also. Have you got about 5 GB Ram on that machine? (5e7 requires appprox. that amount).

When I put a code, that means it survived thousands of different runs for different st,en,interval inputs for en<10^5, and passed a large test, where en~1e10, just to check there is no int/long long int problem in the code.

Note that the interval is 50000256 which is not divisible by BR=128 so could that be screwing things up?

I have 8GB of RAM on that machine, but I never saw it use more than 1.4GB of RAM though. I'm now re-trying the range with the wilsontest2 code using MPIR. There also might have been a bad GMP5 library or something since my old mingw64 environment was misbehaving.

Jeff.

R. Gerbicz · 2011-09-07, 20:19

Quote:

Originally Posted by Jeff Gilchrist

Note that the interval is 50000256 which is not divisible by BR=128 so could that be screwing things up?

I have 8GB of RAM on that machine, but I never saw it use more than 1.4GB of RAM though. I'm now re-trying the range with the wilsontest2 code using MPIR. There also might have been a bad GMP5 library or something since my old mingw64 environment was misbehaving.

Jeff.

Now I understand you, interval should be divisible by 2*BR (=256, since BR=128) the correct assertion, because sg=interval/BR, but sg is also even. (your problem could be that in your case sg is an integer, but odd, and the primes are not stored, only the difference's in 2 bytes, so 2 differences in an unsigned int) Modified again the 2 codes.

Yes, that uses less than 5 GB, the reason that your 71e9-70e9=1e9 range contains much less than 2*interval primes.

MrRepunit · 2011-09-08, 21:05

Quote:

Originally Posted by Jeff Gilchrist

I was able to finish the testing myself, and the MPIR build is *much* faster.

I can confirm this. The same under Linux 64 Bit, speedup of factor 1.5 to 2 compared to GMP5, depending on input parameters.

Jeff Gilchrist · 2011-09-09, 00:00

Some results with different intervals:

interval=50000128
Done the st=71000000000-en=72000000000 interval. Time=57585 sec.

interval=5000192
Done the st=72000000000-en=73000000000 interval. Time=111822 sec.

Huge difference in speed with those intervals. Testing 75000064 right now.

MrRepunit · 2011-09-09, 05:23

Quote:

Originally Posted by Jeff Gilchrist

Some results with different intervals:

interval=50000128
Done the st=71000000000-en=72000000000 interval. Time=57585 sec.

interval=5000192
Done the st=72000000000-en=73000000000 interval. Time=111822 sec.

Huge difference in speed with those intervals. Testing 75000064 right now.

My guess is that it will be at around 57500 sec.
Reason is that there are only 40M primes in that interval. So except from other effects the speed should be the same.

fivemack · 2011-09-09, 12:38

It will be faster; the interval parameter is used in two places in the software, in one place min(interval length, number of primes) is relevant, and in the other it isn't.

Compare the timings in my posts

http://www.mersenneforum.org/showpos...6&postcount=12

and

http://www.mersenneforum.org/showpos...5&postcount=35

in both of which the interval is larger than the number of primes in the range.

To compare:

Code:

interval    RAM     time  slices
1e8       3.647  79427.6       3
2e7       1.904  97210.0       3
1e7       0.983 126835.4       4
4e6       0.397 200194.4      11

(this is with wilsontest.c linked against gmp-5; I am rerunning one parameter choice with wilsontest2.c linked against mpir-2.4)

R.D. Silverman · 2011-09-09, 13:15

Quote:

Originally Posted by MrRepunit

My guess is that it will be at around 57500 sec.
Reason is that there are only 40M primes in that interval. So except from other effects the speed should be the same.

Everyone needs to keep in mind that Wilson primes are going to be
very very rare. Much rarer than than Mersenne primes. They should
be comparable in density (heuristically) to Wiefrich or Miramanoff primes.

As John Selfridge said: We know that loglog N goes to infinity. However,
noone has ever actually observed it doing so.

rajula · 2011-09-09, 13:32

Quote:

Originally Posted by R.D. Silverman

Everyone needs to keep in mind that Wilson primes are going to be
very very rare. Much rarer than than Mersenne primes. They should
be comparable in density (heuristically) to Wiefrich or Miramanoff primes.

As John Selfridge said: We know that loglog N goes to infinity. However,
noone has ever actually observed it doing so.

To put some actual figures: it should be reasonably easy to get to 10¹³ and the current known search-limit is around 10¹¹. The (heuristically) expected number of Wilson primes on that interval is $\log\left(\frac{13}{11}\right) \approx 17%$ , which for me is still worth the shot. However, at some point on one has to think if the odds are too low...

rogue · 2011-09-09, 13:43

Quote:

Originally Posted by rajula

To put some actual figures: it should be reasonably easy to get to 10¹³ and the current known search-limit is around 10¹². The (heuristically) expected number of Wilson primes on that interval is $\log\left(\frac{13}{12}\right) \approx 8%$ , which for me is still worth the shot. However, at some point on one has to think if the odds are too low...

I'm not certain where you got 1e12. Right now they are around 1e11.

R.D. Silverman · 2011-09-09, 13:53

Quote:

Originally Posted by rajula

To put some actual figures: it should be reasonably easy to get to 10¹³ and the current known search-limit is around 10¹². The (heuristically) expected number of Wilson primes on that interval is $\log\left(\frac{13}{12}\right) \approx 8%$ , which for me is still worth the shot. However, at some point on one has to think if the odds are too low...

Slight nitpick. The use of percentage here is wrong. A percentage
represents a faction with respect to some other value. The expected
number (which is an absolute number) of Wilson primes up to N is
~C loglog(N), giving .08C as the number of expected primes in [1e12, 1e13]
for some constant C.

I have never seen a strong argument that gives the value of C. Is it 1??

2011-09-09, 12:38	#51
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 3³×239 Posts	It will be faster; the interval parameter is used in two places in the software, in one place min(interval length, number of primes) is relevant, and in the other it isn't. Compare the timings in my posts http://www.mersenneforum.org/showpos...6&postcount=12 and http://www.mersenneforum.org/showpos...5&postcount=35 in both of which the interval is larger than the number of primes in the range. To compare: Code: interval RAM time slices 1e8 3.647 79427.6 3 2e7 1.904 97210.0 3 1e7 0.983 126835.4 4 4e6 0.397 200194.4 11 (this is with wilsontest.c linked against gmp-5; I am rerunning one parameter choice with wilsontest2.c linked against mpir-2.4) Last fiddled with by fivemack on 2011-09-09 at 14:07

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

2011-09-09, 00:00	#49
Jeff Gilchrist Jun 2003 Ottawa, Canada 3×17×23 Posts	Some results with different intervals: interval=50000128 Done the st=71000000000-en=72000000000 interval. Time=57585 sec. interval=5000192 Done the st=72000000000-en=73000000000 interval. Time=111822 sec. Huge difference in speed with those intervals. Testing 75000064 right now.