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 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.
> 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 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
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!)
> 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):
> > 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
> 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. ;-)
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):
> 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.
>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 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
Thomas M. Hermann wrote: > On Nov 2, 10:30 am, Peter Seibel <peter.sei...@gmail.com> wrote: >> probs[i] = probs[i] * (1 - prob)
> Convert this line to : > probs[i] = probs[i] - probs[i] * prob >> probs[i] = probs[i] / (1 - prob)
> Convert this line to : > probs[i] = probs[i] * (1 + prob) / (1 - prob*prob) > The little experiment I ran indicated that the roundoff errors > should cancel out with those modification.
Is that transformation in the lore or has anyone written about it?
> 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):
> > 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 usefloatingpoint 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 usefloating > > 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.
Hmmm, it didn't seem to help in my actual case. Thanks though.
> Thomas M. Hermann wrote: > > On Nov 2, 10:30 am, Peter Seibel <peter.sei...@gmail.com> wrote: > >> probs[i] = probs[i] * (1 - prob)
> > Convert this line to : > > probs[i] = probs[i] - probs[i] * prob > >> probs[i] = probs[i] / (1 - prob)
> > Convert this line to : > > probs[i] = probs[i] * (1 + prob) / (1 - prob*prob) > > The little experiment I ran indicated that the roundoff errors > > should cancel out with those modification.
> Is that transformation in the lore or has anyone written about it?
> Martin
> -- > Quidquid latine scriptum est, altum videtur.
I think I got the idea for playing algebraic games from mucking around in BLAS code or maybe it was something I read, regardless, I played around with the equations until I found something that didn't exhibit roundoff error for various x and y. The result was:
function foo(x,y) { return x*(1+y)/(1-y*y);
}
function bar(x,y) { return x-x*y;
}
I didn't want to spend a great deal of time verifying this, so I didn't try a great number of inputs. In the process of writing this reply, I just checked x=0.1 and y=0.22 which resulted in a roundoff error of 1.1102230246251565e-16.
I didn't do anything formal, I was just doing a quick experiment with some algebraic manipulation. Obviously, the quick adjective should be replaced with flawed.
|
