Skip to content

bpo-41513: Improve speed and accuracy of math.hypot() #21803

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
rhettinger merged 10 commits into from
Aug 16, 2020
+44 −6
Merged

bpo-41513: Improve speed and accuracy of math.hypot() #21803

Changes from 1 commit
Commits
Show all changes
10 commits
Select commit Hold shift + click to select a range
e2b1b38
frexp/ldexp variant
rhettinger Aug 8, 2020
7cb895d
Multiply by power of two variant
rhettinger Aug 8, 2020
2d586b1
Strengthen assertions
rhettinger Aug 9, 2020
c15ce79
Added notes and commented out assertions to reach a stable resting point
rhettinger Aug 9, 2020
c853597
Two code paths. All tests pass.
rhettinger Aug 9, 2020
03ec58b
Clean-up comments and ranges
rhettinger Aug 10, 2020
ebf6a31
Remove debugging code
rhettinger Aug 10, 2020
4742ef8
Clean-up comments and over-specified tests
rhettinger Aug 10, 2020
5e9f1a9
Add blurb
rhettinger Aug 10, 2020
5c6478f
Improve the comments.
rhettinger Aug 15, 2020
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Improve the comments.
  • Loading branch information
@rhettinger
rhettinger committed Aug 15, 2020
commit 5c6478f2f88f0cb6ccd65f0fe17f25ffbf059a12
12 changes: 8 additions & 4 deletions Modules/mathmodule.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -2432,13 +2432,18 @@ The *csum* variable tracks the cumulative sum and *frac* tracks
the cumulative fractional errors at each step. Since this
variant assumes that |csum| >= |x| at each step, we establish
the precondition by starting the accumulation from 1.0 which
represents the largest possible value of (x/max)**2.
represents the largest possible value of (x*scale)**2 or (x/max)**2.

After the loop is finished, the initial 1.0 is subtracted out
for a net zero effect on the final sum. Since *csum* will be
greater than 1.0, the subtraction of 1.0 will not cause
fractional digits to be dropped from *csum*.

To get the full benefit from compensated summation, the
largest addend should be in the range: 0.5 <= x <= 1.0.
Accordingly, scaling or division by *max* should not be skipped
even if not otherwise needed to prevent overflow or loss of precision.

*/

static inline double
Expand Down Expand Up @@ -2475,9 +2480,8 @@ vector_norm(Py_ssize_t n, double *vec, double max, int found_nan)
}
return sqrt(csum - 1.0 + frac) / scale;
}
/* When max_e < -1023, a scale computed given by ldexp(1.0, -max_e)
would be subnormal and break range invariants for max*scale.
Instead, we just divide by *max*.
/* When max_e < -1023, ldexp(1.0, -max_e) overflows.
So instead of multiplying by a scale, we just divide by *max*.
*/
for (i=0 ; i < n ; i++) {
x = vec[i];
Expand Down