Talk:Alpha max plus beta min algorithm

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Choosing your non-constant alpha and beta non-arbitrarily

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 polish the solution?

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:

{\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

r_{k}

, you can refine it to

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]

Is there one wrong parameter set?

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]

Examples don't seem practical

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]

Polar plot

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]