Re: sum accuracy
So we could build on this On 15 April 2016 at 11:10, Ben Bacarisse wrote: >> from fractions import Fraction >> >> def exact_sum(nums): >> return sum(map(Fraction, nums)) >> >> This will give you the exact result with precisely zero rounding >> error. You can convert it to float at the end. > > Just a word of warning for people new to numerical work: there's no > rounding error, but unless you start with Fraction objects you still > have input or conversion errors. The uninitiated might expect > > exact_sum([0.3, 0.7]) > > to be 1. and make def not_exact_but_probably_the_sum_you_wanted(nums): return sum(map(lambda x:Fraction(x).limit_denominator(), nums)) -- Matt Wheeler http://funkyh.at -- https://mail.python.org/mailman/listinfo/python-list
Re: sum accuracy
Oscar Benjamin writes: > On 15 April 2016 at 11:10, Ben Bacarisse wrote: >> Oscar Benjamin writes: >> >>> On 15 April 2016 at 10:24, Robin Becker wrote: >> yes indeed summation is hard :( >>> >>> Not with Fraction it isn't: >>> >>> from fractions import Fraction >>> >>> def exact_sum(nums): >>> return sum(map(Fraction, nums)) >>> >>> This will give you the exact result with precisely zero rounding >>> error. You can convert it to float at the end. >> >> Just a word of warning for people new to numerical work: there's no >> rounding error, but unless you start with Fraction objects you still >> have input or conversion errors. > > There are no conversion errors in the Fraction constructor. This will > exactly sum any combination of int/float/Fraction/Decimal without > errors. (It will raise ValueError on nan/inf but I consider that a > good thing). Yes, that's a good point. Starting with Fraction objects is just one way to know exactly what you are exactly summing. >> The uninitiated might expect >> >> exact_sum([0.3, 0.7]) >> >> to be 1. > > That's true but I wanted to correct the impression (from above) that > *converting* to Fraction is a source of rounding error. It is your > responsibility to give exact_sum the exact numbers that you want to > add. The bad phrase "input or conversion errors" was intended to refer to the conversion Python does when you write 0.3 in the source or when you read your data and convert it to floating-point. It can certainly be read as if I was talking about the constructor but, as you say, *that* conversion is exact. -- Ben. -- https://mail.python.org/mailman/listinfo/python-list
Re: sum accuracy
On 15 April 2016 at 11:10, Ben Bacarisse wrote: > Oscar Benjamin writes: > >> On 15 April 2016 at 10:24, Robin Becker wrote: > >>> yes indeed summation is hard :( >> >> Not with Fraction it isn't: >> >> from fractions import Fraction >> >> def exact_sum(nums): >> return sum(map(Fraction, nums)) >> >> This will give you the exact result with precisely zero rounding >> error. You can convert it to float at the end. > > Just a word of warning for people new to numerical work: there's no > rounding error, but unless you start with Fraction objects you still > have input or conversion errors. There are no conversion errors in the Fraction constructor. This will exactly sum any combination of int/float/Fraction/Decimal without errors. (It will raise ValueError on nan/inf but I consider that a good thing). > The uninitiated might expect > > exact_sum([0.3, 0.7]) > > to be 1. That's true but I wanted to correct the impression (from above) that *converting* to Fraction is a source of rounding error. It is your responsibility to give exact_sum the exact numbers that you want to add. You can even use strings if you want to write numbers in decimal: exact_sum(['0.3', '0.7']) -- Oscar -- https://mail.python.org/mailman/listinfo/python-list
Re: sum accuracy
Tony van der Hoff writes: > On 15/04/16 11:10, Ben Bacarisse wrote: >> Oscar Benjamin writes: >> >>> On 15 April 2016 at 10:24, Robin Becker wrote: >> yes indeed summation is hard :( >>> >>> Not with Fraction it isn't: >>> >>> from fractions import Fraction >>> >>> def exact_sum(nums): >>> return sum(map(Fraction, nums)) >>> >>> This will give you the exact result with precisely zero rounding >>> error. You can convert it to float at the end. >> >> Just a word of warning for people new to numerical work: there's no >> rounding error, but unless you start with Fraction objects you still >> have input or conversion errors. The uninitiated might expect >> >>exact_sum([0.3, 0.7]) >> >> to be 1. >> > > So I'm uninitiated: > NameError: name 'exact_sum' is not defined > > I appreciate the word of warning, but, in my case, it's not helpful. There's a reason Ben included some context. His point is that Fraction(0.3) is not equal to Fraction(3, 10). That in turn is because the floating point number differs a little from the mathematical ideal, and the representation of that floating point number as a Fraction in Python preserves that difference. Try Fraction(0.3), Fraction("0.3"), Fraction(3, 10), Fraction(3)/10 and see for yourself. Also, Fraction(0.3).limit_denominator() gives Fraction(3, 10). See the documentation. -- https://mail.python.org/mailman/listinfo/python-list
Re: sum accuracy
On 15/04/16 11:10, Ben Bacarisse wrote: Oscar Benjamin writes: On 15 April 2016 at 10:24, Robin Becker wrote: yes indeed summation is hard :( Not with Fraction it isn't: from fractions import Fraction def exact_sum(nums): return sum(map(Fraction, nums)) This will give you the exact result with precisely zero rounding error. You can convert it to float at the end. Just a word of warning for people new to numerical work: there's no rounding error, but unless you start with Fraction objects you still have input or conversion errors. The uninitiated might expect exact_sum([0.3, 0.7]) to be 1. So I'm uninitiated: NameError: name 'exact_sum' is not defined I appreciate the word of warning, but, in my case, it's not helpful. -- Tony van der Hoff| mailto:t...@vanderhoff.org Buckinghamshire, England | -- https://mail.python.org/mailman/listinfo/python-list
Re: sum accuracy
Oscar Benjamin writes: > On 15 April 2016 at 10:24, Robin Becker wrote: >> yes indeed summation is hard :( > > Not with Fraction it isn't: > > from fractions import Fraction > > def exact_sum(nums): > return sum(map(Fraction, nums)) > > This will give you the exact result with precisely zero rounding > error. You can convert it to float at the end. Just a word of warning for people new to numerical work: there's no rounding error, but unless you start with Fraction objects you still have input or conversion errors. The uninitiated might expect exact_sum([0.3, 0.7]) to be 1. -- Ben. -- https://mail.python.org/mailman/listinfo/python-list
Re: sum accuracy
On 15 April 2016 at 10:24, Robin Becker wrote: > On 13/04/2016 18:05, Random832 wrote: > . >> >> >> No, it doesn't. Sum works on any type that can be added (except >> strings), it can't make any assumptions about the characteristics of >> floating point types. For non-numeric types, the addition operator may >> not be semantically commutative or associative. >> > I thought as much. My problem was that the sum of an array of small floats > was being used to compute a grid of points by subtraction like this > > height = sum(H) > pos = [height] > for h in H: > height -= h > pos.append(height) > > the value of height[0] came out negative which was a problem. I could reduce > the error by using Kahan summation instead of sum, but that required Kahan > style subtraction as well. In the end it just seemed better to reverse the > loop and compute pos by addition. > > >> Look at >> >> http://code.activestate.com/recipes/393090-binary-floating-point-summation-accurate-to-full-p/ >> for an example of a more accurate algorithm, but note that, for example, >> this algorithm wouldn't work on complex numbers (you'd have to sum the >> real and imaginary components separately) >> > yes indeed summation is hard :( Not with Fraction it isn't: from fractions import Fraction def exact_sum(nums): return sum(map(Fraction, nums)) This will give you the exact result with precisely zero rounding error. You can convert it to float at the end. -- Oscar -- https://mail.python.org/mailman/listinfo/python-list
Re: sum accuracy
On 13/04/2016 18:05, Random832 wrote: . No, it doesn't. Sum works on any type that can be added (except strings), it can't make any assumptions about the characteristics of floating point types. For non-numeric types, the addition operator may not be semantically commutative or associative. I thought as much. My problem was that the sum of an array of small floats was being used to compute a grid of points by subtraction like this height = sum(H) pos = [height] for h in H: height -= h pos.append(height) the value of height[0] came out negative which was a problem. I could reduce the error by using Kahan summation instead of sum, but that required Kahan style subtraction as well. In the end it just seemed better to reverse the loop and compute pos by addition. Look at http://code.activestate.com/recipes/393090-binary-floating-point-summation-accurate-to-full-p/ for an example of a more accurate algorithm, but note that, for example, this algorithm wouldn't work on complex numbers (you'd have to sum the real and imaginary components separately) yes indeed summation is hard :( -- Robin Becker -- https://mail.python.org/mailman/listinfo/python-list
Re: sum accuracy
Robin Becker wrote: > Does anyone know if sum does anything special to try and improve accuracy? > My simple tests seem to show it is exactly equivalent to a for loop > summation. If you are worried about accuracy and your values are floating point numbers use math.fsum(): """ fsum(...) fsum(iterable) Return an accurate floating point sum of values in the iterable. Assumes IEEE-754 floating point arithmetic. """ -- https://mail.python.org/mailman/listinfo/python-list
Re: sum accuracy
Robin Becker writes: > Does anyone know if sum does anything special to try and improve > accuracy? My simple tests seem to show it is exactly equivalent to a > for loop summation. You want math.fsum. -- https://mail.python.org/mailman/listinfo/python-list
Re: sum accuracy
On Wed, Apr 13, 2016, at 12:51, Robin Becker wrote: > Does anyone know if sum does anything special to try and improve > accuracy? My > simple tests seem to show it is exactly equivalent to a for loop > summation. No, it doesn't. Sum works on any type that can be added (except strings), it can't make any assumptions about the characteristics of floating point types. For non-numeric types, the addition operator may not be semantically commutative or associative. Look at http://code.activestate.com/recipes/393090-binary-floating-point-summation-accurate-to-full-p/ for an example of a more accurate algorithm, but note that, for example, this algorithm wouldn't work on complex numbers (you'd have to sum the real and imaginary components separately) -- https://mail.python.org/mailman/listinfo/python-list
sum accuracy
Does anyone know if sum does anything special to try and improve accuracy? My simple tests seem to show it is exactly equivalent to a for loop summation. -- Robin Becker -- https://mail.python.org/mailman/listinfo/python-list