Comics

[Haggis_McMutton]

Unique values with unexplained meaning or multiple occurrences which could (preferably) be replaced with named constants

That's what I meant.

Anyway, the magic number mentioned in the comic (0x5f375a86) refers to this: http://en.wikipedia.org/wiki/Fast_inverse_square_root

tl;dr version:
Computers can't do square root very fast. In fact it can be hundreds of times slower than addition/subtraction/multiplication.
Computer games need a shitload of square root calculations for physics simulation, and they need them FAST. Approximate methods are usually used.
At some point, years after the game was published, someone made public the inverse square root calculation method in Quake III Arena. The interesting bit is this: (also it has the original comments)

Code: Select all

i  = * ( long * ) &y;                       // evil floating point bit level hacking
i  = 0x5f3759df - ( i >> 1 );               // what the f*ck?
y  = * ( float * ) &i;


I can't really explain what's going on there, but besides the magic number poping out of nowhere, nothing really makes sense in those 3 lines. If you saw it without context you'd think it's some guy who just picked up a "Learn C in 20 days" book and is writing out gibberish.
However this method turns out to have been faster than any other method known at the time(maybe it still is, I dunno). Also no one knows exactly where the code originates. Judging from the comments it's pretty clear the Quake guys didn't write it themselves.

tl;dr tl;dr
0x5f3759df is magic yo. Aliens probably did it.

[BigBallinStalin]

Cool. Thanks! That makes a lot more sense, but I still suspect that aliens were involved.

[Haggis_McMutton]

Edit:
Actually, I was just wondering how one comes up with realistic looking math nonsense for the blackboard and started looking at the equations.
First one is totally based on Bayes Theorem (probably). BOOYAH +1 to nerd cred.

[natty dread]

Click image to enlarge.

[MeDeFe]

I like most meats, but I have this crazy aversion towards liver. I just can't stand the stuff.

Actually I could never stand liver either. I even hate the smell.

Huh. And liver was my favourite meat before I went vegetarian. With lingonberry jam and grated carrots... It would have been heavenly, if there were such a thing.

[natty dread]

I can't really explain what's going on there, but besides the magic number poping out of nowhere, nothing really makes sense in those 3 lines. If you saw it without context you'd think it's some guy who just picked up a "Learn C in 20 days" book and is writing out gibberish.
However this method turns out to have been faster than any other method known at the time(maybe it still is, I dunno). Also no one knows exactly where the code originates. Judging from the comments it's pretty clear the Quake guys didn't write it themselves.

tl;dr tl;dr
0x5f3759df is magic yo. Aliens probably did it.

As far as I can tell (and please take all this with a grain of salt), the floating point number is being "directly" converted into an integer by abusing pointers. Then, some weird binary magic is done on the number, then it's converted back to a float. By directly I mean the bits are simply moved from the floating point number to the integer, no actual "conversion" is really taking place.

In the "binary magic" part, apparently first the faux-integer is shifted to the right by 1 bit. Now, usually this would simply halve the integer, but since the integer is actually a float masquerading as an integer, this apparently does some funky stuff that I don't quite understand - it halves both the exponent and the fraction of the float, assuming it's a positive number, and the exponent is even - if the exponent is odd then the last bit of the exponent is shifted over to the fraction side. Ok...

So then, this resulting number is substracted from the magic number, and the result of this is converted back to float.

I still don't really understand the math behind this, I just (maybe, partially) understand how the programming side works... no idea how this is supposed to give a inverse square root or something. f*ck, I'm not 100% on what an inverse square root even is.

[ender516]

Well, from the reading I did on the matter, the inverse square root is actually what I would call the reciprocal of the square root: 1 divided by the square root, or x to the power of negative one-half. The value obtained by that crazy code is not the correct value, but apparently makes an excellent guess, which is corrected by Newton's approximation method, which basically takes an answer to a problem and runs it through the inverse function to see if it's right and uses the error to construct another guess (which hopefully is closer to the truth). A lot of fancy math in computers use Newton. Some functions converge to the right answer faster than others, but often the key is making a good first guess.

[Army of GOD]

I've taken two classes in C++ and I still don't understand why pointers exist. Then again, that's probably because they were introductory classes so I wouldn't have NEEDED them but still.

[ender516]

I'm off to my first official training in C++ starting in just over a week, but my guess is they exist in C++ because they existed in C and no one was sure that they could live without them.

[Army of GOD]

this is in reference to the cartoon Avater, not the movie:

[natty dread]

I've taken two classes in C++ and I still don't understand why pointers exist. Then again, that's probably because they were introductory classes so I wouldn't have NEEDED them but still.

Pointers point to locations in the memory. You can store variables in memory locations and pointers help you find them afterwards.

[natty dread]

This might explain things

Click image to enlarge.

[natty dread]

Click image to enlarge.

[Haggis_McMutton]

As far as I can tell (and please take all this with a grain of salt), the floating point number is being "directly" converted into an integer by abusing pointers. Then, some weird binary magic is done on the number, then it's converted back to a float. By directly I mean the bits are simply moved from the floating point number to the integer, no actual "conversion" is really taking place.

In the "binary magic" part, apparently first the faux-integer is shifted to the right by 1 bit. Now, usually this would simply halve the integer, but since the integer is actually a float masquerading as an integer, this apparently does some funky stuff that I don't quite understand - it halves both the exponent and the fraction of the float, assuming it's a positive number, and the exponent is even - if the exponent is odd then the last bit of the exponent is shifted over to the fraction side. Ok...

So then, this resulting number is substracted from the magic number, and the result of this is converted back to float.

I still don't really understand the math behind this, I just (maybe, partially) understand how the programming side works... no idea how this is supposed to give a inverse square root or something. f*ck, I'm not 100% on what an inverse square root even is.

Hmm, yeah, It's really crazy. It definitely looks like a rookie mistake when you first see it, with the nonsensical casts.
It probably says something about C that it is even possible to do that. I don't think it would be possible in any other major modern language.

Also, I read thjat someone did a brute force search to get the best constant for the magic number, and the one that was used is apparently second best, with the 0x5f375a86 actually mentioned in the comic being better.

Also, today's SMBC:

Click image to enlarge.

[natty dread]

Click image to enlarge.

Click image to enlarge.

[natty dread]

It probably says something about C that it is even possible to do that. I don't think it would be possible in any other major modern language.

Oh, that's not true. It's quite possible in any low-level programming language (ie. language that compiles directly to machine code), which allows direct manipulation of memory locations - that is, almost any language that allows the use of pointers. Also, any language that allows inline assembler, since everything is obviously possible in assembler.

C++, C#, D, Objective-C should all be able to do it. I'm sure many others can as well.

[Haggis_McMutton]

It probably says something about C that it is even possible to do that. I don't think it would be possible in any other major modern language.

Oh, that's not true. It's quite possible in any low-level programming language (ie. language that compiles directly to machine code), which allows direct manipulation of memory locations - that is, almost any language that allows the use of pointers. Also, any language that allows inline assembler, since everything is obviously possible in assembler.

C++, C#, D, Objective-C should all be able to do it. I'm sure many others can as well.

Yeah, sure, but I kind of view those as derivatives of C.

I was thinking more in the lines of python, ruby, scheme, any functional language obviously.
I'm not even sure if it's possible in Java.

Basically you need explicit pointers and lax type safety, I think.

[natty dread]

It probably says something about C that it is even possible to do that. I don't think it would be possible in any other major modern language.

Oh, that's not true. It's quite possible in any low-level programming language (ie. language that compiles directly to machine code), which allows direct manipulation of memory locations - that is, almost any language that allows the use of pointers. Also, any language that allows inline assembler, since everything is obviously possible in assembler.

C++, C#, D, Objective-C should all be able to do it. I'm sure many others can as well.

Yeah, sure, but I kind of view those as derivatives of C.

I was thinking more in the lines of python, ruby, scheme, any functional language obviously.
I'm not even sure if it's possible in Java.

Basically you need explicit pointers and lax type safety, I think.

Well, obviously you can't do it in higher-level interpreted languages. Java, Python, Ruby and such are all languages which don't compile into machine code, they instead compile the source into a bytecode which runs in their own language-specific virtual machines. So of course you can't directly manipulate memory locations in those languages, since all data and code are virtualized and the languages don't allow direct access to the system.

This doesn't mean those languages are less useful though, it just means they are designed for a different purpose. Making the code run on a virtual machine makes it easier to code cross-platform implementations, since the programmer doesn't have to worry about the low-level hardware stuff. It also makes the languages more useful for scripting purposes.

However, interpreted languages aren't very suitable for uses that require very efficient usage of system resources, such as graphics engines for games or such.

C# is an "interesting" exception - it's a bit of both, and depending on your point of view, it either has the advantages or the disadvantages of both types... basically, it's an interpreted language, but it doesn't run on a virtual machine, instead the code is compiled at run-time to machine code. It's called "just-in-time compiling". C# allows the use of pointers, but only in code blocks which are explicitly marked as "unsafe".

[Gillipig]

Sorry if any of these are re posts.

[Haggis_McMutton]

Well, obviously you can't do it in higher-level interpreted languages. Java, Python, Ruby and such are all languages which don't compile into machine code, they instead compile the source into a bytecode which runs in their own language-specific virtual machines. So of course you can't directly manipulate memory locations in those languages, since all data and code are virtualized and the languages don't allow direct access to the system.

This doesn't mean those languages are less useful though, it just means they are designed for a different purpose. Making the code run on a virtual machine makes it easier to code cross-platform implementations, since the programmer doesn't have to worry about the low-level hardware stuff. It also makes the languages more useful for scripting purposes.

However, interpreted languages aren't very suitable for uses that require very efficient usage of system resources, such as graphics engines for games or such.

C# is an "interesting" exception - it's a bit of both, and depending on your point of view, it either has the advantages or the disadvantages of both types... basically, it's an interpreted language, but it doesn't run on a virtual machine, instead the code is compiled at run-time to machine code. It's called "just-in-time compiling". C# allows the use of pointers, but only in code blocks which are explicitly marked as "unsafe".

Turns out you can actually do it in Java, huh: http://stackoverflow.com/questions/11513344/how-to-implement-the-fast-inverse-square-root-in-java

Yeah, I know about the JVM, I wasn't implying C is better because it lets you do that stuff, rather I think it's worse for most applications. Yeah, there are a handfull of applications where you really have to get down to the metal and squeeze every last bit of performance, but it seems to me that the vast majority of stuff written in C/C++ would work just as well in python and would be more readable and more easily maintainable.

Interesting about C#, I didn't know that.

Also:

[natty dread]

Turns out you can actually do it in Java, huh:

Yes, but not by the same method - instead there are built-in methods in the Java primitives which allow this kind of conversion.

I'm sure you can do it in Python too (it's pretty damn versatile for an interpreted language), but not by directly manipulating memory locations with pointers.

Yeah, I know about the JVM, I wasn't implying C is better because it lets you do that stuff, rather I think it's worse for most applications. Yeah, there are a handfull of applications where you really have to get down to the metal and squeeze every last bit of performance, but it seems to me that the vast majority of stuff written in C/C++ would work just as well in python and would be more readable and more easily maintainable.

Well, I think the trend these days is to use some combination of a low-level language + high-level language. Often, back-ends are written with a low-level language, whereas high-level languages are used for interfaces and front-ends, also scripting.

However there are plenty of applications where low-level languages are still necessary, and I don't think they're going to go anywhere for a while. Operating systems, compilers, hardware drivers, etc. all require lower-level languages for coding. Maybe in the future we'll have computers with such ridiculous performance that the distinction becomes moot, but so far this isn't the case.

[Army of GOD]

Click image to enlarge.

This comic, like many smbcs, has the same problem of adding extra frames. If they end it during the dog's "NOOOO!" I think it wouldbe a lot more funnier than the actual punchline.

[Haggis_McMutton]

I'm sure you can do it in Python too (it's pretty damn versatile for an interpreted language), but not by directly manipulating memory locations with pointers.

I guess you could just embed the C in Python anyway, should be possible, though I've never actually done it.

Well, I think the trend these days is to use some combination of a low-level language + high-level language. Often, back-ends are written with a low-level language, whereas high-level languages are used for interfaces and front-ends, also scripting.

However there are plenty of applications where low-level languages are still necessary, and I don't think they're going to go anywhere for a while. Operating systems, compilers, hardware drivers, etc. all require lower-level languages for coding. Maybe in the future we'll have computers with such ridiculous performance that the distinction becomes moot, but so far this isn't the case.

Sure yeah, but what percentage of programmers actually work on OS's and compilers? It just seems to me that C and even Java to a lesser extent are too low level nowadays for many of the stuff they're used in. I mean I learned to program first in C and then Java, but now that I've been using a lot of stuff like Python and Haskell it seems like a major pain when I have to work in one of those again.
I guess the standard is changing in the start-up scene now though. Most of the ones I've seen were using higher level stuff.

[Haggis_McMutton]

Also:

[natty dread]

I'm sure you can do it in Python too (it's pretty damn versatile for an interpreted language), but not by directly manipulating memory locations with pointers.

I guess you could just embed the C in Python anyway, should be possible, though I've never actually done it.

Indeed it's possible - if I recall, python has means for calling C libraries directly. Then there's Cython which compiles python code to C code. And Jython which compiles python to Java. And Vala which compiles C#-like code to C. etc...

Well, I think the trend these days is to use some combination of a low-level language + high-level language. Often, back-ends are written with a low-level language, whereas high-level languages are used for interfaces and front-ends, also scripting.

However there are plenty of applications where low-level languages are still necessary, and I don't think they're going to go anywhere for a while. Operating systems, compilers, hardware drivers, etc. all require lower-level languages for coding. Maybe in the future we'll have computers with such ridiculous performance that the distinction becomes moot, but so far this isn't the case.

Sure yeah, but what percentage of programmers actually work on OS's and compilers? It just seems to me that C and even Java to a lesser extent are too low level nowadays for many of the stuff they're used in. I mean I learned to program first in C and then Java, but now that I've been using a lot of stuff like Python and Haskell it seems like a major pain when I have to work in one of those again.
I guess the standard is changing in the start-up scene now though. Most of the ones I've seen were using higher level stuff.

There are still plenty of applications where lower-level languages are more suitable. Graphics applications, music/recording, games, emulators, virtual boxes, web server software, shared libraries, etc. Lots of things. Besides, a lot of the benefits of using an interpreted language are diminished on open-source software - for example, when the source is freely available, it becomes much easier to port the software to whatever platform you choose, so the cross-platform functionality of interpreted languages becomes less of an advantage.

Maybe someday we'll get to the point where low-level languages become redundant for everything except the system kernel. On the other hand, it could be that we'll just come up with more resource-hungry applications that still require coding with lower-level languages - the phenomenon is best seen in computer games: no matter how powerful a new gaming hardware is, someone is going to come up with ways to utilize all of its potential...