hewgill.com OGR Project Search

distributed.net OGR Project

Currently the OGR code is based on the GARSP 5.13 code of the original OGR-21 effort. There is a new version (GARSP 6.00) available with some further optimizations, but I have not merged that code in yet.

Because the upcoming DES contests are consuming the rest of the distributed.net resources at the moment, we will not see the OGR project start until some time after DES-III has been completed.

What are Golomb Rulers anyway?

A Golomb ruler is a way to place marks along a line such that each pair of marks measures a unique linear distance. Here is a Golomb ruler with five marks:

| |     |         |   |
0 1     4         9   11

The number below the mark is the distance from the left edge. The length of this ruler is 11, and it happens to be one of the two shortest such rulers with five marks. The other ruler has marks at positions 0, 3, 4, 9, and 11. (The mirror images of these two rulers, 0, 2, 7, 10, 11 and 0, 2, 7, 8, 11, are also optimal Golomb rulers. Usually just one of each mirror-image pair is mentioned.)

You can check that the above ruler is indeed Golomb by writing out a table of all the pairs of marks and their respective distances:

Mark1  Mark2  Distance
-----  -----  --------
  0      1       1
  0      4       4
  0      9       9
  0      11      11
  1      4       3
  1      9       8
  1      11      10
  4      9       5
  4      11      7
  9      11      2

Note that there are no duplicated distances in the third column. There is also no distance 6, but that is okay because Golomb rulers don't have to measure each distance, only distinct distances.

The goal of "optimizing" Golomb rulers is to get them as short as possible, while not duplicating any measured distances. The two 5-mark rulers above are optimal.

Golomb rulers are usually characterized by their differences, rather than absolute distances as in the above diagram. So the above ruler would be 1-3-5-2 (sometimes this is written as 0-1-3-5-2 but the leading zero is often dropped).

The current best known 21-mark ruler is the following:

2-22-32-21-5-1-12-34-15-35-7-9-60-10-20-8-3-14-19-4

James B. Shearer has compiled a list of all the best known Golomb rulers up to 150 marks. If you're comparing rulers, note that the 21-mark ruler listed on James' page is the mirror image of the one above.

How the OGR Search Works

The approach used by the OGR search code is a depth-first recursive tree traversal. The following is a description of an exhaustive tree traversal with no optimizations.

At each stage, a new mark is added some distance past the end of the ruler. If this mark causes a duplicate distance to be measured, the mark is moved to the right by one unit and it is checked again. If the mark moves too far to the right, such that we can't possibly fit the next marks in the remaining length (remember we already know the length of the best-known ruler), then the search backtracks to the previous level. If the newly placed mark satisfies the Golomb-ness requirements, the search proceeds to the next mark along the ruler.

The most important optimization is in the placing of the "next" mark. Through clever manipulation of bitmaps representing tables of distances, we do not need to actually check each new mark position. Rather, the bitmaps tell us where new marks can be placed that already satisfy the Golomb-ness requirements.

The other important optimization is the decision about whether the current ruler is too long or not. By detecting that the ruler so far cannot possibly be part of a ruler shorter than the current best known, we can eliminate a lot of unnecessary searching.

OGR and RC5/DES Compared

The process of searching for an Optimal Golomb Ruler differs somewhat from searching for an encryption key. The following table compares various aspects of the two projects.