Cómo aumentar la velocidad de cálculo de la función trigonométrica en una computadora

Las personas que respondieron antes han respondido bastante bien.

Solo me gustaría agregar que su elección del lenguaje de implementación puede afectar drásticamente la velocidad computacional.

Para responder a su requisito de “10x”, diferentes idiomas generan diferentes niveles de código optimizado y eficiente y algunos son más consistentes y limpios que otros.

Los lenguajes funcionales y concurrentes como Golang, F # .NET, OCaml a menudo producen algunos de los mejores resultados, especialmente si hay que apretar el músculo GPU.

🙂

Mesa de consulta grande

Tabla de búsqueda con interpolación

Expansión taylor de orden inferior

Paralelamente si es posible con SSE o GPGPU (no cálculos más rápidos, pero haciendo más de ellos a la vez)

Fingiéndolo con curvas cuadráticas por partes

Si está calculando un par de ondas seno y coseno en un bucle (como al crear una tabla de búsqueda seno / cos), puede usar iterativamente los valores actuales de seno y coseno de un ángulo para obtener los valores de seno y coseno de un ángulo más un delta utilizando el método de iteración de la pendiente : Cuatro formas de calcular el seno sin disparo. ¡No puede ser mucho más rápido que eso!

Si tiene funciones paralelas (como en un sombreador) puede obtener seno y coseno al mismo tiempo:

En lugar de hacer esto:

flotador sa = sin (ángulo);
flotador ca = cos (ángulo);

Puedes hacerlo en una sola operación:

#define HALF_PI 1.5707963267948966
vec2 sca = sin (ángulo, HALF_PI-angle); // sca.x = sa, sca.y = ca

Dependiendo de sus necesidades de precisión, puede obtener el mejor rendimiento mediante el uso de valores calculados previamente almacenados en una tabla.

Digamos que 1 grado de precisión es lo suficientemente bueno.

Calcule y guarde 90 valores de la función SIN (o COS) en una tabla. Utilice la trigonometría simple para calcular el valor fuera del primer cuadrante y los valores de otras funciones, por ejemplo, si 90 <ángulo <180 entonces SIN (ángulo) = SIN (ángulo 180).

Si tiene más espacio de memoria disponible, puede calcular previamente todos los valores de 0 a 360 grados y guardar algunos cálculos como los anteriores.

Use la función de aproximación:

Para [matemáticas] 0 \ leq x \ leq \ dfrac {\ pi} {2} [/ matemáticas]

[matemáticas] \ dfrac {sin \, x} {x} = 1 + a_2 x ^ 2 + a_4 x ^ 4 + a_6 x ^ 6 + a_8 x ^ 8 + a_ {10} x ^ {10} + \ epsilon ( x) [/ matemáticas]

[matemáticas] | \ epsilon (x) | <2 \ cdot {10} ^ {- 9} [/ matemáticas]

[matemáticas] a_2 = -.16666 \, 66664 [/ matemáticas]

[matemáticas] a_4 = .00833 \, 33315 [/ matemáticas]

[matemáticas] a_6 = – .00019 \, 84090 [/ matemáticas]

[matemáticas] a_8 = .00000 \, 27526 [/ matemáticas]

[matemáticas] a_ {10} = -.00000 \, 00239 [/ matemáticas]

Puede usar las identidades trigonométricas para reducir los argumentos al rango adecuado y calcular las otras funciones trigonométricas. Hay buenas aproximaciones para todas las otras funciones trigonométricas y la mayoría de las funciones especiales más comunes. Una buena referencia es Abramowitz y Stegun, Handbook of Mathematical Functions .

Las funciones aproximadas son las que la gente usaba en los días en que la memoria de la computadora era costosa, y las tablas de consulta eran costosas. Hoy están casi olvidados. Las funciones aproximadas se generan minimizando el valor absoluto máximo del error. Desafortunadamente, esto es difícil de hacer, porque la derivada es discontinua, lo que hace que muchos métodos de optimización se comporten mal. El texto clásico sobre funciones de aproximación es de Hastings, aproximaciones para computadoras digitales .

Tenga en cuenta que la serie truncada de Taylor-Maclaurin suele ser la peor función de aproximación. Esto se debe a que es exacto en un punto, pero el error generalmente crece como [matemática] x ^ n [/ matemática] a medida que se aleja de ese punto.

Tenga en cuenta también que las personas a veces piensan que la forma de obtener una buena función aproximada es minimizar el error RMS. Esto también es menos que óptimo, ya que el error RMS está ponderado para minimizar el error promedio, y lo que más importa es el error máximo.

Podrías buscar tablas de búsqueda, pero ¿cuál es el contexto más amplio? Tal vez estás demasiado concentrado en esta línea cuando la optimización del algoritmo más amplio podría acelerar mil veces. ¿Podría descargar todo en la GPU, por ejemplo? ¿Realmente tiene que repetir eso a menudo, o podría la partición espacial o similar cortar su conjunto de datos en una fracción del tamaño?

Lo intentaría:

• Usa una tabla de búsqueda. (Dependiendo de la precisión requerida, puede intentar usar interpolación lineal o no hacer nada).
• Vea si puede usar aritmética de enteros en lugar de aritmética de coma flotante.
• Explora múltiples subprocesos.

Depende de sus requisitos, pero algunas ideas:

• Precargue una tabla, según sus requisitos de memoria, si necesita una precisión de [matemática] 1 ^ \ circ [/ matemática], entonces solo necesita 90 elementos, ya que todas las funciones trigonométricas son cíclicas. También puede usar el conocimiento de que [matemáticas] cos ^ 2 + sen ^ 2 = 1 [/ matemáticas] para reducir aún más los datos que necesita
• Preload +: si no puede precargar con la precisión que necesita, puede precargarlo para decir sin desde [math] 0 [/ math] a [math] 90 ^ \ circ [/ math] en [math] 1 ^ \ circ [ / math] pasos, y el pecado de [math] 0.1 ^ \ circ [/ math] a [math] 0.9 ^ \ circ [/ math] en [math] 0.1 ^ \ circ [/ math] pasos – y luego use: [matemática] sin (A + B) = sin (A) * cos (B) + cos (A) * sin (B) [/ matemática] para obtener valores de [matemática] 0 ^ \ circ [/ matemática] a [ matemáticas] 90 ^ \ circ [/ matemáticas] en pasos de [matemáticas] 0.1 ^ \ circ [/ matemáticas]
• Almacenamiento en caché: para que este lote sea aún más rápido, y para eliminar la necesidad de la fórmula complicada anterior, puede almacenar en caché los resultados a medida que los resuelve.

LUT: a la resolución requerida (precisión).

Sin embargo, creo que aún tendrás problemas. Sin saber lo que está haciendo, me arriesgaría a adivinar que trabajará con vectores en algún momento, en cuyo caso, sin duda, necesitará usar productos de punto de raíz cuadrada, por ejemplo. Una vez más, un LUT también puede acelerar las cosas aquí, pero necesitará saber el tamaño de vector más grande con el que probablemente esté tratando: espere grandes artefactos sin embargo con esta aproximación.

Use una tabla de búsqueda, posiblemente con interpolación. Por supuesto, debe observar la coherencia de la memoria caché y demás, por lo que debe mantener la tabla tan pequeña como lo permitan sus requisitos de precisión, pero este es el enfoque estándar.

Pero si es posible, intente sacar los cálculos trigonométricos del bucle principal: busque alternativas matemáticas … las soluciones algorítmicas siempre son mejores que las soluciones de optimización.

Escriba sus propias aproximaciones de Taylor para las funciones trigonométricas (en papel).

No calcule todos estos coeficientes con los factoriales en su programa principal, más bien calcule los coeficientes de antemano, cree una tabla de ellos y haga de esta tabla una entrada para su programa principal. Probablemente no necesite demasiados términos, por lo que la tabla no será grande. Detenga la serie cuando el término se vuelva más pequeño que cierta precisión. No establezca la precisión menos de lo que necesita.

Si la precisión no es muy importante, una forma muy rápida es codificar de forma rígida veinte o cien valores precisos y usar interpolación lineal.