Approximation of square root of sum of two squared terms

Question

I have the following equation

$\sqrt{(x_a-x_n)^2+(y_a-y_n)^2}$. I want to get rid of square-root and find an approximation which contains only $x_a,x_n,y_a,y_n$ (there should not be any other non-linear operator in the approximation). Can anyone help me in this matter and guide me to the right direction?

$x_n <x_a, y_n<y_a, y_a<x_a$ and $x_a,x_n,y_a,y_n \in[-1,1]$. However, $y_n$ is not always less than $x_n$.

Answer 1

Let $\vec{r}=<x_n,y_n>$, $\vec{r_0}=<x_a,y_a>$

$d^2=(\vec{r}-\vec{r_0})^2$

$d=\sqrt{r_n^2+ r_0^2-2 \vec{r_n} \cdot \vec{r_0}}$

From here, I Think there are several options.

With some tweaking, I think you can expand with legendre polynomials.

There's also a vector version of Taylor Series applicable.:

$f(x,y)=f(x_0,y_0)+\nabla f \cdot\vec{ds}+...$

Answer 2

You are not very explicit about the kind of function you allow, nor the desired accuracy.

Your expression (Euclidean distance between two points) is essentially the square root of

$$(x_a-x_n)^2+(y_a-y_n)^2$$

which only uses the elementary operations. So you can focus on just the square root function, for arguments between $0$ and $8$.

If you can hack into the floating-point representation, you can transform the value to a number between $1$ and $2$ and an integer power of $2$. Then the square root will be the square root of the number times two to a half-integer power, i.e. an integer or an integer times $\sqrt2$.

The square root function is very smooth and simple, and even a linear approximation could do ! There are numerous options such as parabolic or cubic interpolation or approximation.

---

Another approach is by considering the largest of $|x_a-x_n|,|y_a-y_n|$ (e.g. $x$) and write

$$\sqrt{(x_a-x_n)^2+(y_a-y_n)^2}=|x_a-x_n|\sqrt{1+\left(\frac{y_a-y_n}{x_a-x_n}\right)^2}.$$

Now you only have to approximate $\sqrt{1+t^2}$ in the range $[0,1]$.

(Or $\sqrt{1+t}$ if you can afford to square $t$ explicitly, giving the same curve as above.)

---

Last but not least, you may consider the wonderful Moller-Morisson algorithm that only uses the four basic operations as has an excellent convergence speed. https://blogs.mathworks.com/images/cleve/moler_morrison.pdf

Answer 3

Starting from Yves Daoust's answer.

A good approximation of $\sqrt{1+t^2}$ could be obtained using the simplest Padé approximant of it (built at $t=0$). This would be $$\sqrt{1+t^2}\sim \frac {4+3t^2}{4+t^2}$$ If more accuracy is required, we can minimize $$\Phi=\int_0^1 \left(\sqrt{t^2+1}-\frac{1+a t^2}{1+b t^2}\right)^2 \, dt$$ which has a (very nasty) expression. Numerically, $a= 0.689417$ and $b=0.195385$ corresponding to $\Phi=8.45\times 10^{-8}$ while using $a=\frac 34$ and $b=\frac 14$ would give $\Phi=1.88 \times 10^{-5}$.