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


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 bastante pesado en numéricos (es una simulación de física) y que necesita llamar funciones trigonométricas, principalmente sin y cos, mucho. 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 más rápido sin y cos podría darme un porcentaje adicional .. Entonces, ¿tienen alguna sugerencia?
En otro enviar 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?


32
2018-04-25 09:43


origen


Respuestas:


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...


17
2018-04-25 12:45



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. P.ej. 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).


6
2018-04-25 13:57



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/ 


3
2018-04-25 13:56



Si desea usar una implementación personalizada, mire aquí, aquí y aquí

también aquí (desplácese a Universal SIMD-Mathlibrary) si necesita calcular sin / cos para arreglos grandes

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

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 aquí. Tenga en cuenta que hay un buen sincos funciones que devuelven tanto a sen como a cos.

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


3
2018-04-25 14:02



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 profilers basado en los conceptos de gprof no le diga acerca de las llamadas de la mitad de la pila en las que podría enfocarse para ahorrar grandes cantidades de tiempo. Aquí hay un ejemplo.


2
2018-02-11 16:48



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%. puedes verlo desde 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)

enter image description here

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.


2
2018-04-25 09:49



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


1
2018-01-10 09:17



Puedes mirar esta. Habla de optimizar el pecado, cos.


1
2018-04-25 14:31