6
$\begingroup$

There exists fast algorithm to approximate length of 2D vector - Alpha max plus beta min algorithm.

It says that $\alpha\cdot\max(x,y)+\beta\cdot\min(x,y)\approx\sqrt{x^2+y^2}$ for some constants $\alpha$ and $\beta$.

Also there exists constants $\alpha_0$ and $\beta_0$ that give closest approximation (smallest error).

$$\alpha_0 = \frac{2 \cos \frac{\pi}{8}}{1 + \cos \frac{\pi}{8}},\ \beta_0 = \frac{2 \sin \frac{\pi}{8}}{1 + \cos \frac{\pi}{8}}$$

I feel like similar algorithm exist for approximating length of 3D vector with formula: $$\sqrt{x^2+y^2+z^2}\approx\alpha\cdot\max(x,y,z)+\beta\cdot \text{medium}(x,y,z)+\gamma\cdot\min(x,y,z)$$

I'm wondering what values $\alpha_0$, $\beta_0$ and $\gamma_0$ have and how to find them.

$\endgroup$
0

2 Answers 2

3
$\begingroup$

Assuming $\max(x, y, z), \min(x,y,z), \operatorname{med}(x,y,z)$ are really $|\max(x, y, z)|, |\min(x, y, z)|, |\operatorname{med}(x, y, z)|$.

Not a real proof, only a sketch. Since the formula is symmetrical under permutations of $x, y, z$, let's assume $0 \leq x \leq y \leq z$, so $$ \sqrt{x^2 + y^2 + z^2} = \alpha x + \beta y + \gamma z. $$ Since we're interested in relative error, consider a point on the unit circle. $z^2 = 1 - x^2 - y^2$. The error is the absolute deviation between $\alpha x + \beta y + \gamma z$ and one. The condition $0 \leq x \leq y \leq z$ on the unit circle is equivalent to the following conditions $$ 0 \leq x \leq y\\ \sqrt{1-x^2-y^2} \geq y \Leftrightarrow x^2 + 2y^2 \leq 1 $$ So we came up to a minimax problem $$ \begin{aligned} \operatorname{minimize}\limits_{\alpha, \beta, \gamma} \max_{\substack{x \geq 0\\y \geq x\\x^2 + 2y^2 \leq 1}} \big|1 - \alpha x - \beta y - \gamma \sqrt{1-x^2-y^2}\big| \end{aligned} $$ That is a tough one.

We can suppose that the maximum deviation is equal at three corners and opposed to the deviation at local extremum in the interior.

The interior extremum is simple due to the geometric meaning. It is equal to distance from the plane given by $C = \alpha x + \beta y + \gamma z$ to the sphere origin subtracted one (sphere radius). So the deviation at extremum is $$ \Delta = \sqrt{\alpha^2 + \beta^2 + \gamma^2} - 1. $$ The deviation at the corners $(0,0),\,(0,\frac{1}{\sqrt{2}}),(\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}}))$ is computed easily: $$ \Delta_1 = 1 - \gamma\\ \Delta_2 = 1 - \frac{\beta + \gamma}{\sqrt{2}}\\ \Delta_3 = 1 - \frac{\alpha+\beta+\gamma}{\sqrt{3}} $$ Solving $\Delta = \Delta_1 = \Delta_2 = \Delta_3$ for $\alpha, \beta, \gamma$ we obtain $$\begin{aligned} \alpha = \frac{1}{4} \left(2 \sqrt{14+6 \sqrt{2}+3 \sqrt{3}}-\left(2+\sqrt{2}\right) \left(1+\sqrt{3}\right)\right) &\approx 0.29870618761437979596\\ \beta = \operatorname{root}_6(1 - 4 z - 14 z^2 + 32 z^3 + 45 z^4 - 20 z^5 - 20 z^6 + 4 z^7 + z^8) &\approx 0.38928148272372526647\\ \gamma = \operatorname{root}_8(1 - 4 z - 2 z^2 + 20 z^3 - 3 z^4 - 32 z^5 + 4 z^6 + 16 z^7 + z^8) &\approx 0.93980863517232523127 \end{aligned} $$ The error $1 - \gamma$ is sligtly above $6\%$. Note that I accidentally reversed your $\alpha. \beta, \gamma$. That result looks promising, but may be wrong. Note that $\beta$ and $\gamma$ are pretty close to the 2D optimals.

I've made a simple Mathematica script to have a look at the minimax problem. Here it is

Manipulate[
 ContourPlot[\[Alpha] x + \[Beta] y + \[Gamma] Sqrt[1 - x^2 - y^2] - 
   1, {x, 0, 1}, {y, 0, 1}, 
  RegionFunction -> Function[{x, y}, x <= y && x^2 + 2 y^2 <= 1],
  Contours -> Range[-0.2, 0.2, 0.01]
  ]
 , {{\[Alpha], 0.2987061876143797`}, 0, 
  1}, {{\[Beta], 0.38928148272372454`}, 0, 
  1}, {{\[Gamma], .9398086351723256`}, 0, 1}]

So it appears that the suggestion is sane and we had found at least local optimum of the problem.

$\endgroup$
2
$\begingroup$

The approximation given by @uranix is nice, but can be improved slightly, because we know the hypotenuse is never shorter than the largest of the three inputs.

So, borrowing the nice constants given by @uranix and assuming $0<=z<=y<=x$:

const double alphaMax = 0.9398086351723256, betaMed = 0.38928148272372454, gammaMin = 0.2987061876143797;
double hypotenuse = Max(x, alphaMax * x + betaMed * y + gammaMin * z);

This clamps the errors when x is relatively much larger than y and z; a common special case where the errors otherwise would be relatively large and noticeable.

Side-note: Because the multiplications are with constants, they could be approximated with bit-shifts and additions. This is most useful when using fixed-point arithmetic on embedded systems, where floating-point and multiplications may be expensive.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.