New submission from Raymond Hettinger <raymond.hettin...@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 <rep...@bugs.python.org> <https://bugs.python.org/issue34376> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
