ofVectorMath length approximations


since sqrt() is just about the single most cpu heavy thing you can do, it’s nice to have some ways to approximate the length of a vector without using it. so here’s a couple of methods i’ve been using in my own vector classes up til this point, i thought it might be nice to share them - i think they’d go very nicely on the ofxVec2f/3f/4f classes :wink:

they both apply Newton’s iterative method for square root approximation, and work very nicely if you pass in a reasonable value for ‘guess’. eg, if you’re tracking the length of a vector over time, with moving endpoints, store the value you got last frame, and use that as your ‘guess’ next frame.

/// not so accurate  
float lengthApprox const( float guess = 1.0f )   
	{ return 0.5f*(guess + lengthSquared()/guess); }  
/// a bit more accurate  
float lengthApprox2 const( float guess = 1.0f )   
	{ return lengthApprox(lengthApprox(guess)); }  

they will work as is in ofxVec2f, 3f, and 4f.


To calculate a vector’s length, square the vector’s components, add the squares, and take the square root of the sum, which you can see in the following equation:

v = < x, y, z >
||v|| = sqrt[(x * x) + (y * y) + (z * z)]

Another optimization is to offer a function that returns the square of the vector’s length instead. This avoids the square root and often in calculations the square of the distance can be used instead.

… oh and how convenient lengthSquared is already in ofxVectorMath :wink:

Out of curiosity I just placed a loop into update() doing 10,000,000 (!) sqrt calculations. Cpu time goes up by 50%. It’s not half as dramatic as I thought.

you mean, 10 million sqrts ups the cpu time from (say) 10% to (say) 15%? or from (say) 10% to (say) 60%?

interesting… i shall have to profile myself…

still, if you need to find nearest neighbour pairs in a set of 1000 3d points, that’s 10 million length() calls just like that.

well you can always set up an outside thread to do the math and have the main thread focus on plugging in the numbers. If you are that concerned about optimizing 2 or 3 sqrt() infused loops then you can go be extreme and use your “guess work” but your precision is going to be way off. You really can’t have gaping errors like 0.1 or 0.5 in physics or vectors since that would be the same as using integers. So suck it up and use sqrt().