broken link to A.Neumaier article in built-in sum comment

[enzbus]

Bug report

Bug description:

The new implementation of sum on Python 3.12 (cfr. #100425 , #100426 , #107785 ) is not associative on simple input values. This minimal code shows the bug:

On Python 3.11:

>>> a = [0.1, -0.2, 0.3, -0.4, 0.5]
>>> a.append(-sum(a))
>>> sum(a) == 0
True

On Python 3.12:

>>> a = [0.1, -0.2, 0.3, -0.4, 0.5]
>>> a.append(-sum(a))
>>> sum(a) == 0
False

I'm sure this affects more users than the "improved numerical accuracy" on badly scaled input data which most users don't ever deal with, and for which exact arithmetic is already available in the Standard Library
-> https://docs.python.org/3/library/decimal.html.

I'm surprised this low-level change was accepted with so little review. There are other red flags connected with this change:

• The link to the new algorithm's description in cPython's official code is dead ->

  cpython/Python/bltinmodule.c

  Line 2614 in 289af86

  // https://www.mat.univie.ac.at/~neum/scan/01.pdf

• The researcher to which the algorithm is credited has an empty academic page, with no PDFs -> https://www.mat.univie.ac.at/~neum/

Is anybody interested in keeping the quality of cPython's codebase high? When I learned Python, I remember one of the first thing in the official tutorial was that Python is a handy calculator, and now to me it seems broken. @gvanrossum ?

CPython versions tested on:

3.12

Operating systems tested on:

Linux

Linked PRs

• gh-111933: fix broken link to A.Neumaier article #111937
• [3.12] gh-111933: fix broken link to A.Neumaier article (gh-111937) #111993

[skirpichev]

The researcher to which the algorithm is credited has an empty academic page, with no PDFs -> https://www.mat.univie.ac.at/~neum/

FYI, citation: Neumaier, A. (1974), Rundungsfehleranalyse einiger Verfahren zur Summation endlicher Summen. Z. angew. Math. Mech., 54: 39-51. https://doi.org/10.1002/zamm.19740540106.

Full text is still available in the archive: https://web.archive.org/web/20220804051351/https://www.mat.univie.ac.at/~neum/scan/01.pdf Should we use this url or above citation (no free text access)?

BTW, I doubt there is an issue, besides a broken link. Associativity is broken for addition of floating point numbers, see e.g. TAOCP, Vol. 2, 4.2.2. The Tutorial has a dedicated section for floating point arithmetic, which cover this "issue".

exact arithmetic is already available in the Standard Library -> https://docs.python.org/3/library/decimal.html

The decimal module actually not about exact arithmetics, rather the fractions module.

[Eclips4]

cc @rhettinger

[terryjreedy]

One might naively expect sum(a) to be .9 -.6 = .3. But it is actually 0.29999999999999993, so the error is about 7e-17. The sum(a2) is about 3e-17, so the absolute error has gone down. 0.0 error is something of an accident.

Now add -.3 to list a and sum. Instead of the naively expected 0.0, I got -5.6e-17 in 3.11 and -2.8e-17 in 3.12 (both rounded to 2 digits), which is half the error. This is at least as realistic example than the original one and has nothing to do with badly scaled data.

@enzbus In the future, please first ask about possible bugs on help forums such as https://discuss.python.org/c/users/7. And please omit disparaging comments wherever you post.

[sweeneyde]

You also don't have to modify the example too much to see a case where the accuracy of the sum function improved with the change:

>>> # Python 3.11
>>> sum([0.1, -0.2, 0.3, -0.4, 0.5, -0.1, 0.2, -0.3, 0.4, -0.5])
-5.551115123125783e-17

>>> # Python 3.12
>>> sum([0.1, -0.2, 0.3, -0.4, 0.5, -0.1, 0.2, -0.3, 0.4, -0.5])
0.0

[enzbus]

I'm actually getting the error on random inputs, see the commit above which references this bug report. The point remains, this is a regression, adds little value (as I explain above), is the implementation of a 1974 paper in german (really?) which is not online any more, and should not have happened.

[enzbus]

@terryjreedy please re-open, at least to see if this affects other users. Please note that there were no disparaging comments. I noted that the Standard Library already provides arbitrary precision arithmetic in the decimal module, this change refers a suspicious article in German which I couldn't even find (and I went on the academic webpage of the researcher). I think this should not have passed quality review, since this bug is real (I provided a minimal code to show it, but I encountered it on random inputs where the comparison is exact on python < 3.12), especially since it adds little value.

[skirpichev]

@terryjreedy, lets not forgot the real issue with the broken link, see PR #111937.

[terryjreedy]

Everyone who uses non-integral binary floats in any language, not just Python, is affected by the quirks of decimal-binary conversions and of floating-point arithmetic. Comparing the results with == is usually a bug. One solution is to choose a unit such that all values are integral.

@enzbus Suggesting that most or all of us core developers do not care about code quality is not a compliment.

@skirpichev You are right. Reopening for the doc fix.

[enzbus]

Since the minimal code I provided above is not good enough, here's a more interesting version

import random
random.seed(0)
a = [random.gauss(mu=0.0, sigma=1.0) for i in range(10)]
sum_a = sum(a)
sum(a + [-sum_a]) == 0

This is False on 3.12, and True on all earlier versions. That's a bug in my opinion, and it's not justified by improved accuracy in some extreme cases. Also, a 1974 paper in German from a researcher who doesn't even upload it on his academic webpage is not good enough for a fundamental code change, and I don't think it have should passed quality control.

[pochmann]

Did you not read the researcher's page? It says the site moved and provides the new address: https://arnold-neumaier.at/

And the paper is there as well: https://arnold-neumaier.at/scan/01.pdf

If I prepend the sum, your last example fails on 3.11 (I can't test 3.12):

import random
random.seed(0)
a = [random.gauss(mu=0.0, sigma=1.0) for i in range(10)]
sum_a = sum(a)
print(sum([-sum_a] + a) == 0)   # prints False

[enzbus]

Did you not read the researcher's page? It says the site moved and provides the new address: https://arnold-neumaier.at/

And the paper is there as well: https://arnold-neumaier.at/scan/01.pdf

Yes, and it also says that he moved out his website because the University doesn't approve of its content, which doesn't suggest it's particularly trustworthy.

If I prepend the sum, your last example fails on 3.11 (I can't test 3.12):

import random

random.seed(0)

a = [random.gauss(mu=0.0, sigma=1.0) for i in range(10)]

sum_a = sum(a)

print(sum([-sum_a] + a) == 0)   # prints False

Your argument is invalid, I can give much simpler examples of inexact floating point arithmetic.

I gave you instead multiple examples of arithmetic that was correct on all cpythons < 3.12 and is broken on 3.12. (You can try with different random seeds, 3.12 is broken ~95% of the times and earlier pythons are always correct).

The burden is on whoever proposed and accepted this change to show that a 1e-17 improvement on some examples is worth breaking existing codes. And a 1974 paper in german on some guy's website is not a good exhibit.

By the way, the examples I brought work on any implementation of sum that don't fiddle with dynamic programming (are not state-dependent). This is a fundamental change of a builtin function used throughout the library, and I'm under the impression that it's a vanity project that shouldn't have gotten past some corner of a little-used part of the standard library.

[pochmann3]

Your argument is invalid, I can give much simpler examples of inexact floating point arithmetic.

I merely used your example and just prepended instead of appending.

I can give simpler examples, too. For example this fails in 3.11:

a = [0.1, 0.2]
print(sum([-sum(a)] + a) == 0)

I had actually tried to add that to my earlier comment but got an error message trying to edit it. Also can't add new comments with my other account. Did you block me?

it also says that he moved out his website because the University doesn't approve of its content

Where? I don't see it. Looks like you made that up.

[enzbus]

Your argument is invalid, I can give much simpler examples of inexact floating point arithmetic.

I merely used your example and just prepended instead of appending.

I can give simpler examples, too. For example this fails in 3.11:

a = [0.1, 0.2]

print(sum([-sum(a)] + a) == 0)

I had actually tried to add that to my earlier comment but got an error message trying to edit it. Also can't add new comments with my other account. Did you block me?

it also says that he moved out his website because the University doesn't approve of its content

Where? I don't see it. Looks like you made that up.

It says the rectorate doesn't allow him to link his personal web page, and on the bottom that he moved it for political reasons. I'm not interested in arguing about the 1974 german paper, just in making sure that low-level code changes of very dubious value that break existing code are not inserted without proper review. And this one should be reverted ASAP. Again, I stress that the examples I brought are code that worked on cpython before 3.12, and are broken on 3.12. If you want to give me examples of code broken on 3.11, I don't have time to hear that.

[rhettinger]

The value isn't dubious. Numpy has been using a high accuracy sum() for years. Having sum() become more commutative is of high value as well — for example, having sum(seq) not agree with sum(reversed(seq)) is surprising and error prone. Likewise, having sum{[0.1] * 10) not equal to 1.0 was also surprising and error prone.

In general, having more accumulated rounding error is never desirable except in the case of trying reproduce a less accurate result. If the latter is needed, it is trivially easy to accumulate a total in a loop or to use a functional variant like functools.reduce(operator.add, seq).

FWIW, the German paper can be viewed in other languages using Google Translate. The underlying logic is now called Fast2Sum and has been well studied. It is the foundation for many high accuracy algorithms.

[enzbus]

Ok @rhettinger , I believe that this new implementation has lower numerical error on average, and makes exact some arithmetic expressions that were inexact before. However it is a breaking change, and so far nobody in this thread has acknowledged it (and I guess many are core devs?). I gave you examples of floating point arithmetic code that were exact on all cPythons before, and are broken now. The change is not listed as breaking in the release notes. And, as personal opinion, a breaking change on sum on a language that has been around for ~30 years and is used by millions should not have happened. As you mentioned, numpy already provides an implementation of sum that attempts to recover from accumulated errors, so why is Python also doing it? You could also have merged this in a new builtin, say accsum (for accurate sum or accumulated sum), and leave the core builtin untouched. At least, please amend the release notes to say that in some rare cases the new implementation introduces numerical errors on expressions that were exact before (which is a breaking change, however small).

[terryjreedy]

For the purpose of this tracker, a 'bug' is a discrepancy between code and doc. For sum, they match. We do not consider changes in floating points algorithms to be bugs as long as they are reported, to warn people that exact results may change. There is a change note in the sum doc and an entry in What's New 3.12.

Issue #100425 involved 6 core developers who extensively discussed and tested the proposed change. Few issues get as much attention. As near as I can tell, they all considered the change to be an overall improvement. A few carefully picked examples will not change that opinion.

In any case, 3.12 has been released. Reverting back would be a breaking change again.

[enzbus]

It is not a carefully picked example, but an actual bug that I encountered on an open-source library I maintain (an assert failing). It took me a while to figure out what was wrong, and I volunteer time for that. I provided a minimal example code in the opening of this bug report, and then one with random inputs which shows that the new implementation inserts numerical error on that expression in the vast majority of the cases, while it was always exact before. Also, since you mentioned, #100425 is dated December 2022, and the researcher from Vienna says he moved out his website in April 2022 (on the bottom, since people also took issue with the wording of his academic webpage). So the link was dead before the issue was created, and apparently nobody checked it. One could argue, based on the content of this thread, that there's a dismissive culture among core devs of community needs, like minimizing breaking changes, and, if needed, clearly marking them as such. Indeed, even recognizing them (you still haven't admitted that this is one).

[pochmann4]

it was always exact before

It wasn't.

Consider your original example:

>>> a = [0.1, -0.2, 0.3, -0.4, 0.5]
>>> a.append(-sum(a))

The exact values stored in a are:

 0.1000000000000000055511151231257827021181583404541015625
-0.200000000000000011102230246251565404236316680908203125
 0.299999999999999988897769753748434595763683319091796875
-0.40000000000000002220446049250313080847263336181640625
 0.5
-0.29999999999999993338661852249060757458209991455078125

And the exact sum is:

0.0000000000000000277555756156289135105907917022705078125

Not zero.

(And please stop blocking me.)

[enzbus]

You are really nitpicking, and it's not helping your case. If an == comparison returns correctly True on a valid arithmetic expression on all versions of CPython, and then it returns False, that is a breaking change.

[kirpichevs]

The exact values stored in a are:
...
And the exact sum is

In fact, we have decimal module to demonstrate your argument (current main branch):

>>> from decimal import Decimal
>>> from functools import reduce
>>> from operator import add
>>> a = [0.1, -0.2, 0.3, -0.4, 0.5]
>>> ad = list(map(Decimal, a))
>>> Decimal(float(reduce(add, ad)))
Decimal('0.29999999999999993338661852249060757458209991455078125')
>>> float(reduce(add, ad + [-Decimal(float(reduce(add, ad)))]))
2.77555756156e-17
>>> sd = _
>>> sum(a + [-sum(a)])
2.7755575615628914e-17
>>> sr = _
>>> abs((sr - sd)/(0.0 - sd))
1.0417222640068697e-12

In fact, new sum() here more accurate than naive summation for several orders of magnitude.

(And please stop blocking me.)

@pochmann, you are not alone. (Is he already blocking core developers or not yet?)

If an == comparison returns correctly True

@enzbus, people already told you, that using == to compare floating point numbers is a bug (in your program, yes). E.g. floating point arithmetic lacks associativity (for addition or multiplication), so in general the result will depend on the order of evaluation. Your == comparison will be fragile just for that reason.

[pochmann4]

@kirpichevs Yes, I used decimal as well. I used precision 99, though. Not sure what to think of your calculations using the default precision 28, which is not enough here for exact calculations. (Might be enough for your point, I'm just not sure. But with 99, I get sd = 2.7755575615628914e-17 (in Python 3.11, but I think that's the same in 3.12 and main).)

[kirpichevs]

I used precision 99, though. Not sure what to think of your calculations using the default precision 28, which is not enough here for exact calculations.

Well, with this precision there is still a difference with sum() v3.12. But with prec=99:

>>> getcontext().prec=99
>>> a = [0.1, -0.2, 0.3, -0.4, 0.5]
>>> ad = list(map(Decimal, a))
>>> Decimal(float(reduce(add, ad)))
Decimal('0.29999999999999993338661852249060757458209991455078125')
>>> float(reduce(add, ad + [-Decimal(float(reduce(add, ad)))]))
2.7755575615628914e-17
>>> sd = _
>>> sum(a + [-sum(a)])
2.7755575615628914e-17
>>> _ - sd
0.0

[enzbus]

The exact values stored in a are:

...

And the exact sum is

In fact, we have decimal module to demonstrate your argument (current main branch):

>>> from decimal import Decimal

>>> from functools import reduce

>>> from operator import add

>>> a = [0.1, -0.2, 0.3, -0.4, 0.5]

>>> ad = list(map(Decimal, a))

>>> Decimal(float(reduce(add, ad)))

Decimal('0.29999999999999993338661852249060757458209991455078125')

>>> float(reduce(add, ad + [-Decimal(float(reduce(add, ad)))]))

2.77555756156e-17

>>> sd = _

>>> sum(a + [-sum(a)])

2.7755575615628914e-17

>>> sr = _

>>> abs((sr - sd)/(0.0 - sd))

1.0417222640068697e-12

In fact, new sum() here more accurate than naive summation for several orders of magnitude.

(And please stop blocking me.)

@pochmann, you are not alone. (Is he already blocking core developers or not yet?)

If an == comparison returns correctly True

@enzbus, people already told you, that using == to compare floating point numbers is a bug (in your program, yes). E.g. floating point arithmetic lacks associativity (for addition or multiplication), so in general the result will depend on the order of evaluation. Your == comparison will be fragile just for that reason.

You are really trying to shift blame here, away from having introduced a breaking change. If you don't like my code, that's fine, but I test it across all supported CPython versions, and when I added 3.12 I had to go and find why an expression that was exact became inexact. It took me a while because I would never have thought CPython was to blame. But now I understand, I think I see a cavalier attitude among some core devs on introducing breaking changes.

[ericvsmith]

I don't think anyone is denying it's a breaking change. It clearly was.

However, it's a breaking change we were comfortable making in a effort to improve Python. Every release of CPython has breaking changes, in at least the sense that the changes can be detected somehow. Which is unfortunate, but such is the cost of progress. I'm sorry you were affected by this one. But I agree with others that relying on == with floats is a fragile test, and should be avoided.

There's no appetite here for reverting this change.

[kirguesswho]

why an expression that was exact became inexact.

Could you, please, explain (you can still block people here, enjoy!) why do you think it "was exact"?

Consider a simple list of floats:

>>> a = [0.1, -0.2, 0.3, -0.4, 0.2]

Now we try to compute sum:

>>> from random import sample
>>> from functools import reduce
>>> from operator import add
>>> reduce(add, sample(a, 5))
0.0
>>> reduce(add, sample(a, 5))
-8.326672684688674e-17
>>> reduce(add, sample(a, 5))
0.0
>>> reduce(add, sample(a, 5))
-2.7755575615628914e-17

Oops. Different results! Which answer do you prefer and why?

PS:

since you mentioned, #100425 is dated December 2022, and the researcher from Vienna says he moved out his website in April 2022 (on the bottom, since people also took issue with the wording of his academic webpage). So the link was dead

As it was pointed from the beginning of the thread, the link was not dead at least till August 2022. Your argument is wrong.

[enzbus]

I don't think anyone is denying it's a breaking change. It clearly was.

However, it's a breaking change we were comfortable making in a effort to improve Python. Every release of CPython has breaking changes, in at least the sense that the changes can be detected somehow. Which is unfortunate, but such is the cost of progress. I'm sorry you were affected by this one. But I agree with others that relying on == with floats is a fragile test, and should be avoided.

There's no appetite here for reverting this change.

Ok, apologies accepted. Thanks for making CPython available to the community.

[Eclips4]

Let's make it's open until PR with fix(inaccessible link to the research) get merged.

[terryjreedy]

We are not going to revert the change to sum. We are going to improve the reference. No more discussion needed.

[rhettinger]

Let's make it's open until PR with fix(inaccessible link to the research) get merged.

That's now done.