sharp better c# c++ c algorithm math

better - c++ vs c# vs c



¿Cuál es la forma más rápida de calcular el pecado y el cos juntos? (18)

¿Has pensado en declarar tablas de búsqueda para las dos funciones? Aún tendrías que "calcular" sin (x) y cos (x), pero sería decididamente más rápido, si no necesitas un alto grado de precisión.

Me gustaría calcular el seno y el co-seno de un valor juntos (por ejemplo, para crear una matriz de rotación). Por supuesto que podría calcularlos por separado uno tras otro como a = cos(x); b = sin(x); a = cos(x); b = sin(x); , pero me pregunto si hay una manera más rápida cuando se necesitan ambos valores.

Editar: Para resumir las respuestas hasta ahora:

  • Vlad dijo, que existe el comando asm FSINCOS los dos (casi al mismo tiempo que una llamada a FSIN solo)

  • Al igual que Chi notó, esta optimización a veces ya es realizada por el compilador (cuando se utilizan indicadores de optimización).

  • caf señaló que las funciones sincos y sincosf están probablemente disponibles y pueden ser llamadas directamente con solo incluir math.h

  • tanascius enfoque de tanascius de usar una tabla de búsqueda se discute controvertido. (Sin embargo, en mi computadora y en un escenario de referencia, funciona 3 veces más rápido que los sincos con casi la misma precisión para los puntos flotantes de 32 bits).

  • Joel Goodwin se relacionó con un enfoque interesante de una técnica de aproximación extremadamente rápida con una precisión bastante buena (para mí, esto es incluso más rápido que la búsqueda de la tabla)

Cuando el rendimiento es crítico para este tipo de cosas, no es inusual introducir una tabla de búsqueda.

Cuando necesita rendimiento, puede usar una tabla sin costo / cos calculada (una tabla lo hará, almacenada como un Diccionario). Bueno, depende de la precisión que necesites (tal vez la tabla sea grande), pero debería ser realmente rápido.

Es posible que desee echar un vistazo a http://gruntthepeon.free.fr/ssemath/ , que ofrece una implementación vectorizada SSE inspirada en la biblioteca CEPHES. Tiene una buena precisión (desviación máxima de sen / cos del orden de 5e-8) y velocidad (supera ligeramente a fsincos en una sola llamada y un claro ganador en varios valores).

Hay una buena solución en la biblioteca de CEPHES que puede ser bastante rápida y puede agregar / eliminar la precisión con bastante flexibilidad para un poco más / menos de tiempo de CPU.

Recuerde que cos (x) y sen (x) son las partes real e imaginaria de exp (ix). Entonces queremos calcular exp (ix) para obtener ambos. Precalculamos exp (iy) para algunos valores discretos de y entre 0 y 2pi. Cambiamos x al intervalo [0, 2pi). Luego seleccionamos la y que está más cerca de xy escribimos
exp (ix) = exp (iy + (ix-iy)) = exp (iy) exp (i (xy)).

Obtenemos exp (iy) de la tabla de búsqueda. Y desde | xy | es pequeño (a lo sumo la mitad de la distancia entre los valores y), la serie de Taylor convergerá muy bien en unos pocos términos, por lo que la usamos para exp (i (xy)). Y luego solo necesitamos una multiplicación compleja para obtener exp (ix).

Otra buena propiedad de esto es que puedes vectorizarlo usando SSE.

Los procesadores modernos Intel / AMD tienen instrucción FSINCOS para calcular las funciones de seno y coseno simultáneamente. Si necesita una buena optimización, tal vez debería usarla.

Aquí hay un pequeño ejemplo: http://home.broadpark.no/~alein/fsincos.html

Aquí hay otro ejemplo (para MSVC): http://www.codeguru.com/forum/showthread.php?t=328669

Aquí hay otro ejemplo (con gcc): http://www.allegro.cc/forums/thread/588470

Espero que uno de ellos ayude. (No usé esta instrucción yo mismo, lo siento)

Dado que son compatibles con el nivel del procesador, espero que sean mucho más rápidos que las búsquedas en tablas.

Editar:
Wikipedia sugiere que se agregó FSINCOS en 387 procesadores, por lo que difícilmente se puede encontrar un procesador que no lo soporte.

Editar:
La documentación de Intel establece que FSINCOS es aproximadamente 5 veces más lento que FDIV (es decir, división de coma flotante).

Editar:
Tenga en cuenta que no todos los compiladores modernos optimizan el cálculo de seno y coseno en una llamada a FSINCOS . En particular, mi VS 2008 no lo hizo de esa manera.

Editar:
El primer enlace de ejemplo está muerto, pero todavía hay una versión en Wayback Machine .

Los procesadores modernos x86 tienen una instrucción fsincos que hará exactamente lo que estás pidiendo: calcula el cos y el pecado al mismo tiempo. Un buen compilador de optimización debería detectar el código que calcula sin y cos para el mismo valor y usa el comando fsincos para ejecutarlo.

Tomó algunos giros de banderas de compilación para que esto funcionara, pero:

$ gcc --version i686-apple-darwin9-gcc-4.0.1 (GCC) 4.0.1 (Apple Inc. build 5488) Copyright (C) 2005 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. $ cat main.c #include <math.h> struct Sin_cos {double sin; double cos;}; struct Sin_cos fsincos(double val) { struct Sin_cos r; r.sin = sin(val); r.cos = cos(val); return r; } $ gcc -c -S -O3 -ffast-math -mfpmath=387 main.c -o main.s $ cat main.s .text .align 4,0x90 .globl _fsincos _fsincos: pushl %ebp movl %esp, %ebp fldl 12(%ebp) fsincos movl 8(%ebp), %eax fstpl 8(%eax) fstpl (%eax) leave ret $4 .subsections_via_symbols

¡Tada, usa la instrucción fsincos!

Muchas bibliotecas matemáticas C, como indica caf, ya tienen sincos (). La excepción notable es MSVC.

  • Sun ha tenido sincos () desde al menos 1987 (veintitrés años, tengo una página de hombre impresa)
  • HPUX 11 lo tuvo en 1997 (pero no está en HPUX 10.20)
  • Agregado a glibc en la versión 2.1 (Feb 1999)
  • Se incorporó a gcc 3.4 (2004), __builtin_sincos ().

Y con respecto a la búsqueda, Eric S. Raymond en el Art of Unix Programming (2004) (Capítulo 12) dice explícitamente que esta es una mala idea (en el momento presente en el tiempo):

"Otro ejemplo es precomputar tablas pequeñas, por ejemplo, una tabla de sin (x) por grado para optimizar rotaciones en un motor de gráficos 3D tomará 365 × 4 bytes en una máquina moderna. Antes de que los procesadores obtuvieran suficiente más rápido que la memoria para exigir el almacenamiento en caché , esta era una optimización de velocidad obvia. Hoy en día puede ser más rápido recalcular cada vez en lugar de pagar el porcentaje de fallas de caché adicionales causadas por la tabla.

"Pero en el futuro, esto podría cambiar nuevamente a medida que las memorias caché crecen. En términos más generales, muchas optimizaciones son temporales y pueden convertirse fácilmente en pesimismos a medida que cambian las relaciones de costos. La única manera de saber es medir y ver". (de la programación de Art of Unix )

Pero, a juzgar por la discusión anterior, no todos están de acuerdo.

No creo que las tablas de búsqueda sean necesariamente una buena idea para este problema. A menos que sus requisitos de precisión sean muy bajos, la tabla debe ser muy grande. Y las CPU modernas pueden hacer una gran cantidad de cálculos mientras se obtiene un valor de la memoria principal. Esta no es una de esas preguntas que pueden responderse adecuadamente con argumentos (ni siquiera los míos), probar y medir y considerar los datos.

Pero me gustaría ver las implementaciones rápidas de SinCos que se encuentran en bibliotecas como ACML de AMD y MKL de Intel.

Para un enfoque creativo, ¿qué tal expandir la serie de Taylor? Como tienen términos similares, podrías hacer algo como el siguiente pseudo:

numerator = x denominator = 1 sine = x cosine = 1 op = -1 fact = 1 while (not enough precision) { fact++ denominator *= fact numerator *= x cosine += op * numerator / denominator fact++ denominator *= fact numerator *= x sine += op * numerator / denominator op *= -1 }

Esto significa que debes hacer algo como esto: comenzando en x y 1 para sin y coseno, sigue el patrón - ¡resta x ^ 2/2! de coseno, reste x ^ 3/3! de seno, ¡añada x ^ 4/4! al coseno, ¡añada x ^ 5/5! al seno ...

No tengo idea de si esto sería perfecto. Si necesita menos precisión que la incorporada en sin () y cos (), puede ser una opción.

Puede calcular cualquiera y luego usar la identidad:

cos(x)2 = 1 - sin(x)2

pero como dice @tanascius, una tabla precalculada es el camino a seguir.

Si está dispuesto a usar un producto comercial y está calculando una cantidad de cálculos sen / cos al mismo tiempo (para que pueda usar funciones vectorizadas), debe consultar la Biblioteca de Kernel de Matemáticas de Intel.

Tiene una función sincos

De acuerdo con esa documentación, promedia 13.08 relojes / elemento en core 2 duo en modo de alta precisión, que creo que será incluso más rápido que fsincos.

Si usa la biblioteca C de GNU, puede hacer:

#define _GNU_SOURCE #include <math.h>

y obtendrá las declaraciones de las sincos() , sincosf() y sincosl() que calculan ambos valores juntos, presumiblemente de la manera más rápida para su arquitectura de destino.

Técnicamente, lograrías esto usando números complejos y la Fórmula de Euler . Por lo tanto, algo así como (C ++)

complex<double> res = exp(complex<double>(0, x)); // or equivalent complex<double> res = polar<double>(1, x); double sin_x = res.imag(); double cos_x = res.real();

debería darle seno y coseno en un solo paso. Cómo se hace esto internamente es una cuestión del compilador y la biblioteca que se utiliza. Podría (y podría) tomar más tiempo hacerlo de esta manera (solo porque la Fórmula de Euler se usa principalmente para calcular el exp complejo usando sin y cos - y no al revés), pero podría haber alguna optimización teórica posible.

Editar

Los encabezados en <complex> para GNU C ++ 4.2 están usando cálculos explícitos de sin y cos dentro de polar , por lo que no se ven muy bien para las optimizaciones allí a menos que el compilador haga algo de magia (ver los -ffast-math y -mfpmath como escrito en la respuesta de Chi ).

Una aproximación precisa pero rápida de las funciones sin y cos simultáneamente, en javascript, se puede encontrar aquí: http://danisraelmalta.github.io/Fmath/ (fácilmente importado a c / c ++)