RAIZ CUADRADA INVERSA RÁPIDA: El algoritmo "mágico" del videojuego Quake III
Summary
TLDRThis 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
🎮 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.
👨💻 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.
🔢 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.
📚 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.
🔄 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.
Mindmap
Keywords
💡Quake
💡Game Engine
💡Inverse Square Root
💡Vector
💡Normalization
💡IEEE 754
💡Bit Level Hacking
💡Newton's Method
💡Mantissa
💡Exponent
💡Magic Number
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
5.0 / 5 (0 votes)