mersenneforum.org  

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

 
 
Thread Tools
Old 2006-01-10, 18:16   #210
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2×193 Posts
Default

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
Greenbank is offline  
Old 2006-01-10, 20:39   #211
fetofs
 
fetofs's Avatar
 
Aug 2005
Brazil

2·181 Posts
Default

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!
fetofs is offline  
Old 2006-01-10, 20:49   #212
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2×193 Posts
Default

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.
Greenbank is offline  
Old 2006-01-11, 09:08   #213
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

22×13×37 Posts
Default 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
robert44444uk is offline  
Old 2006-01-11, 10:56   #214
Kosmaj
 
Kosmaj's Avatar
 
Nov 2003

2·1,811 Posts
Default 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
Kosmaj is offline  
Old 2006-01-11, 11:15   #215
Kosmaj
 
Kosmaj's Avatar
 
Nov 2003

2×1,811 Posts
Default 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.
Kosmaj is offline  
Old 2006-01-11, 12:02   #216
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×7×103 Posts
Default

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
File Type: txt bench.txt (1.1 KB, 91 views)

Last fiddled with by R. Gerbicz on 2006-01-11 at 12:14
R. Gerbicz is offline  
Old 2006-01-11, 12:17   #217
axn
 
axn's Avatar
 
Jun 2003

23·607 Posts
Default

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.
axn is online now  
Old 2006-01-11, 13:03   #218
fetofs
 
fetofs's Avatar
 
Aug 2005
Brazil

5528 Posts
Default

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!!!!!
fetofs is offline  
Old 2006-01-11, 13:34   #219
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2·193 Posts
Default

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).
Greenbank is offline  
Old 2006-01-11, 16:40   #220
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×7×103 Posts
Default 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.
Or download the exe for windows from my homepage: http://www.robertgerbicz.tar.hu/octo_3_6.exe
Attached Files
File Type: txt octo_3_6.txt (11.7 KB, 87 views)

Last fiddled with by R. Gerbicz on 2006-01-11 at 16:44
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 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

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