Gmail Calendar Documents Reader Web more »
Recently Visited Groups | Help | Sign in
Google Groups Home
Message from discussion Any way around non-reversibility of floating point ops
The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful
 
From:
To:
Cc:
Followup To:
Add Cc | Add Followup-to | Edit Subject
Subject:
Validation:
For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon. Listen and type the numbers you hear
 
Peter Seibel  
View profile  
 More options Nov 2 2008, 5:30 am
Newsgroups: sci.math.num-analysis
From: Peter Seibel <peter.sei...@gmail.com>
Date: Sun, 2 Nov 2008 08:30:20 -0800 (PST)
Local: Sun, Nov 2 2008 5:30 am
Subject: Any way around non-reversibility of floating point ops
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


    Forward  
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.

Create a group - Google Groups - Google Home - Terms of Service - Privacy Policy
©2010 Google