I am pleased to announce the immediate availability of festog, an
all new cruncher to search optimal and near optimal golomb rulers.
Festog is a complete rewrite from scratch but it uses and extends (!)
techniques learned from many previous efforts by different people and
organizations. Festog stands for "FEiris Successor TO Garsp" which is a
hint to its main ancestor, the currently dominant cruncher called "Garry's Adaptation of Rado's Search Priciples".
I started to work on this rewrite in January 2002. In September of 2002
the first working code was previewed internally at distributed.net,
already including a 64bit version and entirely new ways of computing
constraints that limit the backtracking during the search for OGRs.
Now, after more than 2.5 years in the making, I feel that it is time to
share the results with the public.
Festog is now freely available as source code under a BSD license from http://www.feiri.de/ogr/
A number of lessons learned in festog have already been used to enhance
the existing garsp cruncher in dnetc. But festog represents a whole new
platform that can use much more powerful constraints, that make it
possible to skip significant parts of the search space.
I have run a short sample stub 25/3-2-15-26-30-4 to show the difference on my 1.25 GHz PowerBook G4:
dnetc needs 48 minutes to check 54 billion nodes to finish this stub
festog needs 9 minutes to check 7 billion nodes to finish this stub
Unfortunately these powerful constraints make festog incompatible with
the crunchers that are currently in use at distributed.net. Therefore
festog can not be used in dnetc anytime soon. But if you are as excited
about festog as I am, you can send me an email at email@example.com and
participate in a quick (maybe a couple of months) search for nogr20+48