Alpha max plus beta min algorithm for three numbers

Question

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.

Answer 1

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.