20060110, 18:16  #210 
Jul 2005
2×193 Posts 
OK, getting there slowly.
Anyone who wants to participate can you go to: http://octoproth.greenbank.org/cgibin/op_register.cgi You're free to use whatever username you like, but it would make things simpler if you used the same one as here. I'll start adding links to the reservation sections and other bits over the next 24 hours. I'd just like to get people registered (and activated) before this point (otherwise you'll have to wait 1224 hours for activation). There is nothing of any interest on the rest of the site so don't both trying to find it :) EDIT: Note that if you try and login you will get an Internal Server Error page. This is expected! Last fiddled with by Greenbank on 20060110 at 18:26 
20060110, 20:39  #211  
Aug 2005
Brazil
2·181 Posts 
Quote:


20060110, 20:49  #212  
Jul 2005
2×193 Posts 
Quote:
#1 is me (naturally) #2 is robert44444uk #3 is Kosmaj #4 is smh The count at the bottom is for the number of registered/activated users and I haven't activated you lot yet, I'll do this tomorrow when there is a real reason to login :) Although there is no user id I can order the registration requests as I record the time in UTC when they submitted the request. Currently working on a page where you can submit any results_octo.txt files so I can keep a track of what has been done already. That and the simplified reservation system. 

20060111, 09:08  #213 
Jun 2003
Oxford, UK
2^{2}×13×37 Posts 
183
183 proved elusive:
n=183, kmin=1, kmax=5000000000000000, 2482746958136235 183 3193625384492445 183 4034789398236135 183 3401199708474645 183 4064835043967775 183 2768477025806205 183 2769512353017585 183 Regards Robert Smith 
20060111, 10:56  #214 
Nov 2003
2·1,811 Posts 
Exe Times
I did some tests to establish exe times of recent software versions and to suggest (again) a further speedup. All tests were done using n=336, kmin=100T, kmax=111T (11T wide, enough for the first large speed gain due to large range of k), on a 3.6GHz P4, compiled using O2 (implying fomitframepointer ) and march=pentium4 (implying mcpu=pentium4). Here are exe times.
ver. 2.0: 207 sec. ver. 3.0: 197 sec. (145880 PRP tests) ver. 3.5: 194 sec. (131810 PRP tests) Therefore the speedup from 2.0 to 3.0 is not 40% as claimed by R.Gerbicz but less than 5%, while the speedup from 2.0 to 3.5 is about 6.3%. (In case of nonoptimized versions 2.0 is the fastest but they are not of interest any more.) Possibly, the speed up between an unoptimized ver. 2.0 and 3.0 is 40% as indicated by smh but what's the point in comparing unoptimized and optimized versions specially in this kind of hastily written code? Furthermore, I changed the PRP test block in 3.5 so that 8 member numbers of OctoProth are checked in increasing order beginning with 2^nk, then 2^n+k etc. and the time was 179 sec. or 7.7% faster than 3.5. The number of PRP tests was 133136 or 1% more than in 3.5 but that was compensated by their reduced speed as the majority of candidates are eliminated after the first or second PRP test. Finally, it's not so important, but R.Gerbicz is badly mistaken if he thinks that counting PRP tests using mpz_add_ui can be done in 5 cpu cycles per count. It may be 5 if we are incrementing an int variable, but here he is calling a GMP function to add 1 as an unsigned integer to an mpz_t type variable (used in GMP to represent huge numbers). That function first does a number of check and then calls another function to do the addition. The code can be found in file aors_ui.h in GMP source. The correct way to count PRP tests is to increment an int variable within the for(i=0;i<100000;i++) loop and add that one to the total count using mpz_add_ui outside the loop. But as far as I'm concerned I don't need any test counts (except for testing). As I said, I'm grateful to R.Gerbicz for his hard work but I prefer to have all facts right. Last fiddled with by Kosmaj on 20060111 at 10:57 
20060111, 11:15  #215 
Nov 2003
2×1,811 Posts 
New Project
I see that Greenbank suggested a separate/new project for OctoProths. In that case I think we have to think about the following:
Project goals: To find at least one OctoProth for each n, or to find large ones in which case we better skip some n's and possibly check only promising k's. Extensions: QuadroProths, DodecaProths, and HexaProths come to mind, but the last two may be difficult to find. Henri Lifchitz already has a page about bitwins and related chains of primes and many such instances have been found. So we cannot go that way. Anyway, the main feature of OctoProths is the inclusion of the 2^n+k form so we better keep it. Finally, if the new project is created I'd like to propose Robert and Dougy as additional moderators. 
20060111, 12:02  #216  
"Robert Gerbicz"
Oct 2005
Hungary
2×7×103 Posts 
Quote:
Can you try also O1 and O3 switching options, instead of O2? ( but in almost all cases O2 is the fastest among of O1,O2,O3 for an average c code). I've modified an existing code from D.J. Brenstein. These are some timings for mpz_powm(q,three,pr,pr) where pr is a bbit random integer. I ran several repetitions of each instruction, timing each repetition separately. For example 320: 1294592 1246072 1244256 1244300 1244096 1243940 means that 6 consecutive mpz_powm() instructions took 1294592 cycles, 1246072 cycles, and so on. If you know your computer's speed, my is 1.7 GHz, means that my computer can do 1.7*10^9 cycles in one sec., so I can do about 1365 prp tests in one sec. for 320 bit random integers. Note that it is very possible that you get better time for this, because in general case P4 is better than my P4 Celeron. I've attached the bench program. Can you run this on your computer, and post the timings! It implied for me that for some very bad cases ( if n>350 and if there are very lot of prp tests for that n value ) the prp testing requires more time than sieving!!! But in almost all cases we are testing for n<300 for these n values sieving is faster, and it'll be more faster, if I'll rewrite. So don't worry. Code:
64: 36348 22420 21692 21624 21452 21660 80: 97508 83412 82356 82168 82128 82020 96: 53376 48020 47496 47220 47460 47324 112: 73896 69680 69232 68904 69032 69108 128: 89484 86992 86996 86632 87096 86716 160: 138756 132980 132460 132424 132356 132324 192: 202692 195040 194576 194504 194304 194716 224: 659460 547164 546020 545964 546876 545708 256: 785860 779032 779512 778792 779372 779408 320: 1294592 1246072 1244256 1244300 1244096 1243940 384: 1860616 1856972 1856716 1853796 1856840 1882112 448: 1631732 1623040 1623080 1622396 1622516 1622940 512: 2061828 2055744 2054800 2054092 2054496 2053936 640: 4838112 4325892 4317952 4315264 4317964 4316268 768: 10480624 10320160 15180664 10293436 10267228 13703984 896: 16108304 14426240 14442584 14416000 14557768 14324872 1024: 14130452 14056784 14603076 14064708 40966672 14113224 Last fiddled with by R. Gerbicz on 20060111 at 12:14 

20060111, 12:17  #217  
Jun 2003
2^{3}·607 Posts 
Quote:


20060111, 13:03  #218  
Aug 2005
Brazil
552_{8} Posts 
Quote:


20060111, 13:34  #219  
Jul 2005
2·193 Posts 
Quote:
I think searcing for specific k values would overlap too much with the 15k project. It's best to stick to specific n values and work up from there. Quote:


20060111, 16:40  #220 
"Robert Gerbicz"
Oct 2005
Hungary
2×7×103 Posts 
new octo_3_6 program!
Thank you Kosmaj and axn1, yours suggestion is an algorithmic improvement. I've never thought that the order in Prp testing is important. Here is the new order:
1.: 2^n+k 2.: 2^(n+1)+k , because these are small numbers with very good bit structure 3.: 2^nk 4.: 2^(n+1)k because these are small numbers ( but very bad bit structure) 5.: k*2^n+1 6.: k*2^(n+1)+1 because these has got very good bit structure ( but large numbers ) 7.: k*2^(n+1)1 8.: k*2^n1 because these are large numbers with very bad bit structure ( NOTE: in these two last cases: I've modified the test: 3^(pr+1)==9 mod pr checking, because in this case pr+1 has got very good bit structure, but this is 0 speed up, because these are the last two numbers in the prp checking order). Kosmaj: I've gotten a speed up by 7% for your input parameters ( time has been dropped from 300 to 279 sec. ) Also note that you have got larger speed up as n increases, because the cost of sieving is constant per one number but the time of prp checking is increase. Also note that you'll get more prp tests but on average the cost of 1 test is smaller so you get a speedup in all cases. I've also tested the new program, you get for example a speed up by 2% if n is about 200. Don't worry what is the third, fourth,... numbers in the prp testing order, because the probability that the first two numbers are prp primes is less than 2% if n>200 is true. See my attachment for the c source code. Or download the exe for windows from my homepage: http://www.robertgerbicz.tar.hu/octo_3_6.exe Last fiddled with by R. Gerbicz on 20060111 at 16:44 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Small Primes for Octoproths <= 155  ValerieVonck  Octoproth Search  100  20070216 23:43 
Found Octoproths  Range Archive  ValerieVonck  Octoproth Search  0  20070214 07:24 
Number of octoproths per n  Greenbank  Octoproth Search  15  20060120 16:29 
Need help with NewPGen(octoproths)  jasong  Software  1  20050510 20:08 