Message from discussion
Any way around non-reversibility of floating point ops
Path: g2news1.google.com!postnews.google.com!r15g2000prh.googlegroups.com!not-for-mail
From: Peter Seibel <peter.sei...@gmail.com>
Newsgroups: sci.math.num-analysis
Subject: Re: Any way around non-reversibility of floating point ops
Date: Sun, 2 Nov 2008 13:38:11 -0800 (PST)
Organization: http://groups.google.com
Lines: 66
Message-ID: <7317a871-0136-4789-9f85-03cde6e84663@r15g2000prh.googlegroups.com>
References: <7d6c2a14-36f5-426d-9563-b67f70e17b6f@a29g2000pra.googlegroups.com>
<2008110215132116807-gsande@worldnetattnet>
NNTP-Posting-Host: 99.184.207.175
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1225661891 18333 127.0.0.1 (2 Nov 2008 21:38:11 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Sun, 2 Nov 2008 21:38:11 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: r15g2000prh.googlegroups.com; posting-host=99.184.207.175;
posting-account=sqnA8AoAAABGnoBakAKi36u5ll61lgQa
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (Macintosh; U; PPC Mac OS X 10.4; en-US;
rv:1.9.0.3) Gecko/2008092414 Firefox/3.0.3,gzip(gfe),gzip(gfe)
On Nov 2, 11:13=A0am, Gordon Sande <g.sa...@worldnet.att.net> wrote:
> On 2008-11-02 12:30:20 -0400, Peter Seibel <peter.sei...@gmail.com> said:
>
>
>
> > I've got an algorithm for computing the probability of a candidate in
> > the presidential election winning a certain number of elector votes
> > that looks like this (in pseudo-code):
>
> > =A0 define compute-ev-probabilites (state-probs)
> > =A0 =A0 probs =3D make-array 0 .. 538
> > =A0 =A0 probs[0] =3D 1
> > =A0 =A0 foreach state-prob in state-probs
> > =A0 =A0 =A0 =A0fold-into probs state-prob.votes state-probs.probability
>
> > =A0 define fold-into (probs votes prob)
> > =A0 =A0 for i from 538 downto 0
> > =A0 =A0 =A0 probs[i] =3D probs[i] * (1 - prob)
> > =A0 =A0 =A0 if (votes <=3D i)
> > =A0 =A0 =A0 =A0 probs[i] =3D probs[i] + (prob * probs[i - votes])
>
> > So far so good. Now I'd like to add this function which can back out
> > the effects of a single state:
>
> > =A0 define back-out (probs votes prob)
> > =A0 =A0 =A0for i from 0 to 538
> > =A0 =A0 =A0 if (=3D prob 1)
> > =A0 =A0 =A0 =A0 probs[i] (i + votes) < probs.length ? probs[i + votes] =
: 0
> > =A0 =A0 =A0 else
> > =A0 =A0 =A0 =A0 if (votes <=3D i) probs[i] =3D probs[i] - probs[i - vot=
es] * prob
> > =A0 =A0 =A0 =A0 probs[i] =3D probs[i] / (1 - prob)
>
> > Mathematically this works--I've actually implemented this in Common
> > Lisp and when I use arbitrary-precision rational numbers it works
> > perfectly. But when I use floating point numbers the computations in
> > back-out get wildly out of whack. As best as I can tell this is
> > because small errors introduced because (x * y) / y isn't necessarily
> > exactly x get propagated throughout the whole array of probabilities
> > and perhaps amplified by inaccuracies in the subtraction. (I can't
> > just use rationals because I'm actually implementing this in
> > Javascript whose only numeric type is double float.)
>
> > Is there some obvious way to write this so I can still use floating
> > point numbers but have back-out work properly. I'd be happy to trade
> > some precision for reversibility.
>
> > -Peter
>
> If you are doing a lot of manipulations this numers that are 1 - eps
> it may pay to use a bit of symbolic smarts to keep the 1 separate from
> the eps. How to do this "depends". Working through an error analysis
> should tell you where it might help. You would be using the symbolic
> analysis to lower the sensitivity of the computation to error progation.
>
> However since you had to ask one suspects that you may not be familiar
> with doing the error analyses. (Yet another variation on the classic
> comment on the pricing of yachts!)
I'm aware only that one should do an error analysis but have no idea
how to go about it. I was just wondering if there was some well-known
simple trick for trading off precision. Sounds like not. Thanks--I'm
off to implement bignums in Javascript. ;-)
-Peter
|
