Pythagorean addition

In mathematics, Pythagorean addition is a binary operation on the real numbers that computes the length of the hypotenuse of a right triangle, given its two sides. According to the Pythagorean theorem, for a triangle with sides ${\displaystyle a}$ and ${\displaystyle b}$, this length can be calculated as

$${\displaystyle a\oplus b={\sqrt {a^{2}+b^{2}}},}$$

where ${\displaystyle \oplus }$ denotes the Pythagorean addition operation. ^[1]

This operation can be used in the conversion of Cartesian coordinates to polar coordinates. It also provides a simple notation and terminology for some formulas when its summands are complicated; for example, the energy-momentum relation in physics becomes

$${\displaystyle E=mc^{2}\oplus pc.}$$

It is implemented in many programming libraries as the hypot function, in a way designed to avoid errors arising due to limited-precision calculations performed on computers. In its applications to signal processing and propagation of measurement uncertainty, the same operation is also called addition in quadrature. ^[2]

Applications

Example of Pythagorean addition of independent errors using vector addition of orthogonal vectors

Pythagorean addition (and its implementation as the hypot function) is often used together with the atan2 function to convert from Cartesian coordinates ${\displaystyle (x,y)}$ to polar coordinates ${\displaystyle (r,\theta )}$: ^{[3] [4]}

$${\displaystyle {\begin{aligned}r&=x\oplus y=\operatorname {hypot} (x,y)\\\theta &=\operatorname {atan2} (y,x).\\\end{aligned}}}$$

If measurements ${\displaystyle X,Y,Z,\dots }$ have independent errors ${\displaystyle \Delta _{X},\Delta _{Y},\Delta _{Z},\dots }$ respectively, the quadrature method gives the overall error,

$${\displaystyle \varDelta _{o}={\sqrt {{\varDelta _{X}}^{2}+{\varDelta _{Y}}^{2}+{\varDelta _{Z}}^{2}+\cdots }}}$$

whereas the upper limit of the overall error is

$${\displaystyle \varDelta _{u}=\varDelta _{X}+\varDelta _{Y}+\varDelta _{Z}+\cdots }$$

if the errors were not independent. ^[5]

This is equivalent of finding the magnitude of the resultant of adding orthogonal vectors, each with magnitude equal to the uncertainty, using the Pythagorean theorem.

In signal processing, addition in quadrature is used to find the overall noise from independent sources of noise. For example, if an image sensor gives six digital numbers of shot noise, three of dark current noise and two of Johnson–Nyquist noise under a specific condition, the overall noise is

$${\displaystyle \sigma =6\oplus 3\oplus 2={\sqrt {6^{2}+3^{2}+2^{2}}}=7}$$

digital numbers, ^[6] showing the dominance of larger sources of noise.

Properties

The operation ${\displaystyle \oplus }$ is associative and commutative, ^[7] and

$${\displaystyle {\sqrt {x_{1}^{2}+x_{2}^{2}+\cdots +x_{n}^{2}}}=x_{1}\oplus x_{2}\oplus \cdots \oplus x_{n}.}$$

This means that the real numbers under ${\displaystyle \oplus }$ form a commutative semigroup.

The real numbers under ${\displaystyle \oplus }$ are not a group, because ${\displaystyle \oplus }$ can never produce a negative number as its result, whereas each element of a group must be the result of multiplication of itself by the identity element. On the non-negative numbers, it is still not a group, because Pythagorean addition of one number by a second positive number can only increase the first number, so no positive number can have an inverse element. Instead, it forms a commutative monoid on the non-negative numbers, with zero as its identity.

Implementation

Hypot is a mathematical function defined to calculate the length of the hypotenuse of a right-angle triangle. It was designed to avoid errors arising due to limited-precision calculations performed on computers. Calculating the length of the hypotenuse of a triangle is possible using the square root function on the sum of two squares, but hypot avoids problems that occur when squaring very large or very small numbers. If calculated using the natural formula,

$${\displaystyle r={\sqrt {x^{2}+y^{2}}},}$$

the squares of very large or small values of ${\displaystyle x}$ and ${\displaystyle y}$ may exceed the range of machine precision when calculated on a computer, leading to an inaccurate result caused by arithmetic underflow and overflow. The hypot function was designed to calculate the result without causing this problem. ^[8]

If either input to hypot is infinite, the result is infinite. Because this is true for all possible values of the other input, the IEEE 754 floating-point standard requires that this remains true even when the other input is not a number (NaN). ^[9]

Since C++17, there has been an additional hypot function for 3D calculations: ^[10]

$${\displaystyle r={\sqrt {x^{2}+y^{2}+z^{2}}}.}$$

Calculation order

The difficulty with the naive implementation is that ${\displaystyle x^{2}+y^{2}}$ may overflow or underflow, unless the intermediate result is computed with extended precision. A common implementation technique is to exchange the values, if necessary, so that ${\displaystyle |x|\geq |y|}$, and then to use the equivalent form

$${\displaystyle {\begin{aligned}r&={\sqrt {x^{2}+y^{2}}}\\&={\sqrt {x^{2}\!\left(1+\left({\tfrac {y}{x}}\right)^{2}\right)}}\\&=|x|{\sqrt {1+\left({\tfrac {y}{x}}\right)^{2}}}\left(=|x|+{\frac {y}{|x|}}{\frac {y}{1+{\sqrt {1+\left({\tfrac {y}{x}}\right)^{2}}}}}\right)\!.\end{aligned}}}$$

The computation of ${\displaystyle y/x}$ cannot overflow unless both ${\displaystyle x}$ and ${\displaystyle y}$ are zero. If ${\displaystyle y/x}$ underflows, the final result is equal to ${\displaystyle |x|}$, which is correct within the precision of the calculation. The square root is computed of a value between 1 and 2. Finally, the multiplication by ${\displaystyle |x|}$ cannot underflow, and overflows only when the result is too large to represent. ^[8] This implementation has the downside that it requires an additional floating-point division, which can double the cost of the naive implementation, as multiplication and addition are typically far faster than division and square root. Typically, the implementation is slower by a factor of 2.5 to 3. ^[11]

More complex implementations avoid this by dividing the inputs into more cases:

• When ${\displaystyle x}$ is much larger than ${\displaystyle y}$, ${\displaystyle x\oplus y\approx |x|}$, to within machine precision.
• When ${\displaystyle x^{2}}$ overflows, multiply both ${\displaystyle x}$ and ${\displaystyle y}$ by a small scaling factor (e.g. 2⁻⁶⁴ for IEEE single precision), use the naive algorithm which will now not overflow, and multiply the result by the (large) inverse (e.g. 2⁶⁴).
• When ${\displaystyle y^{2}}$ underflows, scale as above but reverse the scaling factors to scale up the intermediate values.
• Otherwise, the naive algorithm is safe to use.

However, this implementation is extremely slow when it causes incorrect jump predictions due to different cases. Additional techniques allow the result to be computed more accurately, e.g. to less than one ulp. ^[8]

Programming language support

The function is present in many programming languages and libraries, including CSS, ^[12] C++11, ^[13] D, ^[14] Go, ^[15] JavaScript (since ES2015), ^[16] Julia, ^[17] Java (since version 1.5), ^[18] Kotlin, ^[19] MATLAB, ^[20] PHP, ^[21] Python, ^[22] Ruby, ^[23] Rust, ^[24] and Scala. ^[25]

See also

• Euclidean distance
• Alpha max plus beta min algorithm
• Metafont has Pythagorean addition and subtraction as built-in operations, under the names ++ and +-+ respectively.

References

1. Moler, Cleve; Morrison, Donald (1983). "Replacing square roots by Pythagorean sums". IBM Journal of Research and Development. 27 (6): 577–581. CiteSeerX   10.1.1.90.5651 . doi:10.1147/rd.276.0577.
2. Johnson, David L. (2017). "12.2.3 Addition in Quadrature". Statistical Tools for the Comprehensive Practice of Industrial Hygiene and Environmental Health Sciences. John Wiley & Sons. p. 289. ISBN   9781119143017.
3. "SIN (3M): Trigonometric functions and their inverses". Unix Programmer's Manual: Reference Guide (4.3 Berkeley Software Distribution Virtual VAX-11 Version ed.). Department of Electrical Engineering and Computer Science, University of California, Berkeley. April 1986.
4. Beebe, Nelson H. F. (2017). The Mathematical-Function Computation Handbook: Programming Using the MathCW Portable Software Library. Springer. p. 70. ISBN   9783319641102.
5. D.B. Schneider, Error Analysis in Measuring Systems, Proceedings of the 1962 Standards Laboratory Conference, page 94
6. J.T. Bushberg et al, The Essential Physics of Medical Imaging, section 10.2.7, Wolters Kluwer Health
7. Falmagne, Jean-Claude (2015). "Deriving meaningful scientific laws from abstract, "gedanken" type, axioms: five examples". Aequationes Mathematicae . 89 (2): 393–435. doi:10.1007/s00010-015-0339-1. MR   3340218. S2CID   121424613.
8. Borges, Carlos F. (2021), "Algorithm 1014: An Improved Algorithm for hypot(x, y)", ACM Transactions on Mathematical Software, 47 (1): 9:1–9:12, arXiv: 1904.09481 , doi:10.1145/3428446, S2CID   230588285
9. Fog, Agner (2020-04-27). "Floating point exception tracking and NAN propagation" (PDF). p. 6.
10. Common mathematical functions std::hypot, std::hypotf, std::hypotl
11. Measured on ARM and x64 (Intel and AMD) for different compilers with maximum optimization for 32 bit and 64 bit floats.
12. Cimpanu, Catalin. "CSS to get support for trigonometry functions". ZDNet. Retrieved 2019-11-01.
13. "Hypot - C++ Reference".
14. "STD.math - D Programming Language".
15. "Math package - math - PKG.go.dev".
16. "Math.hypot() - JavaScript | MDN".
17. "Mathematics · the Julia Language".
18. "Math (Java 2 Platform SE 5.0)".
19. "hypot - Kotlin Programming Language". Kotlin. Retrieved 2018-03-19.
20. "Square root of sum of squares (Hypotenuse) - MATLAB hypot - MathWorks Benelux".
21. "PHP: Hypot - Manual".
22. "Math — Mathematical functions — Python 3.9.7 documentation".
23. "Module: Math (Ruby 3.0.2)".
24. "F64 - Rust".
25. "Scala Standard Library 2.13.6 - scala.math".

Further reading

• Dubrulle, Augustin A. (1983). "A class of numerical methods for the computation of Pythagorean sums" (PDF). IBM Journal of Research and Development. 27 (6): 582–589. CiteSeerX   10.1.1.94.3443 . doi:10.1147/rd.276.0582..