mersenneforum.org Octoproths
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2006-01-13, 20:23   #254
smh

"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts

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

 2006-01-14, 21:16 #255 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 27568 Posts "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
2006-01-15, 23:16   #256
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2·3·11·23 Posts
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.

or see the attachment for the c code.

Ps. Thanks for Greenbank, I've mainly implemented his string program!
Attached Files
 octo_5_0.txt (14.6 KB, 235 views)

 2006-01-16, 11:20 #257 Greenbank     Jul 2005 2·193 Posts All Dodecaproth discussions moved to a new thread:- http://www.mersenneforum.org/showthread.php?t=5358 This thread remains for further discussion on Octoproths.
 2006-01-16, 19:29 #258 robert44444uk     Jun 2003 Oxford, UK 1,979 Posts Latest Executables Can we move Robert G's latest executables to a new thread? Regards Robert Smith
 2006-01-16, 20:31 #259 robert44444uk     Jun 2003 Oxford, UK 1,979 Posts Aiaia Sorry guys, should have checked "how to help" first. Ignore this and last post. Regards Robert Smith
 2006-01-17, 12:17 #260 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 101111011102 Posts 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.
 2006-01-17, 19:15 #261 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 2×3×11×23 Posts 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
 2006-01-19, 11:53 #262 Greenbank     Jul 2005 2×193 Posts 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.
 2006-01-19, 12:44 #263 Greenbank     Jul 2005 2×193 Posts 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).
2006-01-19, 12:59   #264
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2·3·11·23 Posts

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.

 Similar Threads Thread Thread Starter Forum Replies Last Post ValerieVonck Octoproth Search 100 2007-02-16 23:43 ValerieVonck Octoproth Search 0 2007-02-14 07:24 Greenbank Octoproth Search 15 2006-01-20 16:29 jasong Software 1 2005-05-10 20:08

All times are UTC. The time now is 17:59.

Sun Nov 28 17:59:06 UTC 2021 up 128 days, 12:28, 0 users, load averages: 1.33, 1.66, 1.56