[RC5] Status of OGR-24

Jim C. Nasby decibel at distributed.net
Tue Aug 26 20:17:40 EDT 2003

As indicated on the stats page, we have now searched every OGR-24 stub
that we distributed to the network. There is still more work to be done
before we can declare OGR-24 finished, however.

(If you're unfamiliar with how OGR searches work, you might want to
visit http://n0cgi.distributed.net/faq/cache/281.html)

The issue is that the stub generation for both OGR-24 and -25 has been
constrained very tightly; the 70 mark constraint that is in use is more
appropriate for OGR-21.  In all likelihood if a shorter ruler exists it
would exist in the space we've already searched.  However, we are not
confident that the present search space is sufficiently exhaustive for
scientific purposes.  We've completed the pragmatic search but still
have to fill in the "brute" part of "brute force".

One of the challenges inherent in OGR is that it's not possible to
predict beforehand how long any given stub will take to test.
Accordingly, the total burden of a particular ruler's search is not
predictable.  While counting the number of remaining stubs is easy it is
not a measure of the amount of work which remains, especially since the
remaining stubs are smaller than the stubs that have been searched
to-date. It is safe to say that we're well past 50%, and we're most
likely past 80 or 90%.

Obviously, finding out we're still not done with OGR-24 is a
disappointment to all of us. It's important to realize that the work
that's been done thus far is valid and had to be done. Likewise, while
the 77% shown for OGR-25 right now is also far too optimistic, the
OGR-25 work being done is perfectly valid.

We still have a considerable number of small stubs (length >70 at the
6th mark) which we have not distributed to the network. This is because
most of these stubs would take only minutes or even seconds to complete.
Once we've determined how much work is left to do we will be able to
decide how to complete it. An early estimate indicates that the
distributed.net staff could check the remaining stubs. If this is not
the case we would distribute the work to the network, but we can't do
this until we can 'combine stubs' so that many stubs that would take
minutes to complete could be grouped together.  This is the only way the
network at large could reasonably
process these minute-long stubs.

We are currently working on an improved OGR algorithm. Because of the
work verification process we use, we can not mix the results of the new
algorithm with the results from the current algorithm. We will use the
improved algorithm to finish OGR-24. Once we have checked all OGR-25
stubs with an initial length <=70, we will also use the new algorithm on
Jim C. Nasby, Database Consultant                  jim at nasby.net
Member: Triangle Fraternity, Sports Car Club of America
Give your computer some brain candy! www.distributed.net Team #1828

Windows: "Where do you want to go today?"
Linux: "Where do you want to go tomorrow?"
FreeBSD: "Are you guys coming, or what?"

More information about the rc5 mailing list