[RC5] ogr percentage done - WHY impossible?

Stephen Garrison garrison at ChE.UDel.Edu
Thu Mar 15 11:22:03 EST 2001


On Wed, 14 Mar 2001, TimO wrote:

> >  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.

Is this % for stubs or rulers.

-- 
Stephen Garrison


--
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