[RC5] ogr percentage done - WHY impossible?

TimO hairballmt at mcn.net
Wed Mar 14 18:14:19 EST 2001


Peter Cordes wrote:
> 
> 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

Yes, but it is still a _huge_ space to check.  Worst case scenario where
the known ruler is optimal:

completed = :		3,574,935,297,000,000,000
			/
~exhaustive search = :	88,817,841,970,012,523,233,890,533,447,265,625
			*
			100
			=
			4.0250193 X 10^-15 % finished

Note that an exhaustive search for an optimal ruler is really N times 
worse.

===============
-- Tim
--------------------==============++==============--------------------
--
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