Portada
mis comunidades
otras secciones
#11:
Hay muchas cosas por ahí que alucinas. Yo saque una matricula de honor dibujando círculos en un XML sin usar librerías trigonométricas con una aproximación al seno mediante polinomios de un matemático hindú del siglo 7. Joder que recuerdos.
https://en.wikipedia.org/wiki/Bhaskara_I%27s_sine_approximation_formula
https://en.wikipedia.org/wiki/Bhaskara_I%27s_sine_approximation_formula
#12:
En este video lo explican mejor y esta mucho mas currado: https://youtu.be/p8u_k2LIZyo
Comentarios
En este video lo explican mejor y esta mucho mas currado:
#12 Pero va rápido de pelotas si no tienes los fundamentos frescos. Ahora veo el del envío. Gracias.
#12 Buen vídeo.
Cuenta más o menos lo que escribí en #46 aunque con algún detalle sobre programación como los punteros y conversión de tipos en C ... y más detalle sobre lo que representa la constante mágica, así como detalles del método de Newton para este caso particular (no en general como el vídeo del meneo).
cc #42
Hay muchas cosas por ahí que alucinas. Yo saque una matricula de honor dibujando círculos en un XML sin usar librerías trigonométricas con una aproximación al seno mediante polinomios de un matemático hindú del siglo 7. Joder que recuerdos.
https://en.wikipedia.org/wiki/Bhaskara_I%27s_sine_approximation_formula
#11 Que ha dicho usted??
#11 alguna razón en particular para usar la aproximación polinómica del hindú y no un desarrolló en serie de Taylor
#19 Sirve para operar con ábaco.
#19 Quería ser original, esas cosas las suelen premiar como me pasó a mi.
#19 Si te fijas en el enlace de Wikipedia que puso #11 verás que no es un polinomio sino una división de polinomios, lo que suele llamar una "fracción algebraica". Y eso lo cambia todo.
Aunque es cierto que meter una operación de división puede complicar las cosas, especialmente tiempo atrás cuando los ordenadores (microprocesadores / coprocesadores) no "sabían" dividir... sin embargo, si la máquina tiene operación de división lo que consigues con la fórmula del hindú es más precisión con un mismo número de operaciones o menos.
Otro detalle es que la Serie de Taylor, aunque es exacta dentro del radio de convergencia, es infinita y como no puedes hacer infinitas operaciones lo que haces es truncar, es decir, limitar el grado el polinomio... perdiendo exactitud con un margen de error.
Y otro detalle más es que las series de Taylor suelen tener más error cuanto más te alejas del punto central "c". Recordemos que son potencias de (x - c) así que en el caso x=c tienes garantizado el valor exacto y para valores de x muy cercanos a c la diferencia (x-c) será casi 0 y tendrás valores cercanos a ese punto central pero cuando te alejas, cuanto mayor es la diferencia (x-c) el error suele crecer mucho.
En el caso concreto de la serie de Taylor del seno, las derivadas enésimas están acotadas (son cosenos y senos, que están entre -1 y 1, no pueden crecer mucho) mientras que se divide por un factorial, así que con polinomios de grado bajo (ej: 3 ó 5) te acercas bastante... Aún así, en puntos alejados tendrás más error. Si te fijas en la fórmula del hindú tiene raíces (ceros) donde se anula el seno (0 y PI si es en radianes ó 0 y 180 si es en grados), es decir, no tienes nada de error en los extremos a pesar de tener el mayor alejamiento. Vas a tener error en puntos intermedios, claro, porque no es exacta, pero podríamos decir que el error está equilibrado, hay varios puntos sin nada de error. Esto es diferente en la serie de Taylor porque si es exacta en un punto, en otro punto alejado (los extremos serían el máximo alejamiento) normalmente tienes un error grande.
#43 Peaso explicación, la verdad es que tengo muy olvidadas las mates y ese trabajo lo hice hace 15/20 años, lo que recuerdo es que se me metió en la cabeza no usar librerías trigonométricas (por entonces ya había aprendido el truco para sacar MH y con las 18 que conseguí me ahorré un pastón ) y me puse a buscar y probar diferentes opciones y con esta aproximación salían unos círculos perfectos, al menos a simple vista) y el cálculo era rapidísimo.
#11 Con un colega logramos hacer exponenciacion modular rapida en un microcontorlador de 8 bits a 20Mhz para calcular rsa de 1024 en menos de lo que los de Microchip decian que se podia hacer (subieron nuestra libreria a su web, lo he buscado y no encuentro donde coño esta, tardabamos unos 400ms en calcularlo).
La verdad es que si, hay cosas apasionantes por ahi fuera
El algoritmo... y su camiseta: https://www.redbubble.com/es/i/camiseta/El-truco-de-Quake-III-Ra%C3%ADz-cuadrada-inversa-r%C3%A1pida-0x5F3759DF-de-cybersec/36459737.FB110
#9 Falta la definición de threehalfs en la camiseta...
Logaritmo. En Menéame todo es logaritmo.
#1 algo, es algo
#1 #4 En este caso, sí... ¡¡es un logaritmo!! En base 2. (véase mi explicación en #46 )
#2 Casualmente en el código fuente publicado aparece el WTF en un comentario del código.
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
La implementación más WTF de la historia.
#21, soy matemático y nunca he usado el recíproco para hablar de la función inversa.
#30 Creo que #21 se refería a que el "número inverso" [multiplicativo] se le llama recíproco...
Y, de hecho, en el código de Quake la función se llama Q_rsqrt , que si no me equivoco se refiere a "Quick reciprocal of square root" ... (la Q también podría referirse al Quake).
Sin embargo, pese a que "reciprocal" es una palabra más clara, menos ambigua, el algoritmo se conoce como FISR (Fast Inverse Square Root), quizá porque la "i" es vocal haciendo que sea más pronunciable: un acrónimo, que son siglas que en lugar de leerse letra por letra se lee como una palabra (ejs: RADAR, ONU, LASER, etc). En este caso quizá se lea como "fiser" en lugar de decir "efe, i, ese, erre".
Mientras que el mundo de las matemáticas creo que se tiende a minimizar la ambigüedad, en el mundo coloquial de la vida diaria, o incluso ingenieril, se va a lo práctico... lo que se pronuncia rápido, en especial en lugares como Estados Unidos, que son más "cool", más "guays", menos "estirados" / pedantes que los británicos, y en el mundo de la tecnología punta donde usar algo nuevo, aunque sea una palabra nueva, puede dar sensación de estar más a la última y estar en la onda de los últimos avances / inventos / trucos.
Cuando los programadores eran serios y exprimían la máquina en vez de ser unos picacódigos que trabajan capa sobre capa para sacar una app mierdosa quenecesita 400gb de ram.
#15 Los procesadores en los tiempos del quake tenían todos operaciones de coma flotante integrada. Lo que no tenían, porque es bastante reciente como se puede ver en el vídeo, es una operación rápida de la inversa de la raiz cuadrada.
#17 y aunque la tuvieran su coste en ciclos de cpu nunca seria mejor que una operación con enteros
¿Raíz cuadrada inversa no es elevar al cuadrado?
Ahora miro de qué va
#5 1/√x. Es útil para normalizar un vector
#7, sí, ya lo he visto en el vídeo. Pero es que cuando dice inverso de la raíz cuadrada he pensado en la aplicación inversa, y no al número inverso, por eso me sonaba raro.
#10 eso sería el recíproco...
#3
Aunque es cierto que una operación en aritmética de coma flotante tarde más que una operación con enteros, me parece que la clave no es esa y que en el vídeo no se explica muy bien del todo.
El caso es que la operación a calcular es 1/√x , como dijo #7
Y esa operación se puede escribir como la potencia x^(-1/2)
Y resulta que los números en coma flotante tienen relación con las potencias... en este caso en base 2, aunque también hay variantes en base 10.
Los flotantes son de esta forma: (-1)^s * c * b^q
donde s es el signo, c es el "coeficiente" o "significante" (o "mantisa"), b es la base y q el exponente.
Ejemplo en base 10: -2.5 * 10^14 sería signo = 1; c = 25; b=10 (base 10); q = 13
Ejemplo en base 2 (binario): +0.25 sería +(1/4) = +(2^-2) --> s=0; c = 1; b=2; q = -2
En la Wikipedia lo explica:
https://en.wikipedia.org/wiki/Fast_inverse_square_root#Algorithm
1. Alias the argument x to an integer as a way to compute an approximation of log2(x)
Si el número x es un float ... y especialmente si es positivo la representación binaria de ese
número codifica primero el exponente.
De esa forma, el "convertirlo" o "tomarlo" como un entero es una aproximación al logaritmo en base 2.
En el ejemplo : 0.25 = 2^(-2) y lo que codifica primero el formato de coma flotante es ese "-2", el exponente.
2. Use this approximation to compute an approximation of log2(1⁄√x)= −1/2 log2(x)
Lo que hacemos con ese exponente es dividirlo entre 2 y luego restarlo...
(por ejemplo, dividir entre 2 un entero es un desplazamiento de un bit a la derecha: >> 1)
Tanto esa "división" como la resta son operaciones con enteros, sí.
Pero la verdadera gracia es que eso es el logaritmo del recíproco de la raíz cuadrada.
¡¡¡Justo lo que buscamos calcular!!!
Ejemplo:
si teníamos x=0.25 y el exponente era -2 al dividir entre 2 queda -1 y al restar...
ej: 0-(-1) queda exponente +1
La raíz cuadrada de 0.25 es 0.5 y el recíproco de 0.5 es 2.
Efectivamente, el exponente es +1 porque 2^(+1) = 2
Otro ejemplo. Si fuese x=1024 = 2^10 el exponente es 10. Dividido entre 2 es 5. --> -5
La raíz cuadrada de 1024 es 32 y 1⁄√x = 1/32 = 2^(-5) así que el exponente calculado es correcto.
El significante (mantisa, coeficiente) no importa tanto, sobre todo cuando el formato en coma flotante
es formato normalizado... es decir, números que no son muy pequeños.
En el formato float normalizado solo se representan los dígitos binarios después del 1.
Si en binario es 1.1011 = 1+ 1*(1/2) + 0*0.25+1*0.125 + 1*0.0625 = 1.6875
solo se representa "101100000000000" (la parte fraccionaria después del 1)
Y al desplazarla queda dividida entre 2 (solo la parte fraccionaria). --> 1.34375
log2(x) = log2(c*2^q) = log2(c) + q
el logaritmo base 2 de un número c entre 1 y 2 estará entre 0 y 1.
log2(1⁄√x)= −1/2 log2(x) = -1/2 ( log2(c) + q)
el -1/2 * log2(c) estaría entre -1/2 y 0.
mientras que el nuevo significante esta entre 1 y 1.5 siendo el logaritmo entre 0 y log(1.5)/log(2) = 0.585
Lo que en media debería ser -0.25 realmente es en media +0.292
Aunque no lo se con seguridad, creo que el número mágico en parte intenta corregir este desajuste, especialmente en los casos en que el desajuste podría cometer un mayor error. Esto del número mágico no lo he analizado a fondo y ni siquiera la Wikipedia lo aclara... dice que no se conoce con precisión cómo fue determinado el valor exacto de ese número mágico, aunque añade que alguno intentó determinar el mejor número mágico simplemente probando varios números en un rango para determinar el mejor valor.
Como dijo #8 buscar un parámetro que minimice el error es lo que hace el aprendizaje en el Machine Learning, la principal área de la Inteligencia Artificial (sólo que en este caso es un único número a buscar y en la IA puede ser un "espacio" de miles de dimensiones / parámetros a modificar, los cuales no puedes buscar uno por uno de forma independiente ya que están interrelacionados)
3. Alias back to a float, as a way to compute an approximation of the base-2 exponential
Después de operar con enteros y tener el exponente (logaritmo base 2) que queremos,
deshacemos la conversión tomando ese entero como un número en coma flotante.
Y ese número en coma flotante será de forma aproximada lo que queríamos.
4. Refine the approximation using a single iteration of Newton's method.
Una iteración del método de Newton permite acercarse más al valor verdadero.
#46 Un algoritmo se aplica siempre si o bien es mas rapido o bien es mas preciso. Es mas rápido (check) pero no es mas preciso, pero si lo suficente preciso (check). La clave sigue siendo la velocidad.
#47 Depende de la aplicación, claro.
Por ejemplo, en una aplicación de contabilidad o de diseño / maniobra de un cohete prefieres precisión... En ambas está en juego una cantidad de dinero y puedes sacrificar minutos u horas para evitar perder ese dinero.
Obviamente, en el caso del que habla este meneo se trata de ocio, un videojuego... en el que tardar más tiempo en los cálculos arruina la experiencia de juego o al menos implica que el juego no funcionará bien en ciertos ordenadores, reduciendo el mercado potencial de ese juego. En este caso, que haya pequeños fallos de precisión es algo mucho más asumible que dividir la velocidad del juego por 4 o por 10.
Además, en un contexto de diversión / ocio / arte los errores inesperados dan un factor sorpresa o de ser diferente / especial / único que muchas veces lejos de considerarse un defecto puede llegar a ser un aspecto positivo.
Como el chiste:
- ¡Jaimito! Responda rápido… ¿cuánto es 2 multiplicado por 2?
- ¡CINCO!
- ¿¡Cómo que cinco Jaimito!? ¡SON CUATRO!
- Señorita, usted pidió velocidad, no precisión.
#48 como he dicho la precision era suficiente por lo que se dio por bueno obviametne nadie usaria una funcion imprecisa bajo ningun criterio...
#5 No hablan de una aplicación inversa de la raíz cuadrada. Hablan del inverso multiplicavo.
#15 Si, a partir del 486 por lo menos y bastante anteriores al quake
Sin verlo en la epoca q no habia graficas el coste por pixel de los calculos matemáticos limitaba los juegos (con graficas tb ) por lo que cualquier reducción de ese peso significaba mejores gráficos. Un calculo en flotante es mucho mas pesado qie una operación entre enteros
#3 Solo puntualizar que en la época del Quake 3 arena el menda tenía una Voodoo 3 y ya estaba desfasada, vamos que era raro que alguien no tuviese gráfica.
#13 #6 bueno en ese caso si ya era asi de aquella, sigue siendo valido lo que digo usaban el algoritmo para hacer raices cuadradas para normalizar vectores y de esa forma calcular que poligonos enseñar cuales no enseñar. Sigue siendo un tema de velocidad de calculo y por lo que se ve de aquella aun se hacia en el procesador, si mi memoria no falla de nuevo al principo las graficas renderizaban poligonos y texturas pero el motor 3d, es decir las coordenadas de los poligonos y cuales eran visibles y la luz , aun era parte de los procesadores. Fue la geforce 256 la primera en tener hardware para ello https://es.m.wikipedia.org/wiki/Transform_and_Lighting y salio dos meses antes que el juego demasiado tarde para el juego. Asi que si bien no era un calculo directo sobre el pixel al final influye sobre el pixel
#22 Creo que la Voodoo rampage ya tenía un chip T&L aunque solo salieron a la venta 20 unidades (NVIDIA compró Voodoo)
#24 por lo que veo nunca paso de prototipo.
#26 Hay unidades funcionales que se venden por un pastizal, creo que ya estaba lista para producción pero 3DFX se fue a la mierda y NVIDIA la compró. Creo recordar (igual me equivoco) que el tuber viejuner la enseña en uno de sus vídeos.
#28 lo quet te digo nunca paso de prototipo no hubo preduccion lo que hay es prototipos por ahi rulando
#6 una geforce 2 mx por aquí
#3 Casi... Quake 3 Arena fue el primer juego (al menos que yo sepa) que exigía una aceleradora grafica, no lo podías poner en modo "solo software" como los anteriores. Aunque también es cierto que las aceleradoras de aquella época no podían hacer muchas cosas que hacen las GPU actuales y lo tenia que hacer el procesador de todos modos...
#3 Por eso Dios nuestro señor creó los coprocesadores matemáticos.
#15 y gracias a los coprocesadores nunca hizo falta tarjetas graficas! Y hoy en dia se minan bitcoin con coprocesadores... Oh wait! Aun teniendo coprocesadores esa optimizacion era la leche
#3 gráficas había, lo que no había (en la época del Quake I) eran aceleradoras 3D. En la época del Quake 3 servidor gastaba una Voodoo Banshee, de las primeras en combinar gráfica y aceleración en la misma placa.
Es rápido pero no es exacto. De hecho, se realizan dos aproximaciones. Pero para juego vale.
#14, si lo quieres más exacto basta con repetir el final, que aplicar más iteradas del método de Newton (solo hace una iterada). Pero claro, ganas precisión, pero pierdes velocidad.
gracias por el Canal de youtube , es muy bueno este tio
pero ese algoritmo lo ha creado carmak o lo ha copiado de algún sitio?
#23 (carmack )
Tendrás que ver el video para saber lo que se sabe
#25 #23 El vídeo empieza por meras suposiciones de quién pudo hacerlo: quizá Michael Abrash (que fue compañero de trabajo suyo, de Dave Plummer, en Microsoft y luego se fue a trabajar haciendo el Quake) o quizá el propio John Carmack.
Aunque luego menciona que no es el primero que se pregunta por los orígenes y que más allá de Mike Abrash y Carmack se había usado antes en la estación de trabajo SGI Indigo (que apareció en 1991).
Si miras Wikipedia, dice que la implementación en SGI Indigo fue la primera implementación que se conoce y que fue realizada por Gary Tarolli.
https://en.wikipedia.org/wiki/Fast_inverse_square_root
Sin embargo, la "constante mágica" sería anterior y se encontró que surgió de una colaboración entre Cleve Moler y Gregory Walsh, cuando Gregory estaba trabajando para Ardent Computing a principios de los 80.
Por cierto, esa página de Wikipedia me pareció que explica de forma un poco más clara cómo funciona, hablando del logaritmo en base 2, y mostrando un ejemplo numérico,
aunque reconozco que el vídeo es más ameno porque lo noveliza como una historia con muchas anécdotas y, además, incluye imágenes tanto de los protagonistas como de los fundamentos matemáticos.
Ese número mágico es básicamente es exactamente lo que hacen la IA, sólo que una IA lo hace a una escala mucho mayor. Buscar números "mágicos" a base de iteraciones hasta encontrar uno lo suficientemente bueno