[RC5] ogr percentage done - WHY impossible?

Peter Cordes peter at llama.nslug.ns.ca
Wed Mar 14 17:57:56 EST 2001

On Wed, Mar 14, 2001 at 02:05:21PM -0700, 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.

 As others have said, there are only a finite number of stubs that could
possibly be the start of a shorter ruler.  If the stub is longer than the
whole best-known ruler, there's no way any rulers that start with it could
be the best.  (You can do better than that simple test, of course.)  We are
only interested in rulers that could be better than or equal to the best one
currently known, so there are only a finite number of stubs to get through
before we can declare that we are done.  I would like the stats page to show
how far we are through the stubs.

 Some stubs take longer to process than others, but one would expect this to
even out over a large number of stubs.  i.e. I would be surprised if the
total time for the first 10000 stubs was much different from the total time
for the 10000 stubs most recently handed out, or the last 10000 stubs.  (I
have no proof of this, though.  I guess it would be hard to extract the stub
difficulty from the stub completion rate, because the processing power is
changing with time.  If the returned stubs include a count of how many
rulers were checked in them, that might give useable info.)

#define X(x,y) x##y
Peter Cordes ;  e-mail: X(peter at llama.nslug. , ns.ca)

"The gods confound the man who first found out how to distinguish the hours!
 Confound him, too, who in this place set up a sundial, to cut and hack
 my day so wretchedly into small pieces!" -- Plautus, 200 BCE
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