Alpha max plus beta min algorithm

Not to be confused with Minimax or Alpha–beta pruning.

The locus of points that give the same value in the algorithm, for different values of alpha and beta.

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	3.20
1/1	3/8	6.80	4.25
7/8	7/16	12.50	4.91
15/16	15/32	6.25	3.08
$\alpha _{0}$	$\beta _{0}$	3.96	2.41

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.

This article is issued from Wikipedia - version of the 8/2/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Alpha max plus beta min algorithm

See also

References