mersenneforum.org Octoproths
 Register FAQ Search Today's Posts Mark Forums Read

 2006-01-10, 18:16 #210 Greenbank     Jul 2005 2×193 Posts OK, getting there slowly. Anyone who wants to participate can you go to:- http://octoproth.greenbank.org/cgi-bin/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 12-24 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 2006-01-10 at 18:26
2006-01-10, 20:39   #211
fetofs

Aug 2005
Brazil

2·181 Posts

Quote:
 Originally Posted by Greenbank OK, getting there slowly. Anyone who wants to participate can you go to:- http://octoproth.greenbank.org/cgi-bin/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.
Yay! I'm #1!

2006-01-10, 20:49   #212
Greenbank

Jul 2005

2×193 Posts

Quote:
 Originally Posted by fetofs Yay! I'm #1!
You're #5 actually, but that's still good (and it's prime!).

#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.

 2006-01-11, 09:08 #213 robert44444uk     Jun 2003 Oxford, UK 22×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
 2006-01-11, 10:56 #214 Kosmaj     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 speed-up. 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 P-4, compiled using -O2 (implying -fomit-frame-pointer ) 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 speed-up from 2.0 to 3.0 is not 40% as claimed by R.Gerbicz but less than 5%, while the speed-up from 2.0 to 3.5 is about 6.3%. (In case of non-optimized 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^n-k, 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 2006-01-11 at 10:57
 2006-01-11, 11:15 #215 Kosmaj     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.
2006-01-11, 12:02   #216
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2×7×103 Posts

Quote:
 Originally Posted by Kosmaj 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^n-k, then 2^n+k etc. and the time was 179 sec. or 7.7% faster than 3.5.
OK I'll see it again, I think you've got right. ( before I've tested your suggestion only for very small n values ).
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 b-bit 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
Attached Files
 bench.txt (1.1 KB, 91 views)

Last fiddled with by R. Gerbicz on 2006-01-11 at 12:14

2006-01-11, 12:17   #217
axn

Jun 2003

23·607 Posts

Quote:
 Originally Posted by Kosmaj 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^n-k, 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.
Can you change the testing sequence to 2^n+k, 2^(n+1)+k,2^n-k,2^(n+1)-k, etc...? The reason is that the "+" forms will have large runs of 0's in their binary, which could lead to faster exponentiation compared to "-" forms. OTOH, "-" forms requires one less squaring; so it could still end up slower. Would be interesting to find out, though.

2006-01-11, 13:03   #218
fetofs

Aug 2005
Brazil

5528 Posts

Quote:
 Originally Posted by Greenbank You're #5 actually, but that's still good (and it's prime!). #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.
Oh.... I'm prime!!!!!

2006-01-11, 13:34   #219
Greenbank

Jul 2005

2·193 Posts

Quote:
 Originally Posted by Kosmaj 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.
There are several goals, and people participating will be able to contribute to whichever one they want:
• Finding at least 1 Octoproth for each value of n
• Finding all Octoproths for an n (working on the OEIS sequence)
• Finding as many Octoproths as possible

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:
 Finally, if the new project is created I'd like to propose Robert and Dougy as additional moderators.
Indeed, I had planned on doing this (if we get the forum).

2006-01-11, 16:40   #220
R. Gerbicz

"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^n-k
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^n-1 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.
Attached Files
 octo_3_6.txt (11.7 KB, 87 views)

Last fiddled with by R. Gerbicz on 2006-01-11 at 16:44

 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 14:16.

Fri Feb 26 14:16:26 UTC 2021 up 85 days, 10:27, 0 users, load averages: 2.77, 2.60, 2.21