Alpha max plus beta min algorithm
The alpha max plus beta min algorithm is a high-speed approximation of the square root of the sum of two squares. The square root of the sum of two squares, also known as Pythagorean addition, is a useful function, because it finds the hypotenuse of a right triangle given the two side lengths, the norm of a 2-D vector, or the magnitude of a complex number z = a + bi given the real and imaginary parts.
The algorithm avoids performing the square and square-root operations, instead using simple operations such as comparison, multiplication, and addition. Some choices of the α and β parameters of the algorithm allow the multiplication operation to be reduced to a simple shift of binary digits that is particularly well suited to implementation in high-speed digital circuitry.
The approximation is expressed as
where is the maximum absolute value of a and b and is the minimum absolute value of a and b.
For the closest approximation, the optimum values for and are and , giving a maximum error of 3.96%.
|Largest error (%)||Mean error (%)|
- Hypot, a precise function or algorithm that is also safe against overflow and underflow