Alpha max plus beta min algorithm

The alpha max plus beta min algorithm is a high-speed approximation of the <a href="/facts/Square_root/AfrzfBdQ">square root</a> of the sum of two squares. The square root of the sum of two squares, also known as <a href="/facts/Pythagorean_addition/MG3rbmWH">Pythagorean addition</a>, is a useful function, because it finds the <a href="/facts/Hypotenuse/hVMauM5f">hypotenuse</a> of a right triangle given the two side lengths, the <a href="/facts/Norm_(mathematics)/xIbR4uE1">norm</a> of a 2-D <a href="/facts/Vector_(geometric)/bCLrdksy">vector</a>, or the <a href="/facts/Magnitude_(mathematics)/KCn9PoF0">magnitude</a> 
 
 
 
 
 |
 
 z
 
 |
 
 =
 
 
 
 a
 
 2
 
 
 +
 
 b
 
 2
 
 
 
 
 
 
 {\displaystyle |z|={\sqrt {a^{2}+b^{2}}}}
 
 of a <a href="/facts/Complex_number/2w7mqI7e">complex number</a> z = a + bi given the <a href="/facts/Real_number/R02gw5Pb">real</a> and <a href="/facts/Imaginary_number/6Xh9W3hq">imaginary</a> 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

|
        
        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%.

<table><tbody><tr><th> α {\displaystyle \alpha \,\!} </th><th> β {\displaystyle \beta \,\!} </th><th>Largest error (%)</th><th>Mean error (%)</th></tr><tr><td>1/1</td><td>1/2</td><td>11.80</td><td>8.68</td></tr><tr><td>1/1</td><td>1/4</td><td>11.61</td><td>3.20</td></tr><tr><td>1/1</td><td>3/8</td><td>6.80</td><td>4.25</td></tr><tr><td>7/8</td><td>7/16</td><td>12.50</td><td>4.91</td></tr><tr><td>15/16</td><td>15/32</td><td>6.25</td><td>3.08</td></tr><tr><td> α 0 {\displaystyle \alpha _{0}} </td><td> β 0 {\displaystyle \beta _{0}} </td><td>3.96</td><td>2.41</td></tr></tbody></table>

Alpha max plus beta min algorithm open-in-new

Alpha max plus beta min algorithm