René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Improve accuracy of builtin sum() for float inputs","articleBody":"Currently `sum()` makes no efforts to improve accuracy over a simple running total.  We do have `math.fsum()` that makes extreme efforts to be almost perfect; however, that function isn't well known, it runs 10x slower than regular `sum()`, and it always coerces to a float.\r\n\r\nI suggest switching the builtin `sum()` handling of float inputs to Arnold Neumaier's improved variation of compensated summation.   Per his [paper](https://www.mat.univie.ac.at/~neum/scan/01.pdf), this algorithm has excellent error bounds (though not as perfect as `fsum()`:\r\n\r\n```\r\n|s - š| ≤ ε|s| + ε²(3/4n² + n)·Σ|aᵢ|               (IV,12)\r\n|s - š| ≤ ε|s| + ε²(1/4n³ + 5/2n² + n)·Max|aᵢ|     (IV,13)\r\n```\r\n\r\nThe compensation tracking runs in parallel to the main accumulation.  And except for pathological cases, the branch is predictable, making the test essentially free.  Thanks to the magic of instruction level parallelism and branch prediction, this improvement has zero cost on my Apple M1 build.  Timed with:\r\n\r\n`./python.exe -m timeit -s 'from random import expovariate as r' -s 'd=[r(1.0) for i in range(10_000)]' 'sum(d)'`\r\n\r\nN.B.  Numpy switched from a simple running total to [partial pairwise summation](https://numpy.org/doc/stable/reference/generated/numpy.sum.html).  That isn't as accurate as what is being proposed here, but it made more sense for them because the extra work of Neumaier summation isn't masked by the overhead of fetching values from an iterator as we do here.  Also with an iterator, we can't do pairwise summation without using auxiliary memory.\r\n\r\n\n\n\u003c!-- gh-linked-prs --\u003e\n### Linked PRs\n* gh-100426\n* gh-100860\n* gh-101854\n* gh-107785\n* gh-107787\n\u003c!-- /gh-linked-prs --\u003e\n","author":{"url":"https://github.com/rhettinger","@type":"Person","name":"rhettinger"},"datePublished":"2022-12-22T06:48:17.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":24},"url":"https://github.com/100425/cpython/issues/100425"}