Message from discussion
Any way around non-reversibility of floating point ops
Path: g2news1.google.com!postnews.google.com!b38g2000prf.googlegroups.com!not-for-mail
From: "Thomas M. Hermann" <tmh.pub...@gmail.com>
Newsgroups: sci.math.num-analysis
Subject: Re: Any way around non-reversibility of floating point ops
Date: Sun, 2 Nov 2008 15:27:16 -0800 (PST)
Organization: http://groups.google.com
Lines: 58
Message-ID: <0a36f1e2-ccd3-4d04-84c5-691d2ce76b81@b38g2000prf.googlegroups.com>
References: <7d6c2a14-36f5-426d-9563-b67f70e17b6f@a29g2000pra.googlegroups.com>
NNTP-Posting-Host: 69.29.95.183
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Trace: posting.google.com 1225668436 6180 127.0.0.1 (2 Nov 2008 23:27:16 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Sun, 2 Nov 2008 23:27:16 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: b38g2000prf.googlegroups.com; posting-host=69.29.95.183;
posting-account=wGzyCQoAAABH15vMX85s-CguZ2COcbSN
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (X11; U; FreeBSD i386; en-US; rv:1.8.1.17)
Gecko/20080925 Firefox/2.0.0.17,gzip(gfe),gzip(gfe)
On Nov 2, 10:30 am, Peter Seibel <peter.sei...@gmail.com> wrote:
> 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):
>
> define compute-ev-probabilites (state-probs)
> probs = make-array 0 .. 538
> probs[0] = 1
> foreach state-prob in state-probs
> fold-into probs state-prob.votes state-probs.probability
>
> define fold-into (probs votes prob)
> for i from 538 downto 0
> probs[i] = probs[i] * (1 - prob)
Convert this line to : probs[i] = probs[i] - probs[i] * prob
> if (votes <= i)
> probs[i] = 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:
>
> define back-out (probs votes prob)
> for i from 0 to 538
> if (= prob 1)
> probs[i] (i + votes) < probs.length ? probs[i + votes] : 0
> else
> if (votes <= i) probs[i] = probs[i] - probs[i - votes] * prob
> probs[i] = probs[i] / (1 - prob)
Convert this line to : probs[i] = probs[i] * (1 + prob) / (1 -
prob*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
The little experiment I ran indicated that the roundoff errors should
cancel out with those modification.
Cheers,
Tom H.
|
