![]() ![]() We want to allow for potential negative exponents though, so this eight-bit number is shifted down by 127, thus the actual range of values is -127 to 128. With eight bits, numbers between zero and 255 can be created. E is an integer, and the eight bits craft a number using the same binary addition previously explained. The next eight bits represent an exponent, which we will call E.In the case of an inverse square root, the number has to be positive, so it’s always going to be zero. The first bit represents the sign of the number.Don’t stress if that went over your head it’ll come back up later in detail. To summarize without getting too technical, it involves taking an initial guess close to the expected answer (taken from a look-up table) and using a lot of iterative calculus to converge quadratically closer to the positive root of an x² = r function. Square roots are even worse, as they use Newton’s method of calculating. The computer needs to check after every iteration to see if it has passed zero, whereas with something like multiplication, say n*m, it can just add m to itself n times without needing to make additional checks in between. A simple division question, say n/m, is really saying “how many times do I need to remove m from n until I get zero?”. Division and square roots are both very computationally heavy, due to the nature of how they are performed. Truth be told, it’s not hard to compute the inverse square root of a number at all, but it’s very slow. By letting d² = x, we are thus looking to find 1/√x, which we will multiply our vectors by to normalize. d is the length of the vector, thus when it is normalized, it is dividing the length by √(d²). This calculation is done first to find d². This is used to calculate the length, c, of the hypotenuse of a right-angle triangle, but it can also be used to calculate the length of a vector in three dimensions: a² + b² + c² = d². In order to normalize a vector to a length of one, you just need to divide its length by its length, but what is its length? Well, if you think back to your high school algebra class, you may remember the Pythagorean theorem, a² + b² = c². Why this is important will be explained shortly, but for those who do understand C, try your best to follow along with the code and make sense of it yourself. The ultimate goal of this algorithm is to solve for the inverse square root of a number, i.e. Don’t worry if you don’t understand C coding, as each step will be explained later in further detail. But what exactly was the purpose of this algorithm, and how did it work? The Quake III Algorithm Itselfīelow is an image of the Quake III algorithm exactly as appears in its source code, complete with some pretty funny comments added by another developer. This code accomplished something that was seemingly mathematically impossible and allowed the game to function faster and more smoothly, and has been a subject of investigation for more than 15 years. Quake III Arena is one of the most influential games in FPS history, not just for being one of the greatest early multiplayer-focused shooters, but also due to the absolutely ingenious Quake III algorithm in the source code. ![]()
0 Comments
Leave a Reply. |