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

 2006-01-11, 16:53 #221 Greenbank     Jul 2005 2×193 Posts Good work Robert! These files have been mirrored at:- http://octoproth.greenbank.org/downloads/oc36.c http://octoproth.greenbank.org/downloads/octo_3_6.exe Last fiddled with by Greenbank on 2006-01-11 at 17:01
2006-01-11, 16:59   #222
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

161110 Posts

Quote:
I don' know what you have uploaded, because the size of exe file is too smal. And oc36.txt isn't existing!

[EDIT by Greenbank] Thank you! I've fixed the links and uploaded the correct version of octo_3_6.exe.

Last fiddled with by Greenbank on 2006-01-11 at 17:03

 2006-01-11, 17:01 #223 robert44444uk     Jun 2003 Suva, Fiji 23×3×5×17 Posts Goals I think a useful goal would be to look at the mathematics behind why some n values produce so many octoproths, whilst others seem to produce less. Regarding chains of 3- 4- etc, it is my bet that such chains do exist, but will prove very elusive. Where n is small, the population of k is also small because of the 2^n-k case. I think there is some modular maths that could be applied to perhaps narrow the choice of possible k. We should be looking in the n=30 to 60 range. Of course having the whole possible population of octos for those n vales is essential, as these are the only k that need to be checked! Regards Robert Smith PS congratulations to everyone for making this a "project" and for their hard work in continuing to look for speed ups in software.
2006-01-11, 17:18   #224
axn

Jun 2003

124748 Posts

Quote:
 Originally Posted by Greenbank 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
- Kilobit Octo (I think out-of-reach for single individual but ideal for DC)
- Titanic Octo (Pushing it )
- Cleaning up all n's below a certain level. Currently it's cleaned up till n=45 (64 sounds tough, but feasible; 80 is too much) -- Hopefully the cleanup effort will yield some elusive dodecaproths.

In addition, there is always individual glory and bragging rights -- most Octo, biggest Octo, etc...

Also, somebody could probably try to come up with asymptotic density calculations for Octos and higer forms.

EDIT:- Ooh.. Almost forgot. Generalized Octos!!! With bases other than 2.

For odd base b, k should be even and vice-versa.

Last fiddled with by axn on 2006-01-11 at 17:23

 2006-01-11, 21:53 #225 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 32·179 Posts Warning about octo_4_0 bugs!!! Some time before I've uploaded octo_4_0.exe to my website. I couldn't post the c code because mersenneforum was unavailable. In that time I've tested for some large Range the new program ( before I've tested only for small ranges, for known solutions ) and I've observed that octo_4_0 has got bugs!!! Some solutions has been missed! So delete that file from your computer! Greenbank if you'll get a results text from version 4.0 ( you can find that for each project in that text file ) then consider that it is very very possible that some solutions has been missed. Ps. I've deleted that file from my webpage and there is a warning message about it! Last fiddled with by R. Gerbicz on 2006-01-11 at 22:04
2006-01-11, 23:33   #226
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

32×179 Posts
octo_4_3 program

This new octo program is using now exactly the kmin,kmax range in the sieve, previous versions has oversieved to use a special sieve, now I've rewritten that part, so now there is no oversieve. Note that the speedup is between 0%-25% depending on your range, it isn't easy to give an average rate ( 25% is a theoretic value), and there is also smaller number of prp tests, because there is no redefinition of range.

See my attachment for c code or download the exe for windows from my webpage:http://www.robertgerbicz.tar.hu/octo_4_3.exe
Attached Files
 octo_4_3.txt (13.2 KB, 177 views)

2006-01-11, 23:39   #227
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

32·179 Posts
octo_4_5 program

It is exactly the same as 4.3 version but it'll try to use one more prime in the sieve reduction step, this is value of x in the program. So the speed of this is exactly the same as the speed of 4.3 if it'll use the same x value, but it can be faster for one more prime. Try it for different ranges and different n values. Note that it can be slower than 4.3 !!!

Now magic_constant=10^5, see previous versions: it was started from 2*10^6

See the attachment for the c source or my webpage for the exe file for windows: http://www.robertgerbicz.tar.hu/octo_4_5.exe

Ps: It would be very good if somebody could test for known n values and known ranges the programs!

Note that version 4.0 has got a very serious bug!
Attached Files
 octo_4_5.txt (13.2 KB, 174 views)

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

 2006-01-12, 04:48 #228 tcadigan     Sep 2004 UVic 1068 Posts 171 n=171, kmin=1, kmax=10000000000, version=4.5 Starting the sieve... Using the first 6 primes to reduce the size of the sieve array The sieving is complete. Number of Prp tests=156 Time=1 sec. n=171, kmin=10000000000, kmax=1000000000000000, version=4.5 Starting the sieve... Using the first 10 primes to reduce the size of the sieve array 99180515934675 171 855203637332835 171 42579432483105 171 111420166614855 171 The sieving is complete. Number of Prp tests=15652022 Time=12084 sec.
 2006-01-12, 10:12 #229 Kosmaj     Nov 2003 E2616 Posts Thanks to axn for the feedback and to R.Gerbicz for quick action and many new versions. Four new versions in one day is a little bit too many for me but I never saw ver.4.0 so I tested three versions: 3.6, 4.3, and 4.5. using the same input parameters like before (n=336, k=100-111T). All compiled using -O2 and -march=pentium4. Here are the times: 3.6 ... 179 sec, 133206 PRP tests (the same time like my ver.3.5) 4.3 ... 165 sec, 125962 PRP tests 4.5 ... 171 sec, 125962 PRP tests (the same like 4.3) So I'm now using 4.3. I noticed that the only difference between 4.3 and 4.5 is the size of magic_constant. Maybe 10^5 (now) is not the best value for my test case? Can you change the program so that the constant can be set from the command line. But you will also have to tell us how to use it. Finally, a proposal for a simple new feature: Can you count the number of found OctoProths in one run, and print that at the end. With many numbers on the screen and in the results file it's easy to miss a precious Octo! It's also useful when testing correctness of the program (I use n=52-55 and k<1T). Now I have to count the number of Octos in the results file (90 for n=52, 12 for n=53 etc.) Sorry, but today I didn't have time for other tests (-O1, -O3 and bench.c).
2006-01-12, 11:20   #230
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

32×179 Posts

Quote:
 Originally Posted by Kosmaj 4.3 ... 165 sec, 125962 PRP tests 4.5 ... 171 sec, 125962 PRP tests (the same like 4.3)
It is an impossible timing!!! Because for your input parameters the two versions use the same value of x=8, so the speed is exactly the same +- 1 sec. ( because I've changed only magic_constant and this is only used to determine the value of x). For me the timings were the same 263 sec.

If you reach another breakpoint ( because magic_constant is smaller ), then x is larger by one, so it is possible that you get an improvement ( this is depending on the Range and on n value ), but it is also possible that it'll be slower. I've gotten the two cases on my PC for different input parameters.

It isn't need to modify further magic_constant, because in 4.3 this is 4*10^5, if it would be larger then we get a smaller x value ( or the same ) but this is suboptimal. In version 4.5 this is 10^5, so you'll use the same x value or x+1, if it would be smaller then that isn't optimal, because we are sieving up to 10^5.

Also note that using bench.c isn't very practical in this case, because we are testing very special numbers, and for this mpz_powm instruction is faster by a factor of 2. So probably my program isn't very bad for n<512

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

2006-01-12, 15:45   #231
Greenbank

Jul 2005

2·193 Posts

Quote:
 Originally Posted by Kosmaj so I tested three versions: 3.6, 4.3, and 4.5. using the same input parameters like before (n=336, k=100-111T). All compiled using -O2 and -march=pentium4. Here are the times: 3.6 ... 179 sec, 133206 PRP tests (the same time like my ver.3.5) 4.3 ... 165 sec, 125962 PRP tests 4.5 ... 171 sec, 125962 PRP tests (the same like 4.3)
Hah! BTW, Good work Robert!

Code:
$gcc -m64 -mpowerpc64 -O2 -fomit-frame-pointer oc45.c -o oc45 -lgmp$ ./oc45 336 100000000000000 111000000000000
You can also find the k n values in results_octo.txt file ( These are 3-probable primes )
n=336, kmin=100000000000000, kmax=111000000000000, version=4.5
Starting the sieve...
Using the first 8 primes to reduce the size of the sieve array

The sieving is complete.
Number of Prp tests=125962
Time=82 sec.
Mmmm. Quad 2.5GHz PowerMac G5. Mmmm.

Last fiddled with by Greenbank on 2006-01-12 at 15:46

 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 01:36.

Sat Feb 4 01:36:19 UTC 2023 up 169 days, 23:04, 1 user, load averages: 0.92, 1.27, 1.13