[RC5] ogr percentage done - WHY impossible?

TimO hairballmt at mcn.net
Thu Mar 15 23:01:23 EST 2001


Stephen Garrison wrote:
> 
> 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
> 

Actually, it's iterations(roughly node pairs) to check enough rulers to
find the optimal.  Of course as you stated, knowing an upper bound (480
in this case) on the length reduces this by a large amount.  Beginning
with 6-stubs should reduce this even more.

Hmmmm... has anybody else noticed that this 21 node Golomb ruler
displayed
on the ogr page, isn't???  It has two distances of 10. Tsk, tsk.

(0) 2-22-32-21-5-1-12-34-15-35-7-9-60-10-20-8-3-14-19-4

Does anyone wish to fix it??? ;-)

===============
-- Tim
--------------------==============++==============--------------------
   By (the) which (will) we are sanctified through the offering of the
body of Jesus Christ once for all,  And every priest standeth daily
ministering and offering oftentimes the same sacrifices, which can nev-
er take away sins:  but this man, after he had offered one sacrifice for
sins forever, sat down on the right hand of God;  From henceforth ex-
pecting till his enemies be made his footstool.  For by one offering he
hath perfected forever them that are sanctified.

                        -- Hebrews 10:10-14 (KJV)
--
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