Htykuut

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$.

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 cdotvec{ds}+...$

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

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.45times 10^{-8}$ while using $a=frac 34$ and $b=frac 14$ would give $Phi=1.88 times 10^{-5}$.