This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author rhettinger
Recipients mark.dickinson, rhettinger, serhiy.storchaka, tim.peters
Date 2018-08-10.18:19:58
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1533925198.56.0.56676864532.issue34376@psf.upfronthosting.co.za>
In-reply-to
Content
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
History
Date User Action Args
2018-08-10 18:19:58rhettingersetrecipients: + rhettinger, tim.peters, mark.dickinson, serhiy.storchaka
2018-08-10 18:19:58rhettingersetmessageid: <1533925198.56.0.56676864532.issue34376@psf.upfronthosting.co.za>
2018-08-10 18:19:58rhettingerlinkissue34376 messages
2018-08-10 18:19:58rhettingercreate