|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |