Re: Worst Case Greedy Walk

From	seeWebInstead@rem.intarweb.org (Robert Maas, http://tinyurl.com/uh3t)
Newsgroups	comp.programming, comp.theory, sci.math, comp.graphics.algorithms
Subject	Re: Worst Case Greedy Walk
References	<MPG.291c839290409ff99896b5@news.eternal-september.org> <j8skbl$f86$1@dont-email.me> <MPG.29222115a695e7b29896b7@news.eternal-september.org> <j996jq$obp$1@dont-email.me> <MPG.29230cc6427cda819896b8@news.eternal-september.org>
Message-ID	<REM-2011nov13-001@Yahoo.Com> (permalink)
Date	2011-11-13 11:50 -0800

Cross-posted to 4 groups.

Show all headers | View raw

> From: mike fee <m....@irl.nospam.cri.nz>
> I get all of 0-1, 0-5, and 0-7 to be approximately 0.50383...
> to 5 decimal places (on the crappy calculator on my desk), so at worst
> 0-1 is not jumping "a lot" further than 0-5, or 0-7. In the limiting
> solutions, the nearest neighbour is often only infinitesmally closer
> than the next nearest, so I may have a few round off errors in some
> solutions, but I still believe my solutions are 'approximately' valid.
> I will re-check with extended floats to see if it makes a significant
> difference.

That's a dumb way to do this kind of problem. Since the rational
numbers are dense in the real numbers, for this problem it suffices
to find rational-coordinate solutions. In fact the specific values
you are testing are exact rationals, for example
  0.499849922867556 = 499849922867556/1000000000000000
Given that all coordinates are rational, you can use exact rational
arithmetic to exactly compute square of distance between any two
points, then directly compare square-of-distance to find smallest
such (from last-visited point to unvisited points). No need to
*approximately* compute square-roots at all when verifying that
somebody has indeed correcty selected the nearest unvisited point.

Of course you should use either Common Lisp or some other language
which has exact rational arithmetic built-in, or use some add-on
exact-rational-arithmetic library if you can find one.

The only place you'd need to compute *approximate* square root is
when computing the total path length, and in that case you should
use interval arithmetic instead of shot-in-dark floating-point, to
make sure that your printout doesn't lie about the low-order digit,
and also to compare two different sets of points to verify that one
really does yield a longer path length. If interval arithmetic with
a particular computational precision doesn't show that one set of
points is definitely longer than another, i.e. the error-intervals
overlap, then you know to recompute with better precision, until
the error-intervals no longer overlap.

Suggestion: Continued fractions are a good way to compute
square-root of rational to arbitrary precision, with each iteration
yielding an interval with exact-rational endpoints, thus making it
relatively easy to add up the intervals for the segments within the
path using exact rational arithmetic, as well as comparing the
error-contributions from each segment to see which is contributing
the largest error-interval hence which needs to be iterated one
more continued-fraction step to most effectively shrink the total
error-interval.

Google-groups-search-key: imtrgfdi

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Worst Case Greedy Walk Andrew Tomazos <andrew@tomazos.com> - 2011-10-31 08:11 -0700
  Re: Worst Case Greedy Walk William Elliot <marsh@rdrop.com> - 2011-10-31 21:24 -0700
    Re: Worst Case Greedy Walk Andrew Tomazos <andrew@tomazos.com> - 2011-11-01 12:41 -0700
      Re: Worst Case Greedy Walk William Elliot <marsh@rdrop.com> - 2011-11-01 20:32 -0700
  Re: Worst Case Greedy Walk "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2011-11-01 07:21 +0000
    Re: Worst Case Greedy Walk James Dow Allen <jdallen2000@yahoo.com> - 2011-11-01 00:45 -0700
      Re: Worst Case Greedy Walk Andrew Tomazos <andrew@tomazos.com> - 2011-11-01 13:02 -0700
        Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-02 09:57 +1300
          Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-03 10:55 +1300
            Re: Worst Case Greedy Walk "INFINITY POWER" <infinity@limited.com> - 2011-11-03 09:39 +1000
              Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-07 17:09 +1300
                Re: Worst Case Greedy Walk "INFINITY POWER" <infinity@limited.com> - 2011-11-08 04:04 +1000
                Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-08 09:54 +1300
                Re: Worst Case Greedy Walk seeWebInstead@rem.intarweb.org (Robert Maas, http://tinyurl.com/uh3t) - 2011-11-13 11:50 -0800
                Re: Worst Case Greedy Walk "INFINITY POWER" <infinity@limited.com> - 2011-11-14 06:58 +1000
                Re: Worst Case Greedy Walk seeWebInstead@rem.intarweb.org (Robert Maas, http://tinyurl.com/uh3t) - 2012-03-29 00:28 -0700
                Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-08 11:44 +1300
                Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-08 14:28 +1300
    Re: Worst Case Greedy Walk Andrew Tomazos <andrew@tomazos.com> - 2011-11-01 12:46 -0700
      Re: Worst Case Greedy Walk "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2011-11-02 08:16 +0000
        Re: Worst Case Greedy Walk Patricia Shanahan <pats@acm.org> - 2011-11-02 05:27 -0700
  Re: Worst Case Greedy Walk Graham Cooper <grahamcooper7@gmail.com> - 2011-11-01 14:29 -0700
    Re: Worst Case Greedy Walk Graham Cooper <grahamcooper7@gmail.com> - 2011-11-01 15:30 -0700
    Re: Worst Case Greedy Walk Steve Thompson <thomps2048@yahoo.ca> - 2011-11-01 20:56 -0400
  Re: Worst Case Greedy Walk quasi <quasi@null.set> - 2011-11-02 01:55 -0500
    Re: Worst Case Greedy Walk quasi <quasi@null.set> - 2011-11-02 18:24 -0500
  Re: Worst Case Greedy Walk "INFINITY POWER" <infinity@limited.com> - 2011-11-02 17:49 +1000

csiph-web