mersenneforum.org  

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

 
 
Thread Tools
Old 2006-01-11, 16:53   #221
Greenbank
 
Greenbank's Avatar
 
Jul 2005

6028 Posts
Default

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

101100010112 Posts
Default

Quote:
Originally Posted by Greenbank
I don' know what you have uploaded, because the size of exe file is too smal. And oc36.txt isn't existing!
You can download those two files and after it upload them.

[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
R. Gerbicz is offline  
Old 2006-01-11, 17:01   #223
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

1,907 Posts
Default 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.
robert44444uk is offline  
Old 2006-01-11, 17:18   #224
axn
 
axn's Avatar
 
Jun 2003

12B616 Posts
Default

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
Some additional goals:
- 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
axn is offline  
Old 2006-01-11, 21:53   #225
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

26138 Posts
Default 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
R. Gerbicz is offline  
Old 2006-01-11, 23:33   #226
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

3·11·43 Posts
Default 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
File Type: txt octo_4_3.txt (13.2 KB, 102 views)
R. Gerbicz is offline  
Old 2006-01-11, 23:39   #227
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

3·11·43 Posts
Default 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
File Type: txt octo_4_5.txt (13.2 KB, 97 views)

Last fiddled with by R. Gerbicz on 2006-01-11 at 23:44
R. Gerbicz is offline  
Old 2006-01-12, 04:48   #228
tcadigan
 
tcadigan's Avatar
 
Sep 2004
UVic

2·5·7 Posts
Default 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.
tcadigan is offline  
Old 2006-01-12, 10:12   #229
Kosmaj
 
Kosmaj's Avatar
 
Nov 2003

70468 Posts
Default

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).
Kosmaj is offline  
Old 2006-01-12, 11:20   #230
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

3×11×43 Posts
Default

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
R. Gerbicz is offline  
Old 2006-01-12, 15:45   #231
Greenbank
 
Greenbank's Avatar
 
Jul 2005

6028 Posts
Default

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
Greenbank 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 03:30.

Wed Dec 2 03:30:05 UTC 2020 up 83 days, 41 mins, 1 user, load averages: 1.64, 1.78, 1.65

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