8000 bpo-33089: Multidimensional math.hypot() by rhettinger · Pull Request #8474 · python/cpython · GitHub
[go: up one dir, main page]
Skip to content

bpo-33089: Multidimensional math.hypot() #8474

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
merged 21 commits into from
Jul 28, 2018
Merged

bpo-33089: Multidimensional math.hypot() #8474

Show file tree
Hide file tree
Changes from 16 commits
Commits
Show all changes
21 commits
Select commit Hold shift + click to select a range
ec15283
Segfaulting rough draft without NaN support or raising Overflow
rhettinger Jul 7, 2018
abce2b0
Working verion. Double pass over input tuple. No inf/nan handling.
rhettinger Jul 7, 2018
241932e
Simplify. Remove unnecessary second error check. Remove n<=1 special …
rhettinger Jul 7, 2018
51c52fc
Add some tests
rhettinger Jul 24, 2018
de3c16b
Add support for special values.
rhettinger Jul 25, 2018
18babd4
Test scaling for large values
rhettinger Jul 25, 2018
6c412d2
Add tests for small values
rhettinger Jul 26, 2018
780024b
Neaten-up test cases
rhettinger Jul 26, 2018
d82df99
Use module level constants for float min/max
rhettinger Jul 26, 2018
1a32ac7
Expand range for large value tests
rhettinger Jul 26, 2018
82a12e5
Improve variable name
rhettinger Jul 26, 2018
2d2e3aa
Replace the existing hypot() code
rhettinger Jul 26, 2018
6edd323
Clean stray whitespace
rhettinger Jul 26, 2018
9c25c65
Write the docstring
rhettinger Jul 26, 2018
c4dfbe5
Update the main documentation
rhettinger Jul 26, 2018
0734edd
Add blurb
rhettinger Jul 26, 2018
43471a9
Address Tim's review comments.
rhettinger Jul 27, 2018
3818324
Update argument clinic checksum
rhettinger Jul 27, 2018
8298444
Reuse converted floats rather than converting twice
rhettinger Jul 27, 2018
d785025
Add test for a negative zero input
rhettinger Jul 28, 2018
ee1374c
Test for failed malloc(). Only test inf at the end.
rhettinger Jul 28, 2018
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
15 changes: 12 additions & 3 deletions Doc/library/math.rst
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -330,10 +330,19 @@ Trigonometric functions
Return the cosine of *x* radians.


.. function:: hypot(x, y)
.. function:: hypot(*coordinates)

Return the Euclidean norm, ``sqrt(x*x + y*y)``. This is the length of the vector
from the origin to point ``(x, y)``.
Return the Euclidean norm, ``sqrt(sum(x**2 for x in coordinates))``.
This is the length of the vector from the origin to the point
given by the coordinates.

For a two dimensional point ``(x, y)``, this is equivalent to computing
the hypotenuse of a right triangle using the Pythagorean theorem,
``sqrt(x*x + y*y)``.

.. versionchanged:: 3.8
Added support for n-dimensional points. Formerly, only the two
dimensional case was supported.


.. function:: sin(x)
Expand Down
72 changes: 62 additions & 10 deletions Lib/test/test_math.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -16,6 +16,7 @@
INF = float('inf')
NINF = float('-inf')
FLOAT_MAX = sys.float_info.max
FLOAT_MIN = sys.float_info.min

# detect evidence of double-rounding: fsum is not always correctly
# rounded on machines that suffer from double rounding.
Expand Down Expand Up @@ -720,16 +721,67 @@ def testGcd(self):
self.assertEqual(gcd(MyIndexable(120), MyIndexable(84)), 12)

def testHypot(self):
self.assertRaises(TypeError, math.hypot)
self.ftest('hypot(0,0)', math.hypot(0,0), 0)
self.ftest('hypot(3,4)', math.hypot(3,4), 5)
self.assertEqual(math.hypot(NAN, INF), INF)
self.assertEqual(math.hypot(INF, NAN), INF)
self.assertEqual(math.hypot(NAN, NINF), INF)
self.assertEqual(math.hypot(NINF, NAN), INF)
self.assertRaises(OverflowError, math.hypot, FLOAT_MAX, FLOAT_MAX)
self.assertTrue(math.isnan(math.hypot(1.0, NAN)))
self.assertTrue(math.isnan(math.hypot(NAN, -2.0)))
from decimal import Decimal
from fractions import Fraction

hypot = math.hypot

# Test different numbers of arguments (from zero to five)
# against a straightforward pure python implementation
args = math.e, math.pi, math.sqrt(2.0), math.gamma(3.5), math.sin(2.1)
for i in range(len(args)+1):
self.assertAlmostEqual(
hypot(*args[:i]),
math.sqrt(sum(s**2 for s in args[:i]))
)

# Test allowable types (those with __float__)
self.assertEqual(hypot(12.0, 5.0), 13.0)
self.assertEqual(hypot(12, 5), 13)
self.assertEqual(hypot(Decimal(12), Decimal(5)), 13)
self.assertEqual(hypot(Fraction(12, 32), Fraction(5, 32)), Fraction(13, 32))
self.assertEqual(hypot(bool(1), bool(0), bool(1), bool(1)), math.sqrt(3))

# Test corner cases
self.assertEqual(hypot(0.0, 0.0), 0.0) # Max input is zero
self.assertEqual(hypot(-10.5), 10.5) # Negative input
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Add self.assertEqual(hypot(), 0.0)?

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Okay, added an explict test for this case. FWIW, this was already tested in the section "Test different numbers of arguments (from zero to five)".


# Test handling of bad arguments
with self.assertRaises(TypeError): # Reject keyword args
hypot(x=1)
with self.assertRaises(TypeError): # Reject values without __float__
hypot(1.1, 'string', 2.2)

# Any infinity gives positive infinity.
self.assertEqual(hypot(INF), INF)
self.assertEqual(hypot(0, INF), INF)
self.assertEqual(hypot(10, INF), INF)
self.assertEqual(hypot(-10, INF), INF)
self.assertEqual(hypot(NAN, INF), INF)
self.assertEqual(hypot(INF, NAN), INF)
self.assertEqual(hypot(NINF, NAN), INF)
self.assertEqual(hypot(NAN, NINF), INF)
self.assertEqual(hypot(-INF, INF), INF)
self.assertEqual(hypot(-INF, -INF), INF)
self.assertEqual(hypot(10, -INF), INF)

# If no infinity, any NaN gives a Nan.
self.assertTrue(math.isnan(hypot(NAN)))
self.assertTrue(math.isnan(hypot(0, NAN)))
self.assertTrue(math.isnan(hypot(NAN, 10)))
self.assertTrue(math.isnan(hypot(10, NAN)))
self.assertTrue(math.isnan(hypot(NAN, NAN)))
self.assertTrue(math.isnan(hypot(NAN)))

# Verify scaling for extremely large values
fourthmax = FLOAT_MAX / 4.0
for n in range(32):
self.assertEqual(hypot(*([fourthmax]*n)), fourthmax * math.sqrt(n))

# Verify scaling for extremely small values
for exp in range(32):
scale = FLOAT_MIN / 2.0 ** exp
self.assertEqual(math.hypot(12*scale, 5*scale), 13*scale)
Copy link
Member
@tim-one tim-one Jul 26, 2018 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This makes me nervous, because it depends on that

12 * math.sqrt(1 + (5/12)**2)

happens to be exactly 13.0 despite that 5/12 isn't exactly representable. Would be happier with:

self.assertEqual(math.hypot(4*scale, 3*scale), 5*scale)

because every intermediate value in

4 * math.sqrt(1 + (3/4)**2)

is exactly representable in binary.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Okay, changed to a 3-4-5 triangle.


def testLdexp(self):
self.assertRaises(TypeError, math.ldexp)
Expand Down
1 change: 1 addition & 0 deletions Misc/NEWS.d/next/Library/2018-07-25-22-38-54.bpo-33089.C3CB7e.rst
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1 @@
Enhanced math.hypot() to support more than two dimensions.
29 changes: 0 additions & 29 deletions Modules/clinic/mathmodule.c.h
View file
Open in desktop

Some generated files are not rendered by default. Learn more about how customized files appear on GitHub.

91 changes: 53 additions & 38 deletions Modules/mathmodule.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -2031,49 +2031,64 @@ math_fmod_impl(PyObject *module, double x, double y)
return PyFloat_FromDouble(r);
}


/*[clinic input]
math.hypot

x: double
y: double
/

Return the Euclidean distance, sqrt(x*x + y*y).
[clinic start generated code]*/

/* AC: cannot convert yet, waiting for *args support */
static PyObject *
math_hypot_impl(PyObject *module, double x, double y)
/*[clinic end generated code: output=b7686e5be468ef87 input=7f8eea70406474aa]*/
math_hypot(PyObject *self, PyObject *args)
{
double r;
/* hypot(x, +/-Inf) returns Inf, even if x is a NaN. */
if (Py_IS_INFINITY(x))
return PyFloat_FromDouble(fabs(x));
if (Py_IS_INFINITY(y))
return PyFloat_FromDouble(fabs(y));
errno = 0;
PyFPE_START_PROTECT("in math_hypot", return 0);
r = hypot(x, y);
PyFPE_END_PROTECT(r);
if (Py_IS_NAN(r)) {
if (!Py_IS_NAN(x) && !Py_IS_NAN(y))
errno = EDOM;
else
errno = 0;
Py_ssize_t i, n;
PyObject *item;
double max = 0.0;
double csum = 0.0;
double x;
int found_inf = 0;
int found_nan = 0;

n = PyTuple_GET_SIZE(args);
for (i=0 ; i<n ; i++) {
item = PyTuple_GET_ITEM(args, i);
x = PyFloat_AsDouble(item);
if (x == -1.0 && PyErr_Occurred()) {
return NULL;
}
found_inf |= Py_IS_INFINITY(x);
found_nan |= Py_IS_NAN(x);
x = fabs(x);
if (x > max) {
max = x;
}
}
else if (Py_IS_INFINITY(r)) {
if (Py_IS_FINITE(x) && Py_IS_FINITE(y))
errno = ERANGE;
else
errno = 0;
if (found_inf) {
return PyFloat_FromDouble(max);
}
if (errno && is_error(r))
return NULL;
else
return PyFloat_FromDouble(r);
if (found_nan) {
return PyFloat_FromDouble(Py_NAN);
}
if (max == 0.0) {
return PyFloat_FromDouble(0.0);
}
for (i=0 ; i<n ; i++) {
item = PyTuple_GET_ITEM(args, i);
x = PyFloat_AsDouble(item) / max;
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Are we quite sure a malicious __float__() implementation can't mutate other values in the argument tuple? That is, that no conversion failed the first time through the tuple guarantees none will fail the second time through?

I don't know. In which case checking for a -1.0 error return here too would be safest.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Okay, added the -1.0 test.

csum += x * x;
}
return PyFloat_FromDouble(max * sqrt(csum)); // XXX Handle overflow
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It's good enough for me that +Inf will result from overflow here, but that it is a change from, e.g., what 3.7 does on Windows:

>>> import sys
>>> import math
>>> x = sys.float_info.max
>>> math.hypot(x, x)
Traceback (most recent call last):
    ...
OverflowError: math range error

Copy link
Contributor Author
@rhettinger rhettinger Jul 27, 2018 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

That is good enough for me too :-) I like that it matches the behavior of the pure python code:

>>> import sys
>>> coordinates = [sys.float_info.max] * 1
>>> scale * sqrt(sum((x/scale) ** x for x in coordinates))
1.7976931348623157e+308
>>> coordinates = [sys.float_info.max] * 2
>>> scale * sqrt(sum((x/scale) ** x for x in coordinates))
inf

}

PyDoc_STRVAR(math_hypot_doc,
"hypot(*coordinates) -> value\n\n\
Multidimensional Euclidean distance from the origin to a point.\n\
\n\
Roughly equivalent to:\n\
sqrt(sum(x**2 for x in coordinates))\n\
\n\
For a two dimensional point (x, y), gives the hypotenuse\n\
using the Pythagorean theorem: sqrt(x*x + y*y).\n\
\n\
For example, the hypotenuse of a 3/4/5 right triangle is:\n\
\n\
>>> hypot(3.0, 4.0)\n\
5.0\n\
");

/* pow can't use math_2, but needs its own wrapper: the problem is
that an infinite result can arise either as a result of overflow
Expand Down Expand Up @@ -2345,7 +2360,7 @@ static PyMethodDef math_methods[] = {
MATH_FSUM_METHODDEF
{"gamma", math_gamma, METH_O, math_gamma_doc},
MATH_GCD_METHODDEF
MATH_HYPOT_METHODDEF
{"hypot", math_hypot, METH_VARARGS, math_hypot_doc},
MATH_ISCLOSE_METHODDEF
MATH_ISFINITE_METHODDEF
MATH_ISINF_METHODDEF
Expand Down
0