In one of his chapters (Andre Lamothe), in the book "Tricks of the game programming gurus (second edition)" he wrote a simple looking yet cryptic function simulating the distance formula. This optimized version was very much explained and if anyone can explain this to me, that''ll be great. I just want a basic guideline how what steps he took to get there. I''m sure this math genius used some calculous or something but it can''t be that crazy... or maybe it can because he even noted how "off" the formula was in terms of error percentage. HELLLLPPP! You can check his mini explanation at the bottom of page 474 in the second edition. That''s chapter 8. int Fast_Distance(int x, int y) { x = abs(x); y = abs(y); int mn = MIN(x, y); return (x+y-(mn>>1)-(mn>>2)+(mn>>4)); } -Lewis [m80] Play QUADz MX @ www.m80produxions.com

It''s indeed a nice trick. Try visualizing the graph of sqrt(a+x^2) (where x is the variable and a is a constant), and you''ll see it''s quite linear in the end. Therefore we can build a linear approximation of it. Those shifts just try to multiply the number with the correct approximation value (which is a floating point number). I don''t remember the correct constants right now, but surely you can figure out them from sqrt(a+x^2).

- Mikko Kauppila

I have an even better trick for you.
Precalculate a distance table and take your approximations
from there. It is much much faster.

Damn... thanx. I really appreciate this. I just got back from Amazon (dot com, of course) and I bought that Calculus for dummies book. It talks about that Taylor series thinga-magig. I never though this could be done, but I guess anything is possible. I love math, don''t you?

-Lewis [m80]
Play QUADz MX @
www.m80produxions.com

I would like to make a correction... that''s an idiots guide... I don''t think Dummies have a Calc book. What do you guys think of the "Mathematics for 3D Game Programming and Computer Graphics"
book? Any good?

-Lewis [m80]
Play QUADz MX @
www.m80produxions.com

I doubt that the trick is based on Taylor series. Taylor series is one way of approximating the distance, but it''s very different from Lamothe''s method.

I remember the Lamothe formula goes (for a 2d point x,y):

c = 0.35 // approximation constant

xx = abs(x)
yy = abs(y)

// DIST = BIGGER+SMALLER*CONSTANT

if( xx > yy ) return xx+yy*c;
else return yy+xx*c;

the error is from about 0% to 4% (3% on average)
the source code you presented uses fixed point arithmetic for computing *0.35, which is faster, but requires integers for x and y.

Much of the time on this forum goes to fighting between wether to use lookup tables or pure computation. I don''t want to participate on that, I just want to explain you Lamothe''s method. I really suggest the lounge for flamewars...

- Mikko Kauppila

There is a solution with division that give a fast and moreeee better result.

int Dist(int x, int y ){
if(x > y) return x*SQRTS[(y << SQRT_SHIFT)/x ]) >> SQRT_SHIFT;
else return y*SQRTS[(x << SQRT_SHIFT)/y ]) >> SQRT_SHIFT;
// where SQRTS - precalculated array of 2^SQRT_SHIFT size
}