Groups | Search | Server Info | Keyboard shortcuts | Login | Register

Groups > comp.programming > #1385

Re: Worst Case Greedy Walk

Cross-posted to 4 groups.

Show all headers | View raw

> From: "INFINITY POWER" <infin...@limited.com>
> > ... 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.

I take it "INFINITY POWER" has no quibble with using exact
rationals to *check* the solution the other person proposed to
verify it at least satisfies the premises that the points were
sequenced per the rule that the closest unused point is always
selected next?

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

> LOL!  have you ever used this approach to "defeat rounding error"?

In 2004 I started writing software to use rational interval
arithmetic, and created a set of printouts of various test runs.
Then I posted links to these printouts. But nobody ever showed any
interest. If you want to be the first to take a look:
  http://www.rawbw.com/~rem/IntAri

> You might find you need unbounded length (infinitely big) integer
> coefficients for rationals to be more precise than rounded reals.

The method is to use a small precision to see whether two intervals
overlap or are distinct. If distinct, you are done already. If they
overlap, increase precision and recompute, thus narrowing each
interval, and check whether they still overlap or are now distinct.
Thus you have no a priori bound on precision, but you never use
much more precision that is absolutely needed to get a definitive
answer.

One problem: If you are computing exactly the same mathematical
value by two different methods, no matter how accurately you
compute the two values in parallel, the intervals will *always*
overlap, and thus the loop of trying again with more precision will
never terminate.

So you need some sort of heuristic that pauses the loop after a
while to see if maybe you can mathematicall prove the two methods
are in fact computing the exact same value. Ideally you timeshare
two processes, one of which increases precision to prove by direct
calculation that the two values are different, and one which tries
to prove mathematically that the two values are identical.
Unfortunately Goedel proved that there are some mathematical
questions that are true but unprovable. Fortunately for the problem
at hand, sums of square roots that are EQUAL are in fact PROVABLY
EQUAL. (At least I am pretty sure I read that was true. Rebuttal?)

> Mike's solutions are all wrong anyway, his next closest point is
> not closest at all as I explained.

Simply using exact rational calculations, no interval arithmetic
needed, no repeated calculations with increasing precision, just
using his exact decimal values as exact rational values (numerator
over power of ten), would directly show if he followed the rules or
not, no doubt either way in the result.

> I added a temperature to the annealing javascript program.

Note that you need only exact rational numbers as coordinates in
such a program. Given that fact, you can verify that your trial
paths follow the rules, and then use a fixed precision of interval
arithmetic when computing the sum of segment lengths. If intervals
don't overlap, you know one path is definitely better than the
other. If they do overlap, you have to retain both as possibly best
solutions for the moment, until you improve the fixed precision to
make the intervals no longer overlap. When you have more than two
possibly-best solutions, i.e. A overlaps B, and B overlaps C, it
might be that A doesn't overlap C, so that A or C can be
eliminated, leaving 2 instead of 3 possibly-best paths. When you
have appx. ten possibly-best paths, any pair overlapping, then
maybe it's time to crank up the precision to reduce the amount of
overlapping and thus eliminate some of the paths.

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