mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > Octoproth Search

 
 
Thread Tools
Old 2006-01-13, 20:23   #254
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts
Default

Quote:
Originally Posted by Greenbank
We're both right. ;-)

axn1's program still outputs those values, otherwise Templus would not know them to pass them through PFGW. octo 4.5 (and previous versions) does not even output these values as possible octoproths.

And yes, Templus forgot to add the last 4 cases to the ABC line.
axn's program never claimed those numbers to be octoproths. The program just 'sieved' the range without doing a single prp test. The whole input file (hundred thousends of numbers on a large range) had to be prp tested with another program, like (win)pfgw
smh is offline  
Old 2006-01-14, 21:16   #255
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

26118 Posts
Default "Small project"

I would like to propose a "small project":
take my octo_4_5 program, only the sieving part from c to assembly ( in sieving part don't replace gmp instructions by assembly ), because prp checking is in Gmp and that is quite efficient. Note that I've never written assembly program. I think it isn't very hard, see my code there is only such an instructions like:
for, while, if, else , --, ++, -, +
There is only one modular multiplication per sieving prime. It's cost isn't large, but put this also to assembly, if you can do.

I think we can gain about 10%-20% speed up only, because most of the instructions is only addition and I've highly unrolled the for cycle also in a cache friendly way: see b[j]=0,b[j+A1]=0,b[j+A2]=0,b[j+A3]=0,b[j+A4]=0,b[j+A5]=0,b[j+A6]=0,b[j+A7]=0;

Ps. I don't see any further improvement in the sieving code, it is very optimized in c, put it to assembly.
This octo program is the fastest program that I've ever written in c.
Perhaps I'll rewrite some part of the prp checking code.

Last fiddled with by R. Gerbicz on 2006-01-14 at 21:22
R. Gerbicz is offline  
Old 2006-01-15, 23:16   #256
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

13×109 Posts
Default octo_5_0 program

Returning to octo program:
I've implemented the tricks, what I've used for dodeca program. On some very critical ranges it is faster by about 5% than previous version.
Now you can type: ( use big T )
octo_5_0 150 42T 647T
if you want to search n=150 from 42*10^12 to 647*10^12
Note that you can type also octo_5_0 150 42000000000000 647000000000000
and note if you type decimals that are not divisible by 10^12, then I redefine these: rounding down for kmin and rounding up for kmax, so these will be divisible by 10^12. So if you type:
octo_5_0 150 42760000000000 169120000000000
Then after redefinition you will get on the screen:
n=150, kmin=42T, kmax=170T, version=5.0, here T=10^12

It won't increase the time because it means that you'll search maximum a 2T larger interval, but this is very easy for octo program.

I hope this is clear for everybody, but you can ask.

You can download exe from: http://www.robertgerbicz.tar.hu/octo_5_0.exe

or see the attachment for the c code.

Ps. Thanks for Greenbank, I've mainly implemented his string program!
Attached Files
File Type: txt octo_5_0.txt (14.6 KB, 160 views)
R. Gerbicz is offline  
Old 2006-01-16, 11:20   #257
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2×193 Posts
Default

All Dodecaproth discussions moved to a new thread:-

http://www.mersenneforum.org/showthread.php?t=5358

This thread remains for further discussion on Octoproths.
Greenbank is offline  
Old 2006-01-16, 19:29   #258
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

24·7·17 Posts
Default Latest Executables

Can we move Robert G's latest executables to a new thread?

Regards

Robert Smith
robert44444uk is offline  
Old 2006-01-16, 20:31   #259
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

24×7×17 Posts
Default Aiaia

Sorry guys, should have checked "how to help" first. Ignore this and last post.

Regards

Robert Smith
robert44444uk is offline  
Old 2006-01-17, 12:17   #260
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

13×109 Posts
Default The smallest octoproth for a given n

I've posted in the octoproth reservation thread that the smallest k value is about 2^n/f(n) Looking the tables in almost every cases the smallest k value is smaller than this prediction. It's a little overestimation, I'll think about it what would be a better estimation. The problem is that if k is small than all 8 eight numbers are also small, so they have got a higher probability that they are primes.
R. Gerbicz is offline  
Old 2006-01-17, 19:15   #261
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

13×109 Posts
Default

Weight of n ( for octoproths ) ( PARI programs )
Code:
w(n)=T=128.0;forprime(p=3,10^4,l=listcreate(8);g=Mod(2,p)^n;h=1/g;\
a=[g,-g,h,-h,2*g,-2*g,h/2,-h/2];a=lift(a);for(i=1,8,listput(l,a[i],i));\
l=listsort(l,1);T*=(1-length(l)/p)/(1-1/p)^8);return(T)
Number of octoproths for a given n ( estimation ):
Code:
f(n)=round(w(n)*2^n/(n*log(2))^8*1/16)
Smallest octoproth's k value for a given n ( prediction ), so it is possible that the smallest k value is
much smaller or larger, this is only an "average" expected k value: ( new estimation! )
Code:
s(n)=d=0.0;c=w(n)/(n*log(2))^8;forstep(i=1.0/2^15,1.0,1.0/2^15,\
d+=c*(2^(i*n)-2^((i-1/2^15)*n))/(1+i)^4;if(d>1.0,return(round(2^(i*n)))));return
If n is about 200 then this is 6 times smaller than my previous estimation, this is very good for the octoproth project. If n is about 300 then this is about 8 times smaller! I hope that now this formula is much better than previous.

Last fiddled with by R. Gerbicz on 2006-01-17 at 19:21
R. Gerbicz is offline  
Old 2006-01-19, 11:53   #262
Greenbank
 
Greenbank's Avatar
 
Jul 2005

38610 Posts
Default

Nice work Robert.

When I get a chance I'll compute your estimations for all n < 500 (if PARI allows this, I know a previous version stopped working around n=140 due to precision limitations).

We can then see how these compare to the number of Octoproths found for the completed ranges.

I've also finished n=55 and I'm just running all of them through PARI to confirm they are all primes. When I have the final number I'll update it.

n=56 is 50% of the way through, only running on one CPU though so it will take another 1.5 days.

I doubt I'll go as far as n=57.

When I start throwing the data into mysql on my website I can also have a page showing lowest k per n, and the estimate that your formula produces. We can see how accurate it is then :-)

I know I'm constantly saying "when the website appears" but I am working on it, just taking longer than I expected plus I had to redesign lots of bits when the idea of Dodecaproths (and hexadeca-, icosa-, etc) came along.
Greenbank is offline  
Old 2006-01-19, 12:44   #263
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2×193 Posts
Default

n=55 results in "Number of Octoproths per n" thread.

Here are the other bits of results_octo.txt (without the 700,000 Octoproths!):

n=55, kmin=0T, kmax=10000T, version=5.0, here T=10^12
Starting the sieve...
Using the first 10 primes to reduce the size of the sieve array
The sieving is complete.
Number of Prp tests=1014929270
Time=132475 sec.

n=55, kmin=10000T, kmax=20000T, version=5.0, here T=10^12
Starting the sieve...
Using the first 10 primes to reduce the size of the sieve array
The sieving is complete.
Number of Prp tests=1012619035
Time=132608 sec.

n=55, kmin=20000T, kmax=30000T, version=5.0, here T=10^12
Starting the sieve...
Using the first 10 primes to reduce the size of the sieve array
The sieving is complete.
Number of Prp tests=1012427473
Time=136325 sec.

n=55, kmin=30000T, kmax=36030T, version=5.0, here T=10^12
Starting the sieve...
Using the first 10 primes to reduce the size of the sieve array
The sieving is complete.
Number of Prp tests=614381871
Time=81683 sec.


Total PRP tests: 3654357649
Total time taken: 483091 (5 days 14 hours 11 mins 31 secs).
Greenbank is offline  
Old 2006-01-19, 12:59   #264
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

13·109 Posts
Default

Quote:
Originally Posted by Greenbank
When I get a chance I'll compute your estimations for all n < 500 (if PARI allows this, I know a previous version stopped working around n=140 due to precision limitations).
You can raise the precision limit by \p
See for example:
(13:52) gp > \p 100
realprecision = 105 significant digits (100 digits displayed)
(13:52) gp >
Don't choose very large precision, because it would slow down the whole computation.
R. Gerbicz is offline  
 

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Small Primes for Octoproths <= 155 ValerieVonck Octoproth Search 100 2007-02-16 23:43
Found Octoproths - Range Archive ValerieVonck Octoproth Search 0 2007-02-14 07:24
Number of octoproths per n Greenbank Octoproth Search 15 2006-01-20 16:29
Need help with NewPGen(octoproths) jasong Software 1 2005-05-10 20:08

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

Fri Nov 27 00:49:08 UTC 2020 up 77 days, 22 hrs, 3 users, load averages: 1.52, 1.56, 1.52

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