alpha max plus beta min algorithm

{{short description|High-speed approximation of the square root of the sum of two squares}}

{{Distinguish|Minimax|Alpha–beta pruning}}

File:AlphaMaxBetaMin.png

The alpha max plus beta min algorithm{{Cite journal |last=Assim |first=Ara Abdulsatar Assim |date=2021 |title=ASIC implementation of high-speed vector magnitude & arctangent approximator |journal=Computing, Telecommunication and Control |volume=71 |issue=4 |pages=7–14 |url=https://infocom.spbstu.ru/en/article/2021.71.01/ |language=en |doi=10.18721/JCSTCS.14401}} 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| = \sqrt{a^2 + b^2} of a complex number {{math|1=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| = \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.960433870103... and \beta_0 = \frac{2 \sin \frac{\pi}{8}}{1 + \cos \frac{\pi}{8}} = 0.397824734759..., giving a maximum error of 3.96%.

class="wikitable" style="text-align:right"

! \alpha\,\!

\beta\,\!Largest error (%)Mean error (%)
1/11/211.808.68
1/11/411.613.20
1/13/86.804.25
7/87/1612.504.91
15/1615/326.253.08
\alpha_0\beta_03.962.41

File:Alpha Max Beta Min approximation.png

Improvements

When \alpha < 1, |z| becomes smaller than \mathbf{Max} (which is geometrically impossible) near the axes where \mathbf{Min} is near 0.

This can be remedied by replacing the result with \mathbf{Max} whenever that is greater, essentially splitting the line into two different segments.

: |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 \alpha and higher \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 \mathbf{Max}, and adjust \alpha and \beta accordingly.

: |z| = \max\big(|z_0|, |z_1|\big),

: |z_0| = \alpha_0\,\mathbf{Max} + \beta_0\,\mathbf{Min},

: |z_1| = \alpha_1\,\mathbf{Max} + \beta_1\,\mathbf{Min}.

class="wikitable" style="text-align:right"
\alpha_0 || \beta_0 || \alpha_1 || \beta_1 || Largest error (%)
107/817/32−2.65%
1029/3261/128+2.4%
100.8982041932668680.485968200201465±2.12%
11/87/833/64−1.7%
15/3227/3271/1281.22%
127/1283/1627/3271/128−1.13%

Beware however, that a non-zero \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.

See also

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

References

{{Reflist}}

  • Lyons, Richard G. Understanding Digital Signal Processing, section 13.2. Prentice Hall, 2004 {{ISBN|0-13-108989-7}}.
  • Griffin, Grant. [http://www.dspguru.com/dsp/tricks/magnitude-estimator DSP Trick: Magnitude Estimator].