Anthracks 122 Report post Posted March 20, 2001 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 0 Share this post Link to post Share on other sites

Physik 122 Report post Posted March 20, 2001 yeah you can cut out sqrt()................. 0 Share this post Link to post Share on other sites

Mithrandir 607 Report post Posted March 20, 2001 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. 0 Share this post Link to post Share on other sites

Anonypous Moster 122 Report post Posted March 20, 2001 new sqrt = 0.5*(sqrt + n/sqrt)where sqrt is as approximation, new sqrt is a better approximation, and n is the original numberAlthough modern Pentiums can now do square roots very fast, there was a thread about this a short while back. 0 Share this post Link to post Share on other sites

Wunibald 122 Report post Posted March 20, 2001 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 0 Share this post Link to post Share on other sites

Kylotan 9853 Report post Posted March 20, 2001 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 followingint 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). 0 Share this post Link to post Share on other sites

Anthracks 122 Report post Posted March 20, 2001 Thanks guys, that was quite helpful.Anthracks 0 Share this post Link to post Share on other sites