Message from discussion Any way around non-reversibility of floating point ops

Path: g2news1.google.com!news2.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!newsfeed00.sul.t-online.de!newsfeed01.sul.t-online.de!t-online.de!newsfeed.velia.net!news.tu-darmstadt.de!spellucci
From: spellu...@fb04373.mathematik.tu-darmstadt.de (Peter Spellucci)
Newsgroups: sci.math.num-analysis
Subject: Re: Any way around non-reversibility of floating point ops
Date: Mon, 3 Nov 2008 14:06:25 +0100 (CET)
Organization: TU Darmstadt, Fachbereich Mathematik
Lines: 62
Sender: spellu...@mathematik.tu-darmstadt.de
Message-ID: <gemt0h$fva$1@fb04373.mathematik.tu-darmstadt.de>
References: <7d6c2a14-36f5-426d-9563-b67f70e17b6f@a29g2000pra.googlegroups.com>
NNTP-Posting-Host: fb04373.mathematik.tu-darmstadt.de
X-Trace: lnx107.hrz.tu-darmstadt.de 1225717585 11771 130.83.2.113 (3 Nov 2008 13:06:25 GMT)
X-Complaints-To: news@news.tu-darmstadt.de
NNTP-Posting-Date: Mon, 3 Nov 2008 13:06:25 +0000 (UTC)
X-Newsreader: xrn 9.02


In article <7d6c2a14-36f5-426d-9563-b67f70e17...@a29g2000pra.googlegroups.com>,
 Peter Seibel <peter.sei...@gmail.com> writes:
>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)
>      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)
>
>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

as stated already by others, yuo must in principle use an error analysis based
on the (hopefully for your system ) correct model of the computer arithmetic

  (x machine operation y ) = (x exact operation y)(1+eta) 

with abs(eta)<= eps = "machine precision" = 2^(-53) in double 
but since vote is integer, it might suffice if you replace the test
   < i 
by
  < dble(i)+0.25
?
(you compare variables which in orinciple should come out as integers, 
hopefully the roundoff errors are not thta large that errors >=1 occur.)
hth
peter