3 ms·
One really nifty piece of code that I associate id-software with is the 0x5f3759df hack. Though it was probably known before, Hakmem would be the first place to
by srean 15y ago
One really nifty piece of code that I associate id-software with is the 0x5f3759df hack. Though it was probably known before, Hakmem would be the first place to look.
I am sure there are many more such bit twiddling and magic number hacks, but nothing quite as useful to me than this magic to compute the reciprocal of a square root. The only other floating point operations that comes up this frequently in what I do are log and exp.
In my day to day coding (not that I code every day, far from it) I have nothing to do with game engines, yet inverse square root shows up in almost every corner (pun intended) in the vector manipulation code, for example in finding the cosine similarity between two documents.
Does not work for double precision, 64 bit, and nothing I write is so performance critical that it demands the use of this trick, but its still fun
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) );
return y;
}
Taken from the wikipedia article http://en.wikipedia.org/wiki/Fast_inverse_square_root http://en.wikipedia.org/wiki/Fast_inverse_square_root has the fuller story.
- iliis 15y agoYeah, this is really cool :) A favorite of mine is the xor-swap: While not useful in pratice for me, you can get quite stunned faces if you tell your friends, that a swap is possible without a third variable. x = x xor y y = x xor y x = x xor y It's also possible to use addition and subtraction instead of xor.
- shrikant 15y agoFWIW, pretty much every 3rd (penultimate) year engineering student in India knows the xor-swap, I should think (only they might not call it that, because they've just memorised the procedure, and have very little idea why it works... /cynical) This is one of the most common questions in 'technical interviews' when big IT companies are recruiting fresh grads. (See http://www.allinterview.com/showanswers/17145.html http://www.allinterview.com/showanswers/17145.html)
- srean 15y agoI am not sure where your cynicism or contempt is coming from. There is not much to a deeper understanding of xor-swap. If one knows the xor truth table one knows why it works, and knowing the truth table is essentially an act of memorization. I hope they are exposed to digital logic way before 3rd year. On the other hand cases where this will not work in the current form, perhaps needs a somewhat deeper understanding of bit lay out. Say if one were to swap two unicode characters from void * pointers to them.
- shrikant 15y agoMy cynicism (not contempt - I know that the students are under various sorts of pressures) stems from personal experience. It's not much good explaining how simple it is to understand the xor-swap - it doesn't change the fact that the majority of engineering students go to the link like the one I posted, compile a list of questions and answers, and rattle off answers before the question is even completed in the interviews. It's like knowing [any interesting method] can be used to accomplish a task, without knowing why said method works. edit: I realise all this is OT, but I was downvoted for my earlier post and felt the need to defend it.
- deleted 15y ago[deleted]
- MarkMc 15y agoAm I the only one that thinks this would be a really BAD interview question? There'd be no way to tell if the candidate had memorised the answer or had worked it out on the fly.
- JeanPierre 15y agoTo elaborate on its usefullness: An XOR-swap is only useful when you do not have space for a new pointer, otherwise, making a new temporary variable will on most processors be faster than XOR-swapping.
- onemoreact 15y agoI would assume you need to be using regesters for three XOR's to be slower than a temperary variable.
- baq 15y agobeen used in many-a-obfuscate-a-bug-contests for what happens when x == y.
- amalcon 15y agoI'm almost sad that this isn't useful on modern processors (thanks to an SSE instruction that computes this). It's just such a crazy math hack.