Alpha max plus beta min algorithm

The alpha max plus beta min algorithm^[1] 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 ${\displaystyle |z|={\sqrt {a^{2}+b^{2}}}}${\displaystyle |z|={\sqrt {a^{2}+b^{2}}}} 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 $${\displaystyle |z|=\alpha ,円\mathbf {Max} +\beta ,円\mathbf {Min} ,}$${\displaystyle |z|=\alpha ,円\mathbf {Max} +\beta ,円\mathbf {Min} ,} where ${\displaystyle \mathbf {Max} }${\displaystyle \mathbf {Max} } is the maximum absolute value of a and b, and ${\displaystyle \mathbf {Min} }${\displaystyle \mathbf {Min} } is the minimum absolute value of a and b.

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

When ${\displaystyle \alpha <1}${\displaystyle \alpha <1}, ${\displaystyle |z|}${\displaystyle |z|} becomes smaller than ${\displaystyle \mathbf {Max} }${\displaystyle \mathbf {Max} } (which is geometrically impossible) near the axes where ${\displaystyle \mathbf {Min} }${\displaystyle \mathbf {Min} } is near 0. This can be remedied by replacing the result with ${\displaystyle \mathbf {Max} }${\displaystyle \mathbf {Max} } whenever that is greater, essentially splitting the line into two different segments.

${\displaystyle |z|=\max(\mathbf {Max} ,\alpha ,円\mathbf {Max} +\beta ,円\mathbf {Min} ).}${\displaystyle |z|=\max(\mathbf {Max} ,\alpha ,円\mathbf {Max} +\beta ,円\mathbf {Min} ).}

Depending on the hardware, this improvement can be almost free.

Using this improvement changes which parameter values are optimal, because they no longer need a close match for the entire interval. A lower ${\displaystyle \alpha }${\displaystyle \alpha } and higher ${\displaystyle \beta }${\displaystyle \beta } can therefore increase precision further.

Increasing precision: When splitting the line in two like this one could improve precision even more by replacing the first segment by a better estimate than ${\displaystyle \mathbf {Max} }${\displaystyle \mathbf {Max} }, and adjust ${\displaystyle \alpha }${\displaystyle \alpha } and ${\displaystyle \beta }${\displaystyle \beta } accordingly.

${\displaystyle |z|=\max {\big (}|z_{0}|,|z_{1}|{\big )},}${\displaystyle |z|=\max {\big (}|z_{0}|,|z_{1}|{\big )},}

${\displaystyle |z_{0}|=\alpha _{0},円\mathbf {Max} +\beta _{0},円\mathbf {Min} ,}${\displaystyle |z_{0}|=\alpha _{0},円\mathbf {Max} +\beta _{0},円\mathbf {Min} ,}

${\displaystyle |z_{1}|=\alpha _{1},円\mathbf {Max} +\beta _{1},円\mathbf {Min} .}${\displaystyle |z_{1}|=\alpha _{1},円\mathbf {Max} +\beta _{1},円\mathbf {Min} .}

Beware however, that a non-zero ${\displaystyle \beta _{0}}${\displaystyle \beta _{0}} would require at least one extra addition and some bit-shifts (or a multiplication), probably nearly doubling the cost and, depending on the hardware, possibly defeat the purpose of using an approximation in the first place.

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

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

• "Extension to three dimensions". Stack Exchange . May 14, 2015.

• Approximation algorithms
• Root-finding algorithms
• Pythagorean theorem

• Articles with short description
• Short description is different from Wikidata