Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit5d84966

Browse files
authored
GH-100425: Improve accuracy of builtin sum() for float inputs (GH-100426)
1 parent1ecfd1e commit5d84966

File tree

6 files changed

+45
-8
lines changed

6 files changed

+45
-8
lines changed

‎Doc/library/functions.rst

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1733,6 +1733,10 @@ are always available. They are listed here in alphabetical order.
17331733
..versionchanged::3.8
17341734
The *start* parameter can be specified as a keyword argument.
17351735

1736+
..versionchanged::3.12 Summation of floats switched to an algorithm
1737+
that gives higher accuracy on most builds.
1738+
1739+
17361740
..class::super()
17371741
super(type, object_or_type=None)
17381742

‎Doc/library/math.rst

Lines changed: 1 addition & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -108,12 +108,7 @@ Number-theoretic and representation functions
108108
..function::fsum(iterable)
109109

110110
Return an accurate floating point sum of values in the iterable. Avoids
111-
loss of precision by tracking multiple intermediate partial sums:
112-
113-
>>>sum([.1,.1,.1,.1,.1,.1,.1,.1,.1,.1])
114-
0.9999999999999999
115-
>>>fsum([.1,.1,.1,.1,.1,.1,.1,.1,.1,.1])
116-
1.0
111+
loss of precision by tracking multiple intermediate partial sums.
117112

118113
The algorithm's accuracy depends on IEEE-754 arithmetic guarantees and the
119114
typical case where the rounding mode is half-even. On some non-Windows

‎Doc/tutorial/floatingpoint.rst

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -192,7 +192,7 @@ added onto a running total. That can make a difference in overall accuracy
192192
so that the errors do not accumulate to the point where they affect the
193193
final total:
194194

195-
>>>sum([0.1]*10)==1.0
195+
>>>0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1==1.0
196196
False
197197
>>>math.fsum([0.1]*10)==1.0
198198
True

‎Lib/test/test_builtin.py

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@
99
importgc
1010
importio
1111
importlocale
12+
importmath
1213
importos
1314
importpickle
1415
importplatform
@@ -31,13 +32,20 @@
3132
fromtest.support.os_helperimport (EnvironmentVarGuard,TESTFN,unlink)
3233
fromtest.support.script_helperimportassert_python_ok
3334
fromtest.support.warnings_helperimportcheck_warnings
35+
fromtest.supportimportrequires_IEEE_754
3436
fromunittest.mockimportMagicMock,patch
3537
try:
3638
importpty,signal
3739
exceptImportError:
3840
pty=signal=None
3941

4042

43+
# Detect evidence of double-rounding: sum() does not always
44+
# get improved accuracy on machines that suffer from double rounding.
45+
x,y=1e16,2.9999# use temporary values to defeat peephole optimizer
46+
HAVE_DOUBLE_ROUNDING= (x+y==1e16+4)
47+
48+
4149
classSquares:
4250

4351
def__init__(self,max):
@@ -1617,6 +1625,8 @@ def test_sum(self):
16171625
self.assertEqual(repr(sum([-0.0])),'0.0')
16181626
self.assertEqual(repr(sum([-0.0],-0.0)),'-0.0')
16191627
self.assertEqual(repr(sum([],-0.0)),'-0.0')
1628+
self.assertTrue(math.isinf(sum([float("inf"),float("inf")])))
1629+
self.assertTrue(math.isinf(sum([1e308,1e308])))
16201630

16211631
self.assertRaises(TypeError,sum)
16221632
self.assertRaises(TypeError,sum,42)
@@ -1641,6 +1651,14 @@ def __getitem__(self, index):
16411651
sum(([x]forxinrange(10)),empty)
16421652
self.assertEqual(empty, [])
16431653

1654+
@requires_IEEE_754
1655+
@unittest.skipIf(HAVE_DOUBLE_ROUNDING,
1656+
"sum accuracy not guaranteed on machines with double rounding")
1657+
@support.cpython_only# Other implementations may choose a different algorithm
1658+
deftest_sum_accuracy(self):
1659+
self.assertEqual(sum([0.1]*10),1.0)
1660+
self.assertEqual(sum([1.0,10E100,1.0,-10E100]),2.0)
1661+
16441662
deftest_type(self):
16451663
self.assertEqual(type(''),type('123'))
16461664
self.assertNotEqual(type(''),type(()))
Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
Improve the accuracy of ``sum()`` with compensated summation.

‎Python/bltinmodule.c

Lines changed: 20 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2532,17 +2532,33 @@ builtin_sum_impl(PyObject *module, PyObject *iterable, PyObject *start)
25322532

25332533
if (PyFloat_CheckExact(result)) {
25342534
doublef_result=PyFloat_AS_DOUBLE(result);
2535+
doublec=0.0;
25352536
Py_SETREF(result,NULL);
25362537
while(result==NULL) {
25372538
item=PyIter_Next(iter);
25382539
if (item==NULL) {
25392540
Py_DECREF(iter);
25402541
if (PyErr_Occurred())
25412542
returnNULL;
2543+
/* Avoid losing the sign on a negative result,
2544+
and don't let adding the compensation convert
2545+
an infinite or overflowed sum to a NaN. */
2546+
if (c&&Py_IS_FINITE(c)) {
2547+
f_result+=c;
2548+
}
25422549
returnPyFloat_FromDouble(f_result);
25432550
}
25442551
if (PyFloat_CheckExact(item)) {
2545-
f_result+=PyFloat_AS_DOUBLE(item);
2552+
// Improved Kahan–Babuška algorithm by Arnold Neumaier
2553+
// https://www.mat.univie.ac.at/~neum/scan/01.pdf
2554+
doublex=PyFloat_AS_DOUBLE(item);
2555+
doublet=f_result+x;
2556+
if (fabs(f_result) >=fabs(x)) {
2557+
c+= (f_result-t)+x;
2558+
}else {
2559+
c+= (x-t)+f_result;
2560+
}
2561+
f_result=t;
25462562
_Py_DECREF_SPECIALIZED(item,_PyFloat_ExactDealloc);
25472563
continue;
25482564
}
@@ -2556,6 +2572,9 @@ builtin_sum_impl(PyObject *module, PyObject *iterable, PyObject *start)
25562572
continue;
25572573
}
25582574
}
2575+
if (c&&Py_IS_FINITE(c)) {
2576+
f_result+=c;
2577+
}
25592578
result=PyFloat_FromDouble(f_result);
25602579
if (result==NULL) {
25612580
Py_DECREF(item);

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp