RAIZ CUADRADA INVERSA RÁPIDA: El algoritmo "mágico" del videojuego Quake III

Summary

This video explores the revolutionary 1999 game 'Quake III' and its groundbreaking engine. It delves into the mysterious 'magic number' in the game's inverse square root algorithm, crucial for 3D graphics and physics simulations. The script discusses the use of bit-level hacking and the method of Newton to achieve high precision in calculations, showcasing the ingenuity of early 3D game development.

Takeaways

• 🎮 The 1999 game 'Quake 3' was revolutionary in the gaming industry, known for its pioneering work in 3D gaming and online multiplayer.
• 🛠️ 'Quake 3' utilized a powerful engine that was optimized to run on the widest range of computers at the time, influencing the development of many game sagas, including 'Half Life' and 'Call of Duty'.
• 🔢 The script focuses on a piece of C code from the 'Quake 3' engine, which calculates the inverse square root of a number—a critical operation for 3D vector normalization.
• 💡 The algorithm in question was much faster than the standard method, running up to four times quicker, which was essential given the computational constraints of 1999.
• 🕹️ In 'Quake 3', the inverse square root operation was used extensively for simulating physics like lighting and texture shading, requiring rapid and efficient computation.
• 📚 The script delves into the binary representation of numbers, explaining how floating-point numbers are stored in memory using the IEEE 754 standard.
• 🤔 A mysterious constant in the code, referred to as 'magical', has long puzzled programmers due to its unknown origin and calculation method.
• 📉 The script explains the process of logarithmic approximation to simplify the inverse square root calculation, avoiding the need for slow division operations.
• 👻 The 'evil floating-point bit-level hacking' mentioned in the script refers to the technique of manipulating the bits of a floating-point number to extract its memory representation without altering the number itself.
• 🔄 The method of Newton is introduced as a way to refine the approximation further, using the principles of calculus to iteratively approach the precise inverse square root.
• 📝 The script concludes by highlighting the combination of clever programming tricks, deep understanding of computer memory, and mathematical ingenuity that made the 'Quake 3' algorithm both fast and accurate.

Q & A

What is the significance of Quake III in the gaming industry?

Quake III, released in 1999, was a revolutionary game that significantly impacted the gaming industry. It was known for its pioneering implementation of online multiplayer and its powerful engine, which was optimized to run on a wide range of computers of that era. The engine played a crucial role in the development of many video game franchises that are still active today, such as Half-Life and Call of Duty.

What was the main purpose of the inverse square root algorithm in Quake III's engine?

The inverse square root algorithm in Quake III's engine was used to calculate the inverse square root of a number, which is essential for various mathematical operations in 3D games, such as normalizing vectors. This operation is crucial for simulating physics like lighting, shading, and reflection of light in 3D environments.

Why was the inverse square root algorithm considered 'magic' in the context of Quake III?

The inverse square root algorithm was considered 'magic' due to a mysterious number that appeared in its code. This number was difficult to decipher, and its origin or calculation method was not initially understood, adding an air of mystery to the algorithm.

How did the Quake III developers optimize the inverse square root calculation for performance?

The developers of Quake III found an algorithm that could achieve the same result as the standard inverse square root calculation but was up to four times faster. This was crucial for the performance of the game on the computers of that time, which were not as powerful as today's gaming PCs.

What is vector normalization and why is it important in 3D graphics?

Vector normalization is the process of scaling a vector to have a magnitude of one. This is important in 3D graphics because it ensures that vectors representing surfaces or objects in a 3D space have consistent behavior and appearance, regardless of their original magnitude. Consistent vector magnitudes are crucial for accurate lighting and shading effects.

How do computers typically represent numbers in memory?

Computers typically represent numbers in memory using binary format. For integers, a common approach is to use 32 bits, with the first bit representing the sign (positive or negative) and the remaining 31 bits representing the magnitude in binary form. For floating-point numbers, a more complex method involving scientific notation and binary exponents is used, as defined by the IEEE 754 standard.

What is the IEEE 754 standard and how does it relate to floating-point numbers?

The IEEE 754 standard is a widely used format for representing floating-point numbers in computer systems. It uses a combination of sign bits, exponent bits, and mantissa bits to efficiently store decimal numbers in binary form. This standard allows for a balance between precision and the range of numbers that can be represented.

What is bit shifting and how is it used in the context of the inverse square root algorithm?

Bit shifting is a technique used in binary operations where bits of a number are moved to the left or right, effectively multiplying or dividing the number by powers of two. In the context of the inverse square root algorithm, bit shifting is used to avoid actual division operations, which can be computationally expensive.

What is the role of the 'magic number' in the inverse square root algorithm?

The 'magic number' in the inverse square root algorithm is a constant that is used to approximate the inverse square root calculation. Its exact value was not initially understood and was derived through clever programming tricks and mathematical approximations. It plays a crucial role in the algorithm's efficiency and accuracy.

How does the Newton-Raphson method fit into the inverse square root algorithm in Quake III?

The Newton-Raphson method is used in the final stages of the inverse square root algorithm to refine the approximation. It iteratively improves the estimate of the inverse square root by using tangent lines and the derivative of the function being approximated. This method helps achieve a high level of precision in the final result.

Outlines

00:00

🎮 The Legacy of Quake 3D and Its Innovative Engine

This paragraph delves into the history and impact of 'Quake 3D', a revolutionary game released in 1999 that introduced a powerful engine optimized for a wide range of computers of its time. It played a significant role in the development of many subsequent gaming sagas, including 'Half Life' and 'Call of Duty'. The script focuses on a piece of C language code from the Quake engine, which was shrouded in mystery due to an enigmatic number. The algorithm in question calculates the positive inverse square root of a number, a task simple in theory but complex in its optimized implementation for the era's hardware limitations.

05:00

👨‍💻 Behind the Scenes: Quake's Algorithm and Binary Representation

The script explains the technical aspects of the Quake game engine's algorithm for calculating inverse square roots, which was faster than the standard method by up to four times. It discusses the challenges of performing mathematical operations like division and square roots on the computers of 1999. The explanation includes the binary representation of numbers, the use of 32-bit 'Long' integers, and the complexities of storing decimal numbers in memory, introducing the concept of scientific notation and its application in binary form, known as the IEEE 754 standard.

10:00

🔢 Unraveling the Mystery: The Magic Number and Bit-Level Manipulation

This paragraph explores the intricacies of the 'magic' number used in Quake's algorithm, which was derived from an approximation equation. It explains how the number was used in conjunction with bit-level manipulation techniques, such as casting a float to an integer to access the memory representation of a floating-point number. The script also covers the process of using logarithms and bit shifting to avoid divisions, which were computationally expensive at the time, and how these techniques contributed to the algorithm's efficiency.

15:02

📚 Deep Dive into Newton's Method and Its Application in Quake's Algorithm

The script introduces Newton's method, a technique for finding successively better approximations to the roots of a real-valued function. It applies this method to the problem of calculating the inverse square root, transforming the problem into an iterative process that refines the approximation. The explanation includes the use of a 'magic' constant in the algorithm, the origins of which remain a mystery, and how this constant, along with bit-level hacking and clever programming tricks, contributes to the algorithm's remarkable efficiency and precision.

20:03

🔄 Newton's Method in Practice: Refining the Inverse Square Root Algorithm

The final paragraph details the practical implementation of Newton's method in the context of the Quake engine's inverse square root algorithm. It describes the iterative process of refining the initial approximation, the significance of the chosen constants, and the ultimate achievement of a highly efficient and accurate algorithm. The script concludes by highlighting the combination of mathematical insight, deep understanding of computer memory, and programming ingenuity that made the algorithm possible, leaving the audience with a sense of awe at the blend of magic and science in computing.

Keywords

💡Quake

Quake is a revolutionary series of first-person shooter video games that were highly influential in the gaming industry. The script discusses the third installment of the series, 'Quake 3,' which was released in 1999 and was known for its pioneering online multiplayer mode and its powerful game engine. The game's significance is tied to the video's theme as it exemplifies the technological advancements in gaming and the importance of efficient algorithms for performance optimization.

💡Game Engine

A game engine is the core software framework upon which a video game is built. In the context of the video, the Quake game engine is highlighted for its optimization to run on a wide range of computers of that era, which was crucial for the game's success and its influence on subsequent game development. The engine's efficiency is a central theme in the video as it relates to the innovative algorithms discussed.

💡Inverse Square Root

The inverse square root is a mathematical operation that calculates the reciprocal of a square root. In the script, this operation is central to the video's narrative as it is used to normalize vectors in 3D space for games like Quake. The video delves into an ingenious algorithm implemented in the Quake engine to compute this operation more efficiently, which is vital for the game's physics simulations.

💡Vector

In the script, a vector is described as a mathematical and physical quantity that has both magnitude and direction. In the context of 3D graphics, vectors are used to represent directions and magnitudes, such as the path and intensity of light rays in a 3D game environment. The normalization of vectors, which involves adjusting their magnitude to one, is a key process in the video's explanation of the Quake engine's functionality.

💡Normalization

Normalization in the video refers to the process of adjusting a vector's magnitude to one, which simplifies calculations in 3D graphics. This process is essential for ensuring consistent behavior in the game's physics, such as light reflection and texture shading. The video explains how the inverse square root operation is used in vector normalization, which is a fundamental concept in the game's rendering process.

💡IEEE 754

IEEE 754 is a standard for floating-point arithmetic that defines how floating-point numbers are represented in computer memory. The script discusses this standard in the context of how decimal numbers are stored and manipulated in a computer system. Understanding IEEE 754 is crucial for the video's theme as it underpins the discussion on how the Quake engine's algorithm works with floating-point numbers for efficient computation.

💡Bit Level Hacking

Bit level hacking, as mentioned in the script, refers to the manipulation of individual bits in a computer's memory to achieve a desired outcome, such as optimizing an algorithm. In the video, this concept is used to describe the technique employed in the Quake engine to extract and manipulate the bits of a floating-point number without altering its value, which is a key part of the inverse square root algorithm.

💡Newton's Method

Newton's Method, also known as the Newton-Raphson method, is an iterative technique for finding successively better approximations to the roots, or solutions, of a real-valued function. In the script, Newton's Method is used to refine the approximation of the inverse square root operation. The video explains how this method is applied in the context of the Quake engine's algorithm to achieve high precision in calculations.

💡Mantissa

In the context of the IEEE 754 standard discussed in the script, the mantissa is the significant digits part of a floating-point number. The video explains how the mantissa, along with the exponent, is used to represent a decimal number in binary form. Understanding the role of the mantissa is important for grasping how floating-point numbers are handled in the Quake engine's algorithm.

💡Exponent

The exponent in the IEEE 754 standard is used to scale the mantissa to represent the full range of a floating-point number. In the script, the video explains how the exponent is adjusted and stored in memory to reflect the magnitude of the number. The manipulation of the exponent is a key aspect of the inverse square root algorithm discussed in the video.

💡Magic Number

The 'magic number' in the script refers to a specific constant used in the Quake engine's inverse square root algorithm. It is called 'magic' because its origin and derivation were not initially understood. The video explores the mystery surrounding this number and how it plays a crucial role in the algorithm's efficiency and effectiveness.

Highlights

The year 1999 saw the release of Quake III, a revolutionary game in the industry.

Quake III was a pioneer in implementing online multiplayer.

Quake's engine was highly optimized to run on a wide range of computers of the time.

The Quake engine influenced the development of many game sagas, including Half Life and Call of Duty.

The focus of the video is on a piece of C code from Quake III's engine.

The algorithm in question calculates the positive inverse square root of a number.

The straightforward implementation of the inverse square root is slow on older computers.

The Quake developers found an algorithm that is up to four times faster than the normal method.

The inverse square root operation is crucial in 3D games for physics simulations like lighting and texture shading.

Vectors in 3D graphics are used to determine behaviors like light reflection, requiring normalization.

Normalization of vectors involves reducing their magnitude to one, simplifying calculations.

Computers handle numbers in binary, but operations are typically in base 10.

32-bit integers are represented with one bit for the sign and 31 bits for the number.

Floating-point numbers are stored using scientific notation in binary, known as IEEE 754.

The algorithm uses bit-level hacking to extract and manipulate the bits of a floating-point number without changing its value.

The 'magic number' in the code is used to approximate the inverse square root, though its origin remains a mystery.

The method of Newton is used to refine the approximation further, providing a highly effective algorithm.

The algorithm's effectiveness is due to a combination of clever programming tricks, deep knowledge of computer memory units, and mathematical refinement.

Transcripts

el año 1999 de la mano de los creadores

de T y wst 3D uno de los juegos más

revolucionarios que ha dado la industria

vería la luz la tercera entrega de la

saga quake una saga que quizá a día de

hoy no evoque mucha atención del público

pero que en su tiempo fue de los más

famosos shooters 3D pionero en la

implementación del multijugador online y

muy conocido en el mundo de los

desarrolladores debido a su poderoso

motor llamado engine motor

explícitamente optimizado para correr en

la mayor cantidad de computadoras de la

época y que fue elemento clave directa o

indirectamente en el desarrollo de

muchas sagas de videojuegos algunos que

siguen vigentes Incluso el día de hoy

como Half Life o Call of

Duty hay mucho que podríamos decir sobre

quake pero en este video nos enfocaremos

en este trozo de código en lenguaje c

que forma parte de lo que fue el motor

de quake 3 y es que este algoritmo tiene

tantas capas de genialidad que no solo

es ingeniosa la forma en como fue

implementado Sino que también estuvo

envuelta en un Halo de misterio debido a

cierto número extraño que aparece en su

código que por mucho tiempo nadie llegó

a descifrar de dónde fue que salió o

cómo es que fue calculado por lo que se

ganó el rótulo de

mágico Antes que nada es importante

definir Qué hace el algoritmo Y es que s

entemente hace algo bien sencillo el

algoritmo simplemente haa la raíz

cuadrada inversa positiva de un número

es decir si la entrada de la función

fuera 4 el resultado será 1/2 o 0.5 en

decimales Y es que es tan sencillo que

tampoco es difícil de implementar si

sabes programación básica en C esto se

haría de la siguiente forma sin embargo

el algoritmo que se implementó en el

motor es bastante más complejo Por qué

Recuerden que era el año 1000 1999 las

computadoras no eran precisamente del

tipo Gamer y la forma simple era lenta

para los procesos que se requerían en el

juego en Aquellos tiempos los

procesadores manejaban bien operaciones

como la multiplicación y la suma pero la

división y la raíz cuadrada no eran

precisamente su punto fuerte para este

fin es que los programadores de quake

encontraron un algoritmo que haya el

mismo resultado pero hasta cuatro veces

más rápido que la forma normal y

hablando del juego

exactamente En qué parte del juego se

utiliza esta

operación quake como muchos otros juegos

3D tiene físicas simuladas como puede

ser iluminación sombreo de texturas

reflexión de luz entre otras cosas y

para que esto funcione en un computador

el juego se apoya de un concepto

matemático llamado vector de forma

simple un vector es un segmento que

tiene magnitud y

dirección y la podemos Representar en un

campo 3D con sus coordenadas en los ejes

x y z las superficies de los gráficos en

3D suelen utilizar vectores que nos

ayudan a determinar por ejemplo cómo le

rebotara un rayo de luz normalmente

todos los vectores deben tener una misma

magnitud Y esto es debido a que si dos

superficies iguales tienen vectores de

distinto tamaño pueden tener

comportamientos raros si las magnitudes

no son iguales podemos transformarlas

matemáticamente al valor con el que es

más fácil trabajar la unidad a este

proceso se le llama normalización cuando

normalizamos un vector reducimos su

magnitud original a uno y como es obvio

sus componentes en x y z también se

achican Cómo saber qué valor ahora

tienen estos nuevos

componentes Ah Pues para eso usamos la

fórmula de la magnitud de un vector la

cual es igual a la raíz del cuadrado de

cada una de las

coordenadas quizás esto le suene un poco

del colegio y es que se parece mucho al

teorema de Pitágoras verdad

pues de hecho usa la misma lógica con la

diferencia de que el teorema de

Pitágoras serviría para vectores en

2D pero volviendo al tema Si queremos

que la magnitud sea uno simplemente

dividimos cada componente del vector

entre su

magnitud porque de esta forma al

resolver la fórmula podemos observar que

ahora Siempre será

uno así fue que hemos logrado el

procedimiento de normalización

claramente Se observa en el proceso de

normalización El Por qué la inversa de

la raíz es tan importante y eso no es lo

único sino que al ser un juego 3D tan

detallado debía correr este proceso

miles de miles de veces en cada

renderizado he ahí su

importancia debido a que el algoritmo

utiliza bastantes trucos relacionados a

la forma en Cómo se guardan los números

en la memoria del computador lo mejor es

explicar algunos conceptos previos como

es de conocimiento general las

computadoras se manejan en el mundo de

los binarios Pero no es así para las

operaciones del día a día donde

usualmente la base es 10 Si quisiéramos

guardar un número de esta base en la

memoria del computador Cuál es el

procedimiento el procesador usualmente

nos da 32 bits o espacios para alojar un

número en el caso de enteros Es simple

como pueden ser positivos o negativos el

primer bit se usa para representar el

signo en los 31 restantes simplemente

ponemos el número en su equivalente

binario en el contexto de programación a

este tipo de dato no se le llama entero

sino Long y por qu 32 bits Porque así es

como ha diseñado el procesador de hecho

esto de 32 bits y 64 bits les debe

recordar algo en la actualidad ya los

procesadores de 32 bits no son tan

comunes pero en el pasado Pues eran la

Norma este algoritmo se hizo para 32

bits justo por esta razón los números

decimales o floats como se le llama en

sistemas computacionales se guardan en

memoria de una forma más compleja

Recuerden que los decimales tienen una

parte entera y una parte decimal Así que

no es tan simple como guardar enteros

qué tal si queremos guardar este número

El

14.625 en los 32 bits que tenemos

disponibles bueno en primer lugar

podemos utilizar 16 bits para su parte

entera y 16 para la decimal pero si lo

haríamos así hemos reducido a la mitad

los números enteros que podemos

representar Y de paso hemos limitado

también el lado decimal por lo que

perderemos precisión Para aprovechar

mejor estos 32 espacios de los que

disponemos podemos usar la anotación

científica Esta anotación es un tipo de

representación que usualmente se usa en

física o en otras ciencias relacionadas

y es fácil de usar Por ejemplo si

tenemos el número 5 millones en lugar de

escribir tantos ceros podemos

representarlo como 5 * 10 a la 6 Esta es

su notación científica en esta notación

el cinco es conocido como mantisa y el

seis como exponente la mantia siempre es

un número mayor a uno y menor a 10 para

notación científica de binarios La idea

es la misma Solo que las potencias de 10

por las que se multiplican está en

binarios y puede pasarse a potencias de

dos para que coincida con la base es

importante observar que la mantia al ser

binaria siempre es mayor a uno y menor a

dos en esta base utilizando notación

científica Entonces utilizaremos los 32

espacios de forma más eficiente para

guardar los bits que representan nuestro

número decimal esto resultaría así un

bit para el signo c si es positivo y uno

si es negativo 8o bits para el exponente

lo que nos permitiría guardar en sí 256

valores desde el 0 al

255 Aunque es importante recordar aquí

que el exponente también puede ser

negativo por lo que de esta forma no

podríamos representarlo para solucionar

esto el valor que está en la memoria se

debe restar por 127 y este es el valor

que se representa en la realidad

en nuestro ejemplo el exponente es 3 Así

que en la memoria debe estar guardado

130 tal que 130 - 127 es 3 esto nos

permite representar exponentes negativos

tal como se ve en este otro

ejemplo pasando a los 23 bits restantes

de la mantia como ya se vio en los

ejemplos de la anotación de binarios

esta siempre es mayor a un y menor a do

O sea que siempre tendrá un uno en la

parte entera como como la parte entera

es un valor que no cambia nunca Entonces

no tiene sentido guardarlo por ello los

23 bits de la mantia se ocupan

exclusivamente para su parte decimal y

de esta forma es que se guardan números

decimales en memoria a través de los

bits que Los representan este método es

el conocido estándar iee754 que quizás

si están estudiando sistemas se lo topen

en algún momento ahora a partir de ese

estándar llegaremos a unas ecuaciones

interesantes empecemos intentando hacer

lo contrario a lo que hicimos antes o

sea a partir de los bits en memoria

recuperaremos el número

original para ello tenemos s e y m

variables que toman los valores de los

bits de signo exponente y mantia

respectivamente los bits de m se

encuentran como si fueran un número

entero pero recordar que representan

solo la parte decimal de la mantia por

lo que primero tomamos los 23 bits de m

y los dividimos entre 2 a la 23 para

regresarlo así a su forma decimal

luego recuperaremos el entero de la

mantia sumando uno ya que Recuerden que

siempre es uno en notación científica

resultando igual a 1 + m ent 2 a la 23 o

por 2 a la-23 que es lo mismo respecto a

s el signo del número como el algoritmo

solo deben ingresar números positivos

Entonces ese Siempre será cero y podemos

ignorarlo finalizando con la exponente

recordemos que este se guarda tal cual

el valor que representa pero con una

diferencia de 127

y Bueno listo hemos encontrado así la

ecuación para regresar de los bits con

estándar I 754 al número binario decimal

que representa esta será la ecuación

uno ahora veamos el número alojado de

memoria desde otro ángulo en lugar de

ver lo que representa qué tal si lo

vemos como un número entero qué tal si

queremos representar este número entero

en función de las variables s e y m para

esto pues podemos descomponer el entero

en tres sumandos de forma que logremos

sacar los bits de s e y m de alguna

forma Aunque un sumando correspondería A

S como ya sabemos que siempre es cer0 lo

podemos ignorar de esta forma el primer

sumando que queda corresponde a e tal

que este número son los 8 bits de e con

23 ceros extras debido a la separación

de los 23 bits de m y Bueno finalmente

el segundo sumando que es simplemente m

porque son los bits de la parte final la

suma de estos dos forman el número

entero por tanto la siguiente ecuación

que tenemos es

esta y esta será la ecuación

dos recapitulando tenemos estas dos

ecuaciones el primero encuentra el

número decimal guardado en memoria y el

segundo encuentra los bits en memoria

que representan este decimal entendiendo

esto apliquemos la operación de

logaritmo a la primera ecuación por qué

logaritmo HM No sabría decir la verdad

eh No encontré el Por qué solo que así

se hizo Pero en fin el logaritmo que le

aplicamos obviamente será de base dos

porque estamos trabajando con binarios

si operamos lo que corresponde al final

no podemos desaparecer este logaritmo

debido a la suma qué hacemos ahora bueno

existe de hecho una aproximación

logarítmica para simplificar operaciones

de este tipo donde logaritmo de 1 + x es

x siempre y cuando x tenga un valor

pequeño menor a uno si lo vemos

gráficamente De hecho sí se ve muy

aproximada y se puede aproximar aún más

si es que se le hacen algunos ajustes

representados en la variable

Sigma de esta forma usando la

aproximación desapareceremos la suma

luego movemos un poco los valores y le

damos otra forma y llegamos a esto

pueden notar

algo ha aparecido mágicamente el valor

de la ecuación dos la que haya los bits

en memoria de un decimal si reemplazamos

encontramos una relación directa entre

el logaritmo de un número decimal y los

bits en memoria que representan dicho

decimal llamaremos a esta la tercera

ecuación toda esta explicación ha sido

larguísima para llegar a una ecuación

Tan pequeña pero no la subestimen Porque

será importante para develar la magia

del algoritmo en cuestión ahora

explicaremos por qué recuerdan la

operación que queríamos encontrar eh Y

es la salida y x es la entrada si le

aplicamos logaritmo de base 2 a ambos

lados y tenemos en cuenta que la entrada

y salida son decimales Pues operando un

poco podemos ver que nos Será muy útil

la ecuación

3 reemplazamos utilizando dicha

ecuación y ordenamos y agrupamos las

constantes que son iguales llegando así

a esta otra igualdad que llamaremos

ecuación 4 est eación es el resultado

final al que queríamos llegar ya que nos

da una relación entre la entrada y la

salida Aunque en su formato de bits en

memoria con esto ya hemos conseguido una

aproximación a la raíz cuadrada inversa

Así que en teoría podríamos acabar el

algoritmo aquí solo quedaría ajustar el

valor de Sigma que si lo ponemos en cero

y graficamos observamos que el resultado

ya se acerca mucho a lo que se

quiere teniendo esto presente si

quisiéramos implementar esto en C

tocaría preguntarse es esta aproximación

más veloz que la raíz cuadrada inversa

común pues para empezar no hay raíces

por ese lado tenemos un punto a favor y

estas divisiones Bueno en realidad estas

no afectan porque fácilmente podríamos

cambiarlas a multiplicaciones

equivalentes Entonces sí es mucho más

veloz aún así Este no es el final del

algoritmo la gente detrás de su

implementación fue aún más lejos por lo

que aún queda magia por develar así que

adentremos en el

código lo primero que se observa en esta

sección es una simple declaración de

variables básicamente se le dice a c Qué

tipo de datos son las variables con las

que trabajaremos

primero tenemos number el cual es el

número de tipo float o decimal que entra

a la función y luego tenemos y

Igualmente decimal que si vos la parte

final es la salida de la

función para hacer un símil con las

ecuaciones que hallamos y que nos sea

todo más fácil de entender le cambiamos

el nombre de la entrada number por

x luego tenemos I x2 y 3 hales 3h es una

constante de valor decimal 1.5 mientras

que las otras dos son variables

auxiliares en la línea siguiente se le

asigna un valor a x2 el cual es la mitad

de X como ya sabemos la idea es no usar

divisiones por lo que en su lugar se

multiplicó por 0.5 luego y toma el valor

de la entrada x todo muy simple hasta

ahora pero lo que sigue Sí ya se ve algo

más extraño se le asigna un valor a i

pero no se ve tan legible y de hecho el

comentario ya indica un comportamiento

medio truculento Qué significa

veamos desglosamos esta línea de código

Empezando por el final lo primero que se

ve es y que en la línea anterior se le

dio el valor de la entrada x por lo que

para propósitos didácticos usaremos X en

su lugar el simbolito de su costado lo

único que hace es obtener la dirección

en memoria de esta variable es decir en

qué parte de la memoria Se ha guardado x

cada dato al ser guardado en la

computadora tiene una dirección a la

cual el procesador irá a buscar cuando

lo necesite algo así como las columnas y

filas del Excel esta dirección

usualmente suele tener esta forma lo que

sigue es esta parte si ignoramos el

asterisco esto básicamente es un cast

que es un método para convertir un tipo

de dato a otro tipo como por ejemplo

convertir un tipo entero a decimal el

cast normal se usa con datos pero

recordar que aquí se le aplica a una

dirección y es por eso que aparece este

asterisco que cambia el enfoque del cast

ahora es un método para cambiar el tipo

de la dirección del dato aunque las

direcciones no tienen un tipo en sí sí

sí an cierta información sobre el tipo

del dato al que apuntan este cast

convierte esa información de decimal a

entero finalmente todo termina con

asterisco que lo único que hace es

recuperar un dato según la dirección

dada como la dirección dice que el dato

es entero pues se lo entiende así

entonces el asterisco extrae los bits

sin tocarlos y se los asigna a la

variable de tipo entero I en resumen la

variable I serían los bits en memoria

del decimal x pero interpretados como si

fueran un número entero dónde será que

hemos visto esto antes pues claro y

tiene exactamente el mismo valor que x

bits que aparece en varias de las

ecuaciones halladas incluyendo la más

importante la ecuación 4 Ahora ven el

sentido de hacer este truco si

hubiéramos hecho un cast normal nos

hubiera resultado algo que en realidad

sí tiene sentido en programación normal

y coherente pero hubiera modificado el

valor de X por lo que sus bits se H

hubieran perdido básicamente esta línea

de código ha tenido el único objetivo de

engañar a C para que nos permita extraer

los bits de la entrada sin

modificarlos y de ahí es que sale la

frase del comentario Evil floating

points bit Level hacking un hacking

maligno de los bits de un número decimal

a continuación veremos la línea de

código que ha generado tanta admiración

y confusión a lo largo de los años y

pues no es de extrañar ya que con solo

mirar el comentario original ya genera

curiosidad podríamos empezar con el

número mágico pero dejémoslo para el

final primero veamos el valor que se le

resta si les resulta un poco raros esos

símbolos es porque en realidad Este es

otro truco llamado bit shifting para

entenderlo imaginemos primero un número

por decir

4270 si te pido que lo dividas entre 13

probablemente ocuparás de una

calculadora Pero si te digo que lo

dividas Entre 10 es muy fácil todo No

simplemente quitamos el último dígito

Eso es así porque estamos dividiendo un

número de base 10 entre un valor que es

la misma base y pues eso ese es el

simple concepto detrás del bit shifting

con la diferencia de que como las

computadoras manejan binarios esta

operación se realiza en base dos si en

base 10 es fácil dividir Entre 10 Pues

en base dos es fácil dividir entre dos

simplemente quitamos el último dígito

este truco funciona perfecto para

números binarios que terminan en cer0 ya

que quitarlo nos da la mitad exacta Pero

no es así cuando el número termina en

uno quitar el último dígito en este caso

resulta en la mitad truncada esta

pequeña imprecisión es aceptable en

tanto hemos logrado hacer una división

pero sin hacerla

realmente para implementarlo en código

Se le indica a los bits de I que se

mueva un bit hacia la derecha que es

básicamente lo mismo que quitar el

último dígito esto ahorra hacer

divisiones por lo que ahorra también

valioso tiempo de

procesamiento podríamos haber

multiplicado por 0.5 en lugar de hacer

todo esto no y es un entero si lo

multiplicamos por 0.5 lo volveríamos

decimal y no tendría sentido haber hecho

todo el paso anterior y bueno Al fin

llegamos al número mágico el cual está

en base hexadecimal para que se entienda

mejor lo convertimos a base 10 Y de paso

reemplazamos y * x bits recordando la

sección

anterior si Seguimos observando

detenidamente nos daremos cuenta que

esto se parece a la ecuación de

aproximación pueden notar las

similaridades Exacto Son la misma

ecuación todo el código que se ha visto

hasta ahora se ha hecho para este Exacto

momento para poder implementar esta

ecuación en forma de código en C si

observan las constantes en la ecuación

de aproximación vemos que su resultado

determina el número mágico como ya lo

conocemos del código podemos encontrar

el valor de sigma y así ver qué valor le

dieron los creadores del algoritmo

Entonces vene al caso preguntarse cómo

lo calcularon o de dónde lo sacaron la

respuesta es que no se sabe y como el

comentario en código solo genera aún más

confusión es así que se le ha etiquetado

como

mágico varios trabajos se han planteado

métodos matemáticos de cómo se pudo

haber llegado a este valor quizás

simplemente fue producto de prueba y

error incluso cuando le preguntaron a

Gary taroli de dónde salió el número

básicamente dijo que no recordaba los

detalles es que tal vez este número sí

tiene algo de mágico después de todo

quién sabe

realmente antes de seguir con Newton

simplemente toca aclarar que la

aproximación que hallamos en la sección

anterior en realidad representa un

decimal pero se lo sigue viendo como un

tipo entero debido al truco del cast por

lo que usamos el mismo truco para

regresarlo a su valor decimal lo

guardamos en y y ahora ya tenemos la

aproximación en su valor decimal real

con eso aclarado continuamos con el paso

final del algoritmo el método de

Newton este sirve para hallar una

aproximación a la solución O soluciones

de una ecuación veamos por ejemplo esta

ecuación bien simple tal que queremos

hallar la solución a esto sin utilizar

calculadora el primer paso es con

convertir la ecuación en una función de

X de la siguiente

manera esto se hace así ya que el método

de Newton utiliza una forma gráfica de

hallar soluciones a ecuaciones en la

Gráfica la solución se encuentra cuando

la función FX es igual a 0 o sea cuando

corta al eje X en el método de Newton se

le da una aproximación inicial Y a

partir de esta el método hallará

aproximaciones cada vez más y más

cercanas por medio de rectas tangentes

que sean rectas tangentes es importante

porque hay una forma fácil de Hallar las

pendientes de este tipo de rectas si se

conoce la función original y eso es con

la derivada de forma sencilla Esa es la

lógica detrás de esta fórmula la cual es

parte del método de Newton como se

observa ahí está la función original su

derivada y la aproximación

inicial aplicamos la fórmula en nuestro

ejemplo escogiendo una aproximación

inicial de

1.5 y vemos que solo nos ha tomado dos

iteraciones llegar a un valor cercano al

real Igualmente haremos el procedimiento

pero para la operación que realmente nos

importa que es la inversa de la raíz

cuadrada una vez que tenemos la función

y su derivada pues aplicamos la fórmula

operamos y ordenamos hasta que nos queda

esta

ecuación se parece a algo que ya hemos

visto antes pues claro esta ecuación es

la que aparece en el código para esto es

que se definió trhs y y x2 que bueno la

única función que tienen es evitar

realizar divisiones recordar también que

la primera aproximación ya la hemos

hallado y se encuentra en la variable y

con esto finalmente se puede implementar

el método de Newton en código como

pueden notar aquí se ha dejado comentado

la segunda iteración y es que si

comparamos la precisión del algoritmo

completo ya prácticamente es

perfecta el nivel tan alto de

efectividad de este algoritmo es Gracias

más que todo a la aproximación inicial

que se encontró con ingeniosos trucos de

programación en C un profundo

conocimiento de las unidades de memoria

de los computadores y un poco de magia

quizás todo para darle un toque final

matemático de la mano de Newton para

refinar aún más esta precisión con esto

finalmente podemos dar por terminada

esta explicación he intentado ser lo más

entendible posible pero pues si tienen

aún alguna pregunta por favor no duden

en dejar un comentario Gracias Eso es

todo than