Old and somewhat contrived example, but the first thing to pop into my head is the famous fast inverse square root function. float FastInvSqrt(float x) {
float xhalf = 0.5f * x;
int i = *(int*)&x; // evil floating point bit level hacking
i = 0x5f3759df - (i >> 1); // what the fuck?
x = *(float*)&i;
x = x*(1.5f-(xhalf*x*x));
return x;
}
I can't think of a way to write a test that sufficiently explains "gets within a certain error margin of the correct answer yet is much much faster than the naive way."The only way to test an expected input/output pair is to run the input through that function. If you test that, you're just testing that the function never changes. What if the magic number changed several times during development, do you recalculate all the tests? You could create the tests to be within a certain tolerance of the number. Well how do you stop a programmer from replacing it with return 1.0/sqrt(x);
And then complaining when the game now runs at less than 1 frame per second?Here's a commented version of the same function from betterexplained.com. float InvSqrt(float x){
float xhalf = 0.5f * x;
int i = *(int*)&x; // store floating-point bits in integer
i = 0x5f3759df - (i >> 1); // initial guess for Newton's method
x = *(float*)&i; // convert new bits into float
x = x*(1.5f - xhalf*x*x); // One round of Newton's method
return x;
}
It's still very magic looking to me, but now I get vaguely that it's based on Newton's method and what each line is doing if I needed to modify them.I actually just found this article [0] where someone is trying to find the original author of that function, and no one on the Quake 3 team can remember who wrote it, or why it was slightly different than other versions of the FastInvSqrt they had written. > which actually is doing a floating point computation in integer - it took a long time to figure out how and why this works, and I can't remember the details anymore This made me chuckle. The person eventually tracked down as closest to having written the original thing had to rederive how the function works the first time, and can't remember exactly how it works now. I think the answer is both tests and documentation. Sometimes you do need both. Sometimes you don't, but the person after you will. [0] https://www.beyond3d.com/content/articles/8/ |
Using Ruby and its built-in minitest gem:
1. Write a test that does minitest assert_in_epsilon(x,y,e)
2. Write a minitest benchmark test that compares the speed of the fast function with the speed of the naive function.
Notice the big advantage for long term projects: if the hack ever ceases to work then you'll know immediately. This actually happens in practice, such as math hacks that use 32-bit bit shifts that started failing when chip architecture got wider.
> no one on the Quake 3 team can remember who wrote it
Exactly. We have the code file, but not any documentation separate from the code, such as notes, plans, attempts, reasoning, etc.