[New-bugs-announce] [issue34376] Improve accuracy of math.hypot() and math.dist()

[Raymond Hettinger]

New submission from Raymond Hettinger <raymond.hettinger at gmail.com>:

Apply two accuracy improvements that work well together and that are both cheap (less than 5% difference in speed).  

1. Moving the max value to the end saves an iteration and can improve accuracy (especially in the case where len(args) <= 3 where the summation order is always optimal).

2. Use Kahan summation which works especially well because all the inputs are non-negative.

The patched version generally gets the error down to within 1 ULP (tested with 100,000 trials using 100 arguments to hypot() where the arguments are generated using random.expovariate(1.0) and arranged in the least favorable order, largest-to-smallest):

Patched:
 [(0.0, 67276),
  (1.0, 16700),
  (-0.5, 14702),
  (-1.0, 1322)]

Baseline:
[(1.0, 30364),
 (0.0, 25328),
 (-0.5, 17407),
 (-1.0, 10554),
 (2.0, 6274),
 (-1.5, 4890),
 (-2.0, 3027),
 (-2.5, 897),
 (3.0, 752),
 (-3.0, 380),
 (-3.5, 61),
 (4.0, 51),
 (-4.0, 13),
 (-4.5, 1),
 (5.0, 1)]

The impact on performance is minimal (well under 5%).

Patched:
$ py -c 'import sys; print(sys.version)'
3.8.0a0 (heads/hypot-kahan-late-swap-2:e1d89184f0, Aug 10 2018, 11:06:21)
[Clang 9.1.0 (clang-902.0.39.2)]
$ py -m timeit -r 7 -s 'from math import hypot' 'hypot(15.0, 14.0, 13.0, 12.0, 11.0, 10.0, 9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0)'
1000000 loops, best of 7: 230 nsec per loop
$ py -m timeit -r 7 -s 'from math import hypot' 'hypot(10.0, 9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0)'
2000000 loops, best of 7: 170 nsec per loop
$ py -m timeit -r 7 -s 'from math import hypot' 'hypot(5.0, 4.0, 3.0, 2.0, 1.0)'
2000000 loops, best of 7: 119 nsec per loop
$ py -m timeit -r 7 -s 'from math import hypot' 'hypot(3.0, 2.0, 1.0)'
5000000 loops, best of 7: 95.7 nsec per loop
$ py -m timeit -r 7 -s 'from math import hypot' 'hypot(2.0, 1.0)'
5000000 loops, best of 7: 81.5 nsec per loop
$ py -m timeit -r 7 -s 'from math import hypot' 'hypot(1.0)'
5000000 loops, best of 7: 67.4 nsec per loop

Baseline:
$ py -c 'import sys; print(sys.version)'
3.8.0a0 (heads/master:077059e0f0, Aug 10 2018, 11:02:47)
[Clang 9.1.0 (clang-902.0.39.2)]
$ py -m timeit -r 7 -s 'from math import hypot' 'hypot(15.0, 14.0, 13.0, 12.0, 11.0, 10.0, 9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0)'
1000000 loops, best of 7: 237 nsec per loop
$ py -m timeit -r 7 -s 'from math import hypot' 'hypot(10.0, 9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0)'
2000000 loops, best of 7: 173 nsec per loop
$ py -m timeit -r 7 -s 'from math import hypot' 'hypot(5.0, 4.0, 3.0, 2.0, 1.0)'
2000000 loops, best of 7: 120 nsec per loop
$ py -m timeit -r 7 -s 'from math import hypot' 'hypot(3.0, 2.0, 1.0)'
5000000 loops, best of 7: 94.8 nsec per loop
$ py -m timeit -r 7 -s 'from math import hypot' 'hypot(2.0, 1.0)'
5000000 loops, best of 7: 80.3 nsec per loop
$ py -m timeit -r 7 -s 'from math import hypot' 'hypot(1.0)'
5000000 loops, best of 7: 67.1 nsec per loop

----------
assignee: rhettinger
components: Library (Lib)
files: measure_hypot_alternatives.py
messages: 323378
nosy: mark.dickinson, rhettinger, serhiy.storchaka, tim.peters
priority: low
severity: normal
status: open
title: Improve accuracy of math.hypot() and math.dist()
type: enhancement
versions: Python 3.8
Added file: https://bugs.python.org/file47741/measure_hypot_alternatives.py

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue34376>
_______________________________________