Talk:Alpha max plus beta min algorithm

It seems that the accuracy of the estimate depends both on your choice of alpha and beta, and also on the magnitude relationship between a and b in the sqrt(a^2+b^2). Im just wondering how we might take a look at a and b beforehand, and choose a more optimal alpha and beta for the situation.

Is there a way to compute a new estimate of hypot from this starting condition like is done with typical sqrt algorithms? --Jaded-view (talk) 03:29, 5 June 2008 (UTC) [reply ]

You could apply the Newton method:

${\displaystyle {\begin{aligned}&r:=\alpha \max\{|a|,|b|\}+\beta \min\{|a|,|b|\}\\&r={\sqrt {a^{2}+b^{2}}}\Leftrightarrow f(r):=a^{2}+b^{2}-r^{2}=0\\&r:=r-{\frac {f(r)}{f'(r)}}={\frac {r^{2}+a^{2}+b^{2}}{2r}}\end{aligned}}}${\displaystyle {\begin{aligned}&r:=\alpha \max\{|a|,|b|\}+\beta \min\{|a|,|b|\}\\&r={\sqrt {a^{2}+b^{2}}}\Leftrightarrow f(r):=a^{2}+b^{2}-r^{2}=0\\&r:=r-{\frac {f(r)}{f'(r)}}={\frac {r^{2}+a^{2}+b^{2}}{2r}}\end{aligned}}}

This means if you have a solution ${\displaystyle r_{k}}${\displaystyle r_{k}}, you can refine it to ${\displaystyle r_{k+1}={\frac {r_{k}^{2}+a^{2}+b^{2}}{2r_{k}}}}${\displaystyle r_{k+1}={\frac {r_{k}^{2}+a^{2}+b^{2}}{2r_{k}}}}.

I assume that this refining is not very fast because of the division but it could still be faster than an accurate square root calculation. Hybrid Dog (talk) 09:03, 3 August 2020 (UTC) [reply ]

The parameter set alpha=7/8 and beta=15/16 can't be right. I tried to plot that and the graph looks completely different. My guess is that this should have been something like beta=15/32. Most beta values are close to 1/2.

TomF —Preceding unsigned comment added by 77.191.238.62 (talk) 22:56, 26 December 2008 (UTC) [reply ]

This has now been corrected to alpha = 7/8 and beta = 7/16. Gaius Cornelius (talk) 12:06, 2 September 2009 (UTC) [reply ]

This formula is extremely useful, but I have a question: Why are the examples not very good approximations of the ideal alpha and beta? For example, alpha = 31/32 and beta = 13/32 outperforms all of the other examples, and (similarly to most of the others) only requires 2 multiplies and one shift to apply those constants, with similar bit-depth requirements.

It might also be worth showing how well 16-bit approximations do (i.e. alpha = 62941/65536 and beta = 26070/65536). Many archetectures have extremely efficient and/or SIMD-able 16-bit multiplies, and those values do an excellent job.

Nathaniel bogan (talk) 18:52, 27 January 2011 (UTC) [reply ]

Well just as an example (7/8, 7/16) can be done just using 2 shifts, 1 add and 1 sub:

 len = mx + (mn >> 1);
 len -= (len >> 3);

I agree that it would not hurt to add the 16bit approximation as well --92.76.235.178 (talk) 22:26, 13 June 2011 (UTC) [reply ]

Wouldn't it be better to add a polar plot with the results of this function? as it more intuitively shows how this formula works. (a polar plot will show an octagon)213.126.27.106 (talk) 10:19, 12 August 2013 (UTC) [reply ]

It wouldn't be a polygon: here is the plot for close to optimal values: Plot on wolfram alpha — Preceding unsigned comment added by 213.137.178.134 (talk) 13:59, 24 April 2014 (UTC) [reply ]

Yes, but the opposite is true, in that the set of points that give the same value by the function form an octagon. (forgot I had to make that transformation first) Plot on wolfram alpha 37.153.248.249 (talk) 12:41, 14 May 2014 (UTC) [reply ]

• Start-Class mathematics articles
• Unknown-priority mathematics articles