Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.albasani.net!newsfeed1.swip.net!npeer03.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!post01.iad.highwinds-media.com!newsfe14.iad.POSTED!00000000!not-for-mail From: seeWebInstead@rem.intarweb.org (Robert Maas, http://tinyurl.com/uh3t) Errors-To: ErrorsToHere@YahooGroups.Com X-Spam-This: SpamCopies@YahooGroups.Com X-Twitter: CalRobert Newsgroups: comp.programming,comp.theory,sci.math,comp.graphics.algorithms Subject: Re: Worst Case Greedy Walk References: Message-ID: Lines: 48 X-Complaints-To: abuse@rawbandwidth.com NNTP-Posting-Date: Sun, 13 Nov 2011 19:52:23 UTC Date: Sun, 13 Nov 2011 11:50:56 -0800 Xref: x330-a1.tempe.blueboxinc.net comp.programming:1038 comp.theory:1373 comp.graphics.algorithms:577 > From: mike fee > 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