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 | z | = 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.

Formulation

The approximation is expressed as | z | = α M a x + β M i n , {\displaystyle |z|=\alpha \,\mathbf {Max} +\beta \,\mathbf {Min} ,} where M a x {\displaystyle \mathbf {Max} } is the maximum absolute value of a and b, and M i n {\displaystyle \mathbf {Min} } is the minimum absolute value of a and b.

For the closest approximation, the optimum values for α {\displaystyle \alpha } and β {\displaystyle \beta } are α 0 = 2 cos ⁡ π 8 1 + cos ⁡ π 8 = 0.960433870103... {\displaystyle \alpha _{0}={\frac {2\cos {\frac {\pi }{8}}}{1+\cos {\frac {\pi }{8}}}}=0.960433870103...} and β 0 = 2 sin ⁡ π 8 1 + cos ⁡ π 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%.

Improvements

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

| z | = max ( M a x , α M a x + β M i n ) . {\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 } and higher β {\displaystyle \beta } can therefore increase precision further.

This can be improved even further by, instead of using | z 0 | = 1 ⋅ M a x + 0 ⋅ M i n {\displaystyle |z_{0}|=1\cdot \mathbf {Max} +0\cdot \mathbf {Min} } as the second estimate, use a second pair of parameters α 0 {\displaystyle \alpha _{0}} and β 0 {\displaystyle \beta _{0}}, with α 1 {\displaystyle \alpha _{1}} and β 1 {\displaystyle \beta _{1}} adjusted accordingly.

| z | = max ( | z 0 | , | z 1 | ) , {\displaystyle |z|=\max \left(|z_{0}|,|z_{1}|\right),}

| z 0 | = α 0 M a x + β 0 M i n , {\displaystyle |z_{0}|=\alpha _{0}\,\mathbf {Max} +\beta _{0}\,\mathbf {Min} ,}

| z 1 | = α 1 M a x + β 1 M i n . {\displaystyle |z_{1}|=\alpha _{1}\,\mathbf {Max} +\beta _{1}\,\mathbf {Min} .}

Of course, a non-zero β 0 {\displaystyle \beta _{0}} requires at least one extra addition and some bit-shifts (or a multiplication), nearly doubling the cost and, depending on the hardware, possibly defeating the purpose of using an approximation in the first place.

See also

• 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 ISBN0-13-108989-7.
• Griffin, Grant. .

External links

• . Stack Exchange. May 14, 2015.