:: 16-Aug-2004 04:11 GMT (Monday) ::
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 nogr@feiri.de and participate
in a quick (maybe a couple of months) search for nogr20+48 using festog.