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.

$|z|={\sqrt {a^{2}+b^{2}}}$

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:

$|z|=\alpha \,\!\mathbf {Max} +\beta \,\!\mathbf {Min}$

Where $\mathbf {Max}$ is the maximum absolute value of a and b and $\mathbf {Min}$ is the minimum absolute value of a and b.

For the closest approximation, the optimum values for $\alpha \,\!$ and $\beta \,\!$ are $\alpha _{0}={\frac {2\cos {\frac {\pi }{8}}}{1+\cos {\frac {\pi }{8}}}}=0.96043387...$ and $\beta _{0}={\frac {2\sin {\frac {\pi }{8}}}{1+\cos {\frac {\pi }{8}}}}=0.39782473...$, giving a maximum error of 3.96%.

$\alpha \,\!$	$\beta \,\!$	Largest error (%)	Mean error (%)
1/1	1/2	11.80	8.68
1/1	1/4	11.61	0.65
1/1	3/8	6.80	4.01
7/8	7/16	12.5	4.91
15/16	15/32	6.25	1.88
$\alpha _{0}$	$\beta _{0}$	3.96	1.30

See also

• Hypot, a precise function or algorithm that is also safe against overflow and underflow

References

• Lyons, Richard G. Understanding Digital Signal Processing, section 13.2. Prentice Hall, 2004 ISBN 0-13-108989-7.
• Griffin, Grant. DSP Trick: Magnitude Estimator.