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;
}
Yeah, 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.
FWIW, 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.
I 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.
My 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.
Am 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.
To 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.
This is a great book. It basically goes over how the game industry was able to develop itself for the PC, which at the time people believed was only for work. The guys at I'd pioneered a lot of efficient technology whited allowed for games to even be playable on PCs.
The Smashing Pumpkins for their part continued to the joke by adding a sample from Doom to 'Where Boys Fear to Tread' on 'Mellon Collie and the Infinite Sadness'. The booklet contains the following credit: "Explosion from Doom courtesy of id Software, Inc and bobby prince Music""
This is a really great wiki entry. I was searching around after reading it and came across this pic from '92 which is really amazing:
http://bit.ly/qxaxrC
Both Carmacks, Romero, Tom Hall, Kevin Cloud, etc in startup mode :D
I'm a data nerd and I like to see when people click on my links :) For example barely anyone clicked when I posted this on twitter vs. tons of exposure on HN: https://bitly.com/qxaxrC+
Dunno, I just enjoy keeping track of what I post and seeing what's popular, etc!
Fair enough, I guess I forgot about that. It's still a leap of faith to press a bit.ly link by paranoids like me. I should probably use an addon and forget about these.
Here's a video tour of their offices circa 1993, for those who haven't seen it. I think this is a cool look into the beginnings of the company and the (early) excitement surrounding Doom at the time.
It's quite an interesting talk - lots of people have interviewed John Carmack about the history of Doom, and he was certainly a core figure, but I enjoyed hearing a telling from outside the usual "id Software has been continuously successful for decades" frame of reference.
Gotta love the cool stop animated models they used for the sprites in the games, but here's the best bit that I didn't know:
(about the sources for some of the textures)"Among the more unusual sources, one texture was based on Adrian's snakeskin boots, and a bloody texture for the hell levels was created from a photograph of a wound on Cloud's knee"
Awesome. I thought the skin-wall textures in ep.3 were pretty gross. Eww! nerdscabs!
If I remember well, the biggest problem with NeXT was that it was quite expensive! According to the "Master of Doom" book, Carmack pay around U$ 10,000 for one workstation in 1991.
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
Taken from the wikipedia article http://en.wikipedia.org/wiki/Fast_inverse_square_root has the fuller story.