[RC5] ogr percentage done - WHY impossible?

Dan Oetting dan_oetting at uswest.net
Thu Mar 15 11:55:12 EST 2001

on 3/14/01 2:58 PM, Stephen Garrison wrote:

>On Wed, 14 Mar 2001, TimO wrote:
>> Actually, because there exist an infinite number of stubs (yes, even
>> an infinite number of the 6-stubs we start with), I would say that
>> we are 0% done and will remain there until (if) we find a shorter
>> 25-node ruler.  We may be performing this test on a 200Ghz laptop.
>Actually there can't be an infinite number of stubs. Once we find a valid
>ruler (whether or not it is of minimum length makes no difference). It
>gives us an upper bound on the length of of the ruler. There is a finite
>number of cominations of 25 (for OGR-25) integers that will add up to a
>number less than our first ruler's length. An extremely rough estimate of
>the maximum number of possibly smaller rulers would be N choose 25
>(combinatorics), where N is the length of our current upper bound ruler.
>An extremely rough estimate of the max number of stubs would be N choose
>Reasoning: Since N is the length of our initial guess, the maximum length
>between any two points on any other ruler would be N (otherwise we would
>have a length greater than N and therefore be longer than our initial
>guess and could not be the optimal ruler) (and actually I guess you could
>reduce the max dist. between pts because every other distance must be
>atleast 1 unit long). Picking any number between 1 and N twice would mean
>we have two ways of measuring the same distance and we would not have a
>golomb ruler. Since I don't remember if order matters in OGR it might
>actually be the number of permutations of picking 6 (for the stubs)
>numbers out of N numbers. However, this still results in a finite (but
>large) number of stubs and rulers.

The upper bound on the length of an OGR isn't just a guess but is the 
best known ruler with a given number of marks. There are tests that can 
determine if a stub could lead to valid shorter ruler or should be 
discarded. First of all, the stub itself must be golomb. The remaining 
marks in the ruler must also form a golomb ruler and it cannot be shorter 
than the known optimal optimal ruler for the remaining number of marks.

Since we don't want to waste time on reflections we choose to deal only 
with the rulers whose first half is shorter than the second half. The 
ruler segment from the end of the current stub to the center must also be 
golomb and cannot contain any of the distances used in the first stub. 
The client uses a table of the shortest known segments for any set of 
forbidden small distances to determine if the stub will fit.

The client searches by adding a mark to the current stub. For each length 
of the new mark that passes all the tests a new stub is created and the 
search continues recursively. When all extensions to the current stub 
have been tested or rejected work continues on the previous stub branch.

The total number of 6-stubs that are valid for OGR-24 is somewhere around 
50 million if I remember correctly. The difficulty of verifying each stub 
will depend on how early the various tests cut off the recursion 
branches. The biggest factor for stub difficulty will be the length of 
the stub. Shorter stubs have less constraints and will take longer to 
process. The longest stubs will hit most of the cutoffs very soon so will 
take almost no time to process.

It would be possible to estimate the difficulty of each stub from it's 
length and other secondary factors. To generate the estimate formula the 
master server would need to distribute stubs chosen randomly from the 
available pool. The results from processing these stubs would be used to 
tune the estimation function. As more stubs are processed the estimates 
of stub difficulty and total processing time will become more accurate. 
Of course, for the subsequent verification pass we will already know 
exactly how long it took the first time to process each stub.

-- Dan Oetting
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest

More information about the rc5 mailing list