c++ - trigonometria - razones trigonometricas facil

Implementación rápida de funciones trigonométricas para c++

Question

Versión corta: me gustaría saber si hay implementaciones de las funciones trigonométricas estándar que son más rápidas que las incluidas en math.h

Versión larga: obtuve un programa que es bastante pesado en numéricos (es una simulación de física) y que necesita llamar mucho a funciones trigonométricas, principalmente sin y cos . Actualmente solo estoy usando las implementaciones incluidas en math.h La creación de perfiles muestra que las llamadas a estas funciones cuestan más de lo que esperaba (con la esperanza).

Si bien es cierto que hay mucho espacio para la optimización en otras partes del código, tener un sin más rápido y cos podría darme un porcentaje adicional ... Entonces, ¿tienen alguna sugerencia?
En otra post se sugiere el uso de tablas de búsqueda creadas por ellos mismos. Pero tal vez hay alternativas? ¿O soluciones de búsqueda listas y bien probadas en algunas bibliotecas?

Answer 1

A) Tratar de ahorrar pequeños porcentajes no será muy satisfactorio. Terminar en 97 en lugar de 100 horas todavía es mucho tiempo.

B) Dice que tiene un perfil, y que las funciones trigonométricas toman más tiempo del que le gustaría. ¿Cuánto cuesta? y ¿qué hay del tiempo restante? Es muy posible que tengas peces más grandes para freír. La mayoría de los perfiladores basados ​​en los conceptos de gprof no le informan sobre las llamadas de la mitad de la pila en las que podría concentrarse para ahorrar grandes cantidades de tiempo. Aquí hay un ejemplo.

Answer 2

Aquí hay algunas buenas diapositivas sobre cómo hacer aproximaciones de series de potencia (aunque no las series de Taylor) de las funciones trigonométricas: http://www.research.scea.com/gdc2003/fast-math-functions.html

Está orientado a programadores de juegos, lo que significa que la precisión se sacrifica por el rendimiento, pero deberías poder agregar otro término o dos a las aproximaciones para recuperar algo de la precisión.

Lo bueno de esto es que también deberías poder extenderlo a SIMD fácilmente, de modo que puedas calcular el pecado o el cos de 4 valores a la vez (2 si estás usando doble precisión).

Espero que ayude...

Answer 3

Esto debería ser bastante rápido si puedes optimizarlo más, por favor hazlo y publica el código en pastie.org o algo así.

Especificaciones del equipo -> 512 MB Ram, Visual Studio 2010, Windows XP Professional SP3 versión 2002, Intel (R) Pentium (R) 4 CPU 2.8GHZ.

Esto es increíblemente preciso y proporcionará resultados ligeramente mejores en algunas situaciones. Por ejemplo, 90, 180, 270 grados en C ++ devuelve un decimal no 0.

TABLA COMPLETA DE 0 a 359 grados: https://pastee.org/dhwbj

FORMAT -> DEGREE # -> MINE_X (#), CosX (#), MINE_Z (#), SinZ (#).

A continuación se muestra el código utilizado para construir la tabla que se muestra arriba. Probablemente pueda hacerlo aún más preciso si usa un tipo de datos más grande. Utilicé un corto sin firmar e hice N / 64000. Entonces, ¿qué el cos (##) y el pecado (##) estuvieron más cerca de redondear a ese índice? También traté de usar la menor cantidad de datos adicionales posible, así que esta no sería una tabla desordenada con 720 valores de flotación para cos y sin. Lo cual probablemente daría mejores resultados, pero sería un completo desperdicio de memoria. La tabla a continuación es tan pequeña como podría hacerlo. Me gustaría ver si es posible hacer una ecuación que pueda redondear a todos estos valores cortos y usar eso en su lugar. No estoy seguro si sería más rápido, pero eliminaría la mesa por completo y probablemente no reduzca la velocidad por nada o mucho.

Entonces, la precisión en comparación con las operaciones cos / sin de C ++ es del 99.99998% hasta el 100%.

A continuación se muestra la tabla utilizada para calcular los valores de cos / sin.

static const unsigned __int16 DEGREE_LOOKUP_TABLE[91] =
{
    64000, 63990, 63961, 63912, 63844, 63756,
    63649, 63523, 63377, 63212, 63028, 62824,
    62601, 62360, 62099, 61819, 61521, 61204,
    60868, 60513, 60140, 59749, 59340, 58912,
    58467, 58004, 57523, 57024, 56509, 55976,
    55426, 54859, 54275, 53675, 53058, 52426,
    51777, 51113, 50433, 49737, 49027, 48301,
    47561, 46807, 46038, 45255, 44458, 43648,
    42824, 41988, 41138, 40277, 39402, 38516,
    37618, 36709, 35788, 34857, 33915, 32962,
    32000, 31028, 30046, 29055, 28056, 27048,
    26031, 25007, 23975, 22936, 21889, 20836,
    19777, 18712, 17641, 16564, 15483, 14397,
    13306, 12212, 11113, 10012,  8907,  7800,
     6690,  5578,  4464,  3350,  2234,  1117,
        0,
};

A continuación se muestra el código real que hace los cálculos de cos / sin.

    int deg1 = (int)degrees;
    int deg2 = 90 - deg1;
    float module = degrees - deg1;
    double vX = DEGREE_LOOKUP_TABLE[deg1] * 0.000015625;
    double vZ = DEGREE_LOOKUP_TABLE[deg2] * 0.000015625;
    double mX = DEGREE_LOOKUP_TABLE[deg1 + 1] * 0.000015625;
    double mZ = DEGREE_LOOKUP_TABLE[deg2 - 1] * 0.000015625;
    float vectorX = vX + (mX - vX) * module;
    float vectorZ = vZ + (mZ - vZ) * module;
    if (quadrant & 1)
    {
        float tmp = vectorX;
        if (quadrant == 1)
        {
            vectorX = -vectorZ;
            vectorZ = tmp;
        } else {
            vectorX = vectorZ;
            vectorZ = -tmp;
        }
    } else if (quadrant == 2) {
        vectorX = -vectorX;
        vectorZ = -vectorZ;
    }

VELOCIDADES A CONTINUACIÓN utilizando las especificaciones de computadora mencionadas originalmente. Lo estaba ejecutando en modo de depuración antes de que este sea el modo de depuración, pero se ejecuta a través del ejecutable, que creo que está depurado sin depuración.

MI MÉTODO

1,000 Iterations -> 0.004641 MS or 4641 NanoSeconds.
100,000 Iterations -> 4.4328 MS.
100,000,000 Iterations -> 454.079 MS.
1,000,000,000 Iterations -> 4065.19 MS.

MÉTODO COS / SIN

1,000 Iterations -> 0.581016 MS or 581016 NanoSeconds.
100,000 Iterations -> 25.0049 MS.
100,000,000 Iterations -> 24,731.6 MS.
1,000,000,000 Iterations -> 246,096 MS.

Así que para resumir lo anterior, realizar tanto cos (###) como sin (###) con mi estrategia permite aproximadamente 220,000,000 de ejecuciones por segundo. Utilizando las especificaciones de la computadora mostradas originalmente. Esto es bastante rápido y utiliza muy poca memoria, por lo que es un gran sustituto de las funciones matemáticas cos / sin que normalmente se encuentran en C ++. Si desea ver la precisión, abra el enlace que se muestra arriba y hay una impresión de grados 0 a 359. También esto admite de 0 a 89 y los cuadrantes de 0 a 3. Así que tendría que usar eso o realizar ( GRADOS% 90).

Answer 4

Hace mucho tiempo en máquinas lentas las personas usaban matrices con valores precalculados. otra opción para calcular con su propia precisión como this : (busque "Definiciones de serie")

Answer 5

Implementé una función sinusoidal rápida en el lado de la CPU, que es al menos dos veces más rápida que la función sinusoidal de math.h. Sin embargo, utilicé una tabla de búsqueda muy pequeña (20 flotadores). su precisión tampoco es mala; la tasa de error relativa promedio es 0.095%. puede consultarlo en http://www.hevi.info/tag/fast-sine-function/

La explicación del método es bastante simple y se basa en el hecho de que para small a''s sen (a) = a * pi / 180 (ver el enlace de arriba para la prueba)

Algo de trigonometría

Aunque es posible obtener resultados relativamente precisos con la fórmula que se muestra arriba para ángulos entre 0 y 10, a medida que el ángulo se hace más ancho a medida que pierde accuricy. Por lo tanto, deberíamos usar la fórmula para ángulos menores a 10 pero ¿cómo?

La respuesta proviene de la fórmula trigonométrica de adición de seno;

sin (a + b) = sin (a) cos (b) + sin (b) cos (a)

Si podemos mantener la ''b'' menor que 10, podremos usar nuestra fórmula para encontrar el seno con un par de operaciones aritméticas.

Digamos que nos preguntan el valor del seno para 71.654, entonces;

a = 70

b = 1.654

y,

sin (71.654) = sin (70 + 1.654) = sin (70) cos (1.654) + sin (1.654) cos (70)

En esta fórmula, podemos usar el cálculo rápido para la parte sin (1.654) y para el resto lamentablemente necesitamos tener tablas seno y coseno. Lo bueno es que solo necesitamos la multiplicación de decenas para ángulos sinusoidales y naturales entre 0 y 10 para el coseno.

Answer 6

La fuente de Quake 3 tiene algún código para Sine / Cos precalculado dirigido a la velocidad sobre la precisión, no es basado en SSE que sea bastante portátil (tanto en arquitectura como en API intrínseca). También puede encontrar este resumen de las funciones basadas en sse y sse2 muy interesante: http://gruntthepeon.free.fr/ssemath/

Answer 7

Para un 2-3% de ganancia, es casi seguro que no vale la pena el riesgo de inexactitud, error, las suposiciones ya no son ciertas (por ejemplo, nunca caer fuera de [-1,-1] ), etc., a menos que esté planeando ejecutar esto en una gran cantidad de máquinas (donde el 2-3% representa miles o millones de dólares en electricidad y el costo amortizado de la máquina).

Dicho eso, si tiene conocimiento específico del dominio sobre lo que está tratando de lograr, puede acelerar sus cálculos por un factor de dos o más. Por ejemplo, si siempre necesita sin y cos del mismo valor, calcúlelos cerca el uno del otro en el código y asegúrese de que su compilador los traduce en una instrucción de ensamblado FSINCOS (vea esta pregunta ). Si solo necesita una pequeña porción del rango completo de la función, puede usar potencialmente un conjunto de polinomios de bajo orden seguidos de una iteración del método de Newton para obtener la precisión completa de la máquina (o todo lo que necesite). De nuevo, esto es mucho más poderoso si sabes que solo necesitas algunos valores; por ejemplo, si puedes usar ese pecado (x) está cerca de x cerca de cero, y solo necesitarás valores cercanos a cero, entonces puedes disminuir drásticamente la cantidad de términos que necesita

Pero, nuevamente, mi consejo principal es: 2-3% no lo vale. Piense más sobre los algoritmos utilizados y otros posibles cuellos de botella (por ejemplo, si malloc está consumiendo demasiado tiempo) antes de optimizar esto.

Answer 8

Puedes ver http://gruntthepeon.free.fr/ssemath/ . Habla de optimizar el pecado, cos.

Answer 9

Si quieres usar una implementación personalizada, mira here , http://gruntthepeon.free.fr/ssemath/ y here

También here (vaya a Universal SIMD-Mathlibrary) si necesita calcular sin / cos para arreglos grandes

También puede intentar utilizar los intrínsecos C ++ SSE. Mira here

Tenga en cuenta que la mayoría de los compiladores modernos admiten optimizaciones SSE y SSE2. Para Visual Studio 2010, por ejemplo, deberá habilitarlo manualmente. Una vez que haga esto, se usará una implementación diferente para la mayoría de las funciones matemáticas estándar.

Una opción más es usar DirectX HLSL. Mira here . Tenga en cuenta que hay un bonito sincos funciones que devuelven tanto el pecado como el cos.

Por lo general, uso IPP (que no es gratis). Para más detalles, mira here