-3

I want to compute 2D distance faster.
We all know the base formula: $$ \left(x\right)^{2}+\left(y\right)^{2}=r^{2} $$ but it require $$ \sqrt{r} $$ which is very heavy computing, my case is 4 millions loop.

I've made this formula $$ a=\frac{\left|x\right|+\left|y\right|}{2\max\left(\left|x\right|,\left|y\right|\right)} $$ $$ \frac{\left(a\left(\left|x\right|+\left|y\right|\right)+2\left(1-a\right)\cdot\max\left(\left|x\right|,\left|y\right|\right)\ \right)}{1.5}=\ r $$ which doesn't require to calculate the square root at all! It is low accuracy but it is acceptable.

Desmos's graph showcase

Are there any quicker distance calculating than this? Thank you very much!

Update

I know this not a good way to approximate the distance, compare to the square root one. So that is why I am asking to learn any better formula (faster calculating) available. Thanks!

p/s: Not so much precision is need but need to be more precise than the Manhattan distance.

Khang Dinh Hoang
  • 11
  • 2
    Just an interest, what is the tool you are using that needs that much to calculate the square root? – Yalikesifulei Feb 06 '23 at 11:38
  • 4
    Why would you need such an approximation? Current algorithms are fast enough for calculating $\sqrt r$ and almost all of the programming languages implement it. – Mostafa Ayaz Feb 06 '23 at 11:38
  • 2
    This is much much more expensive than a square root – Claude Leibovici Feb 06 '23 at 12:12
  • It depends upon your application. For example, if you want to determine if two points are within a certain distance of each other you can just use the square of the distance instead. – John Douma Feb 06 '23 at 13:51
  • 1
    "This is much much more expensive than a square root " indeed , there is no gain using this expression. – Peter Feb 06 '23 at 16:17
  • 1
    @Yalikesifulei I am a game developer and I am trying implement faster way to approximate distance than the original square root, in C#. – Khang Dinh Hoang Feb 07 '23 at 03:20
  • @Claude Leibovici and Peter : Yes I think so too, so I am asking if any quicker formula (for computer) available. – Khang Dinh Hoang Feb 07 '23 at 03:22
  • @John Douma you mean the manhattan distance? Yes that is the fastest way (depend on what I know) to approximate the distance. Now in my case need something that between the precise distance and manhattan distance. – Khang Dinh Hoang Feb 07 '23 at 03:25
  • @KhangDinhHoang No. If you are writing a game, for example, and you want to record a hit on a target if the missile comes within a distance $d$ of the target, then you can use $d^2$ instead. This avoids the computation of the square root and you get the same accuracy. – John Douma Feb 07 '23 at 03:52
  • @John Douma Thank you very much for that! – Khang Dinh Hoang Feb 07 '23 at 04:01
  • https://en.wikipedia.org/wiki/Fast_inverse_square_root might help. has always intrigued me – student91 Feb 08 '23 at 10:29

1 Answers1

1

$$\begin{align}r&=x\sqrt{1+\left (\frac{y}{x}\right)^2}, x\ne 0\\ &=x\cdot \sec t, \tan t=\frac{y}{x}\end{align}$$

If x=0 then you factor the y.

If you implemented a table of secants then you’re a linear interpolation (or a mean average) plus a multiplication away from the result.

WindSoul
  • 2,160