Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #107037 > unrolled thread

Re: sum accuracy

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: sum accuracy Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2016-04-15 10:36 +0100
    Re: sum accuracy Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-04-15 11:10 +0100
      Re: sum accuracy Tony van der Hoff <tony@vanderhoff.org> - 2016-04-15 11:39 +0100
        Re: sum accuracy Jussi Piitulainen <jussi.piitulainen@helsinki.fi> - 2016-04-15 14:31 +0300
      Re: sum accuracy Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2016-04-15 08:11 -0400
      Re: sum accuracy Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2016-04-15 14:49 +0100
        Re: sum accuracy Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-04-15 17:54 +0100
      Re: sum accuracy Matt Wheeler <m@funkyhat.org> - 2016-04-15 18:04 +0100

#107037 — Re: sum accuracy

On 15 April 2016 at 10:24, Robin Becker <robin@reportlab.com> 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

[toc] | [next] | [standalone]

#107039

Oscar Benjamin <oscar.j.benjamin@gmail.com> writes:

> On 15 April 2016 at 10:24, Robin Becker <robin@reportlab.com> wrote:
<snip>
>> 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.

[toc] | [prev] | [next] | [standalone]

#107041

On 15/04/16 11:10, Ben Bacarisse wrote:
> Oscar Benjamin <oscar.j.benjamin@gmail.com> writes:
>
>> On 15 April 2016 at 10:24, Robin Becker <robin@reportlab.com> wrote:
> <snip>
>>> 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:tony@vanderhoff.org
Buckinghamshire, England |

[toc] | [prev] | [next] | [standalone]

#107043

Tony van der Hoff writes:
> On 15/04/16 11:10, Ben Bacarisse wrote:
>> Oscar Benjamin <oscar.j.benjamin@gmail.com> writes:
>>
>>> On 15 April 2016 at 10:24, Robin Becker <robin@reportlab.com> wrote:
>> <snip>
>>>> 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.

[toc] | [prev] | [next] | [standalone]

#107051

On Fri, 15 Apr 2016 11:39:45 +0100, Tony van der Hoff <tony@vanderhoff.org>
declaimed the following:

>On 15/04/16 11:10, Ben Bacarisse wrote:
>> Oscar Benjamin <oscar.j.benjamin@gmail.com> writes:
>>
	<snip>
>>>
>>> Not with Fraction it isn't:
>>>
>>> from fractions import Fraction
>>>
>>> def exact_sum(nums):
>>>      return sum(map(Fraction, nums))
>>>
	<snip>
>
>So I'm uninitiated:
>NameError: name 'exact_sum' is not defined
>

	It's a use-defined function whose code was given in the content you had
quoted.
-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
    wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

[toc] | [prev] | [next] | [standalone]

#107056

On 15 April 2016 at 11:10, Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
> Oscar Benjamin <oscar.j.benjamin@gmail.com> writes:
>
>> On 15 April 2016 at 10:24, Robin Becker <robin@reportlab.com> wrote:
> <snip>
>>> 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

[toc] | [prev] | [next] | [standalone]

#107065

Oscar Benjamin <oscar.j.benjamin@gmail.com> writes:

> On 15 April 2016 at 11:10, Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>> Oscar Benjamin <oscar.j.benjamin@gmail.com> writes:
>>
>>> On 15 April 2016 at 10:24, Robin Becker <robin@reportlab.com> wrote:
>> <snip>
>>>> 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.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#107066

So we could build on this

On 15 April 2016 at 11:10, Ben Bacarisse <ben.usenet@bsb.me.uk> 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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web