Archived

This topic is now archived and is closed to further replies.

Anthracks

Optimising the Distance Formula

Recommended Posts

Anthracks    122
This is probably an obvious question, but I wanted to make sure I was right before I went ahead and threw this into my game. For various reasons, I need to implement the "distance formula" for finding the distance between two points (I''m only working in 2D for the moment, so it''s pretty easy heh). And unless I totally forgot my eighth grade math, it goes something like this:
  
double distance(int x1, int y1, int x2, int y2)
{
  return (sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1)));
}
  
Now, this works, but does not strike me as exactly the fastest code on the block. One thing about the way I use this code is that I only need to find the shortest distance between two points from a bunch of them, I don''t care what that distance actually is, just which is closest. So, could I cut out the sqrt() call and still have the shortest distance be the shortest? I assume so. I also assume the sqrt keeps it from being inlineable, which could help. Finally, is there a way to get rid of any of the multiplies? The coordinates could in theory be anywhere so I don''t think I can get away with shifts... I hope this made sense, that isn''t always my strong point . Thanks, Anthracks

Share this post


Link to post
Share on other sites
Mithrandir    607
There''s a quick way of doing an approximate square root (i cant remember off the top of my head, but i will post it when i get home), by taking the first few terms of the taylor polynomial expansion of a square root approximation.



===============================================
Hurry up madness, hurry up disease,
hurry up insanity, hurry up please.
Hooray! I say, for the end of the world.

Share this post


Link to post
Share on other sites
new sqrt = 0.5*(sqrt + n/sqrt)

where sqrt is as approximation, new sqrt is a better approximation, and n is the original number

Although modern Pentiums can now do square roots very fast, there was a thread about this a short while back.

Share this post


Link to post
Share on other sites
Wunibald    122
quote:
Original post by Anonypous Moster

Although modern Pentiums can now do square roots very fast, there was a thread about this a short while back.


I think that was my thread . I was very proud of using a damn complicated approximation (which I didn''t understand, actually).
Then I found out, that a simple sqrt() is faster with the new pentiums...

Wunibald

Share this post


Link to post
Share on other sites
Kylotan    9853
quote:
Original post by Anthracks

double distance(int x1, int y1, int x2, int y2)
{
return (sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1)));
}

Now, this works, but does not strike me as exactly the fastest code on the block. One thing about the way I use this code is that I only need to find the shortest distance between two points from a bunch of them, I don''t care what that distance actually is, just which is closest.

So, could I cut out the sqrt() call and still have the shortest distance be the shortest? I assume so. I also assume the sqrt keeps it from being inlineable, which could help.


Yes, of course. A square root is just a multiplicative function and therefore relative ordering is preserved. (Except where the numbers get so small that precision errors mean you can''t tell them apart, but that''s unlikely with a double.)

Look at the equation again, and you can see some common factors

((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1))
equals
(( a ) * ( a ) + ( b ) * ( b ))
where ''a'' = (x2-x1) and ''b'' = (y2-y1)

So, you could do the following
int xDelta = x2 - x1;
int yDelta = y2 - y1;
return (xDelta * xDelta) + (yDelta * yDelta)

which may be faster. (Many compilers will attempt to do this sort of thing for you, but since it''s simple enough you may as well do it yourself).

Share this post


Link to post
Share on other sites