I wrote a small bit of code to test what the speed of the various 
approximation methods was.  The code was complied with g++ and the times 
given for each method are for 100000000 calls to the function.  First, 
the functions I tested:

// Naive method
inline bool isect1(double aSq, double bSq, double dSq) {
     return sqrt(dSq) < sqrt(aSq) + sqrt(bSq);
}

// Slime's approximate method
inline bool isect2(double aSq, double bSq, double dSq) {
     return dSq < aSq + bSq + 2*std::max(aSq,bSq);
}

// Suggested by bart, but with a bugfix.
// Avoids a sqrt, but uses a few multiplies
inline bool isect3(double aSq, double bSq, double dSq) {
     double t1 = aSq+bSq;
     double t2 = dSq - t1
     return (dSq < t1) || (4*aSq*bSq > t2*t2);
}

// Naive method using a fast approximate sqrt
inline bool isect4(double aSq, double bSq, double dSq) {
     return fastSqrt(dSq) < fastSqrt(aSq) + fastSqrt(bSq);
}

and now the times under various optimization levels:


---------- O0
time for isect1 = 9.66935
time for isect2 = 2.03143
time for isect3 = 2.18224
time for isect4 = 7.03525

---------- O1
time for isect1 = 5.13777
time for isect2 = 0.413757
time for isect3 = 0.413756
time for isect4 = 0.0376559

---------- O2
time for isect1 = 0.564358
time for isect2 = 0.276049
time for isect3 = 0.305847
time for isect4 = 0.0381372

---------- O3
time for isect1 = 0.564529
time for isect2 = 0.159936
time for isect3 = 0.206905
time for isect4 = 0.0376384


It looks like my initial suggestion implemented in isect4 is the fastest 
when you have optimization turned on, by a margin which rather surprises 
me.  It takes about as long as simply computing the incorrect formula 
'dSq < aSq + bSq', which seems almost impossibly fast.  Nevertheless 
I've checked the results and it seems to work pretty well despite the 
approximation in the sqrt call.  If you don't want to live with the 
approximation, however, bart's method seems to be the best choice.

Post a reply to this message