Optimal Golomb Ruler With 5 Marks
Download Software Get a New Stub Current Progress

Email Us
About this project Join Mail List Distributed.Net

Other Links

In Search Of The Optimal 20, 21 & 22 Mark Golomb Rulers

In mathematics, the term "Golomb Ruler" refers to a set of non-negative integers such that no two distinct pairs of numbers from the set have the same difference.  Conceptually, this is similar to a ruler constructed in such a way that no two pairs of marks measure the same distance.  An Optimal Golomb Ruler (OGR) is the shortest Golomb Ruler possible for a given number of marks. OGR's have many applications including sensor placements for X-ray crystallography and radio astronomy. However, finding (and proving) OGR's becomes exponentially more difficult as the number of marks increases, and it is for this reason that we have turned to the web for help in finding the OGR's with 20 and 21 marks. If you are interested, we have written an introduction to Golomb rulers.

News & Views

SPECIAL Update
We have written to the listserv mailing group that OGR-23 will be our final OGR from this site.  Since we will most likely complete the OGR-23 search in June, we have decided to make it a little more interesting.  We have written a new client that can be used instead of the existing ones (see http://ogr.virtualave.net/clients/) that not only searches for the OGR-23, but along the way also saves potential good beginnings for higher OGR's such as OGR-24 and OGR-25.  We will use this in an expedited search for the "best" 24 mark ruler we can find before Distributed.Net has to search the entire 24 mark space exhaustively.  If we find a better one than currently exists we can save Distributed.Net singificant effort.  Of course, whoever found the "good beginning" file and sent it in would be credited ... though it may not be known for several weeks after the fact.  If you want to try this out, use the above link to get all the details!

May 1999


When OGR-22 is complete we plan on starting OGR-23. We had hoped that Distributed.Net would already be up and running, but as most our helpers already know there has been some major change going on over there, and it may take a few weeks longer to get up and running. In the meantime, we will start OGR-23 which in total should take about 6 weeks to finish (a lot less than this once Distributed.Net is online with Project Kangaroo!)

The following table shows current progress and estimated workload left to go in trillions (10^12). Estimation of nodes remaining is based on extrapolation from nodes already completed.  For a more current summary, visit the "current progress" link at the top of this page.

  January     February       March      April      May  
  Done   - 60 295 virtually complete! -
Left 600 540 320 virtually none! -

Wow! We are finishing a lot faster than anticipated. Over the April 26 weekend we ran out of stubs never assigned and started reassigning stubs that had not been returned to us for over 3 weeks. We plan on doubling up on all remaining stubs to ensure a timely finish to the OGR-22 search. We anticipate finishing around the end of April.

March 1999

Yes, we finally gave the main page a face lift ... if you're looking for the old "main page" it has been moved to "index98.htm".

Wow ... we are now well into OGR-22 searching.  This was a lot faster then we anticipated, considering we only completed our beta-testing in February.   D.Net is also gearing up, and hopefully this all comes together soon! When the D.Net clients are ready, expect fast completion of not only OGR-22, but OGR-23 and higher as well. In the meantime, feel free to join our preliminary searching at: http://members.aol.com/golomb20/cg-stubs.htm.

January 1999

Beta testing of the current ChoosyGarsp routines were begun in January.

November 26 1998

We're Coming Back REAL SOON NOW!

Sorry for the delay.  But at least we have good news to report.  First, "Distributed.Net" has taken a liking to Golomb Rulers and plans on working on OGR-22 and OGR-23.  With resources like D.Net, these rulers should both be completed in almost no time!  Second, we have been working on the GARSP core preparing it for OGR-22 and higher.  Not only is the external choose file eliminated, but GARSP runs about 5-10 times faster and in just a fraction of its old memory requirements.

We are making some final corrections to the core before general release, so please be patient for another week or two.  In the meantime, if you were one of our key supporters in the prior searches and would like to be emailed when we start up, let us know. (If you are already part of D.Net, just follow their own news pages).

If you helped out on the earlier OGR-20 and/or 21 searches, please note that we will probably look for a few volunteers to try out some preliminary OGR-22 and OGR-21 stubs (to make sure the program runs as expected on various platforms).  Let me know if you want to help us work out the last few kinks!  We expect that D.Net will work their own magic with platform specific optimizations, but we'd like to make sure we've got the basics down OK.

May 1998

The search for OGR-21 has been completed.  The last sub-stub (1-8-18) was submitted at: Fri May 8 10:24:52 1998

In the end we did not find a new ruler ... rather, we proved the existing best known 21 mark was optimal.

SPECIAL Update
The following table shows current progress and estimated workload left to go in trillions (10^12). Estimation of nodes remaining was based on extrapolation from nodes already completed.
Apr May Jun Jul Aug Sep Oct Nov Dec Jan Feb Mar Apr May-8
Done - 9 20 37 48 70 94 116 153 181 223 327 740 912
Left - - - - 1122 1088 972 953 939 914 871 743 240 -
Paul Nord graphed our progress month by month (http://physics.valpo.edu/staff/pnord/node_graph.htm).  Its kinda neat.  To complete the search for OGR-21 took a total of 3467 CPU weeks.  A majority of time consumed was on our first program GVANT, although the newer GARSP program actually searched more space ("nodes").  The final rate of progress on OGR-21 was higher than anticipated due to program improvements, more machines, the TCP/IP server, and faster CPU's.
To celebrate complerting OGR-21, Rick Niles made a real OGR-21 necklace for his girlfriend Julie Nottingham, bringing us back "full circle" to Kris Coolsaet's wierd colored necklaces, which expain how most of the known golomb rulers were discovered!  Don't be surprised if Rick suggests we search for orthogonal ruler pairs (i.e., braclets) next!
Meanwhile we are now preparing to follow up with the OGR-22 search.  It is less likely to find a better ruler than our OGR-21 search ... but could still prove fruitful.  We are also considering other related projects.  So far we have two volunteers for a web-hosted GD and also for TCP hosting.  If you want to offer additional facilities please contact Mark (Golomb20@AOL.com).
Stay tuned till about mid-to-late May for the startup of OGR-22!

April 1998

New!Rick Niles has completed alpha testing of a TCP/IP stub distribution system!  We are now releasing it as a beta version ... which means it has a few known bugs, but is being received very favorably.  Rick has spent a lot of time developing this, and we give him great credit for getting it to beta release this quickly.  As most of us know, the web-based GD is temporarily (?) offline, so we asked Rick to open the TCP/IP for much broader use before he might normally have done so.
Its primary advantage is that you don't have to interact as much -- the program does almost everything by itself now.  Its disadvantage it that you must install it and you must have an internet connection available for the program to report back in and get its next stub (of course, that means that while you were reading this page, the client could have been reporting back in its results and getting its next assignment!)
Rick writes:
The golomb TCP/IP distributor is going beta. You can pick up the new beta version from:
    ftp://axp745.gsfc.nasa.gov/pub/golomb/gd-tcpip-0.1.0.tar.gz

The Golomb TCP/IP Distributor consists of a client program and a server program that communicate over a TCP/IP connection and exchange Golomb ruler stubs. I have set up the server on my computer with some stubs from Mark Garry. If you connect your machine(s) to the Internet and run the client you will be assigned stubs from the server for the garsp program to process. Once the stubs are completed the client will automatically contact the server and exchange the old stubs for new ones. You must have the garsp program working to use this client software.

1) Get the package.
2) Unpack the archive.
3) Edit the Makefile.
4) "make"
5) "./client" (fill out the configuration menu.)
6) Oh and read the README.

I don't have a web page for stats. Hopefully I'll make one someday soon.

Happy Stubbing!
Rick Niles.
James B. Shearer has expanded on Lloyd Miller's list of the Best Known Golomb Rulers to 150 mark rulers. His Golomb Ruler's page lists the sources of the rulers as well as their lengths and includes fortran source code. As a reminder, if you are interested in projective and affine planes and related perfect difference sets, Kris Coolsaet has generated an excellent on-line introduction to them and also provides some code examples (in C++). Check out his weird colored necklaces pages and let him know if you enjoyed your visit!
Choose.c --version 5-- is now available.  It lets you build choose.dat files for MAXBITS=y using choose.dat files you already created for MAXBITS=x (so its faster).  It also allows you to start and stop the run as needed, versus needing to run it all at one time.
GARSP 5.13 64bit code is out! It is about 30 percent faster than the 32 bit version.  We have uploaded the source code, and will follow with some binaries soon.
GARSP 5.13 32bit code is out!  We hope to follow soon with a 64 bit version.  You can link here or read the source code for all the details, but here are some of the highlights:
We are in the midst of uploading new binaries at the File Downloads page.  If the v5.13 binary for your OS is not available yet, check back in a day or so!  Note: the web based GD is not yet set up to handle the 5.13 uploads, so hold onto your 5.13 outputs for a week or so to give David L time to upgrade the GD!!!

March 1998


We reached 300 trillion nodes searched! See the WEM page for updates.  BTW, Greg has added some animated gifs of our progress ... they look nice! (link is on the WEM page).

The long awaited automated Golomb Distributor is being tested as you read this.  Start downloading new stubs to work on via CGI scripts at Golomb GD Central.  Next up...a TCP/IP version(?).  But don't hold your breath (its still in alpha test mode, and then comes beta testing) ... try out the web based GD now!

We continue to add clients for different platforms. The latest are an AIX Binary compiled by John Caldwell and MultiThreaded clients for BeOS and Solaris compiled by Chuck Sanders.

February 1998

We have a new "client" available to find golomb rulers (and optimal golomb rulers).  It is called GARSP, and takes a radically different approach than GVANT.  Using bitmaps to store mark locations and spans, it is capable of running about 2-3 times faster than GVANT, or 5 times faster if you have a 64 bit OS! Unfortunately, it also requires additional RAM.  We've built a version that allows YOU to decide how much RAM it can use (the more the merrier, but it may interfere with your other "real life" programs). Besides being faster, GARSP saves more frequently -- for those really hard stubs!  See the new download page for more details. As current users complete assignments, we'll be asking you to transition to the new client if possible.

Brian Hayes published "Computing Science: Collective Wisdom" in the March/April edition of American Scientist ("The magazine of Sigma Xi, The Scientific Research Society"). Among other projects such as SETI and GIMPS, he mentions our Golomb Ruler project. Thanks Brian! No online link yet ... so go visit your local library (yes ... they still exist :)

A.Dollas, W.T.Rankin and D.McCracken just published "A New Algorithm for Golomb Ruler Derivation and proof of the 19 Mark Ruler" in IEEE Transactions On Information Theory (January, 1998, Volume 44, Number 01).  You may want to take a read through it ... our new GARSP client originated with McCracken's DIST/LIST bit vector concept :)

Though not related directly to Golomb Rulers, congratulations to Torbjörn Alm for winning the Contest to Predict Sizes of Mersenne Factors ! (Gee ... maybe we need a contest!) Torjörn's been working with us as well as the Mersenne project from near the beginning of the OGR-21 search.

December 1997

A sad note: Our condolences go to the family of Marc Zimmerman. Marc, who joined our effort in September and was most recently working on stub 2-19 passed away on December 3.

Are you using UNIX and want more control over lowering a job's priority so that it doesn't interfere with other jobs? Then download loadwchr.txt and modify the script as needed for your own use.

November 1997

Are you a new user wondering what the "send.dat" file is supposed to look like? Wondering how fast an Alpha runs these things? David Landgren has a live link to one of his runs at A Golomb Stub Run

Win-95/NT executables with priority set to "idle" are now available that only consume CPU when your system is otherwise ... (you got it) ... idle. If you are running any normal priority jobs (such as WORD or EXCEL) this GVANT will use almost _no_ clock cycles, so you can leave it running all the time! :) And if your CPU is otherwise idle, this VC5 GVANT can run almost 1/3 more nodes/second than DJGPP's (wow). Thanks to all those who previously tried to convince us switch to a native client and to Matt Thomlinson who added the priority="idle" code. FYI, Matt compiled this version using VC5 switches /Zp4 /O2 /Ob2.

A small problem with the MAC client has been noted. On long runs, the client priority may slow significantly if left running unattended in the foreground (just nudge the mouse or touch a key and it returns to full speed). John Bafford is working on getting this corrected.

Geoffrey Faivre-Malloy wrote Distributed Computing in this month's BoardWatch. Interesting reading ;~)

October 1997

We've got a new MAC client! John Bafford has been kind enough to recompile Uwe Falck's earlier client. We have a self extracting archive version here called golomb.sea but visit John's site to make sure you have his latest!

September 1997

We've added a link (timing.htm) if you are interested in seeing how your GVANT run times compare to configurations used by other users. You are free to add an entry (you can stay anonymous if you want) or to simply use the table to see if you can configure your system any better.

August 1997

We would like to welcome any Power MAC users. Uwe Falck has been kind enough to compile a MAC self extracting archive (SEA) for the Power MAC. Although the program uses little memory, at this time it tends to "hog" the system CPU so you may only want to run jobs over weekends, etc.

July 1997

A chart depicting why we believe we will find a better 21 mark ruler is available for viewing. The info for the chart was primarily based on the list of the best known golomb rulers maintained by Lloyd Miller (including some ones he found recently using Cyclic Difference Sets)

Awards(?)

"Geek Site of the Day" (Nov 1, 1996) {Note, the linked site seems to have disappeared in early 1999}

Page Counter ... 999999!