#### Archived

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

# Optimising the Distance Formula

This topic is 6362 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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 on other sites
yeah you can cut out sqrt().................

##### Share on other sites
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 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

##### Share on other sites
quote:
Original post by Anonypous Moster

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 on other sites
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 on other sites
Thanks guys, that was quite helpful.

Anthracks

1. 1
2. 2
JoeJ
17
3. 3
4. 4
frob
11
5. 5

• 13
• 16
• 13
• 20
• 13
• ### Forum Statistics

• Total Topics
632186
• Total Posts
3004637

×