Aproximación numéricamente eficiente de cos(s)

Question

Tengo una aplicación en la que tengo que ejecutar $\cos(s)$ (e $\operatorname{sinc}(s) = \sin(s)/s$) un gran número de veces y es medido a ser un cuello de botella en mi aplicación.

No necesito cada último dígito de precisión: $10^{-10}$ sobre un rango de entrada de $[-15^\circ < s < 15^{\circ}]$ debería ser suficiente (Este es el límite del sensor de entrada de datos).

He implementado una simple aproximación de Taylor, pero me gustaría preguntar:

• (a) ¿existe una forma más eficiente de aproximación?

• (b) Si Taylor es el más eficiente, es que hay una forma mejor de hacerlo?

  // Equation Coefficients
  double s_2  = 0.25 * omega_ebe.squaredNorm();
  double s_4  = s_2 * s_2;
  double s_6  = s_4 * s_2;
  double s_8  = s_6 * s_2;
  double s_10 = s_8 * s_2;
  
  double cos_coef  = 1.0 - s_2 /  2.0 + s_4 /  24.0 - s_6 /   720.0 + s_8 /  40320.0 - s_10 /  3628800.0;
  double sinc_coef = 0.5 - s_2 / 12.0 + s_4 / 240.0 - s_6 / 10080.0 + s_8 / 725760.0 - s_10 / 79833600.0;
  

---

EDIT: no he olvidado a seleccione una respuesta. Voy a código de algunos de los y las ejecutan en destino (incorporado un PowerPC y una incrustado BRAZO) para ver cómo se realizan.

Answer 1

Usted puede mejorar la Taylor/Padé idea. Lo que usted puede hacer es la escala de su argumento repetido reducir a la mitad; decir, $z^\prime=\dfrac{z}{2^n}$ donde $n$ elegido es tal que el término de error en cualquiera de los Taylor o Padé approximants es pequeña, es suficiente. Habiendo hecho esto, usted puede recorrer el ángulo doble identidad (que es, $\cos\,2z=2\cos^2 z-1$) $n$ veces en el resultado de la Taylor o Padé approximant evaluados en $z^\prime$. El resultado es el coseno del valor que usted necesita.

Si usted necesita un sinusoidal de valor, usted tendrá que par el doble ángulo de identidad para el coseno con el doble ángulo de identidad para el seno, $\sin\,2z=2\sin\,z\cos\,z$.

---

Un Mathematica demostración:

testCos[z_?InexactNumberQ] := Module[{co, za = z, k = 0},
  (* repeated halving *)
  While[Abs[za] > 1/4, za /= 2; k++];
  (* Padé approximant *)
  co = (1 + za^2*(-115/252 + (313*za^2)/15120))/(
        1 + za^2*(11/252 + (13*za^2)/15120));
  (* double-angle identity *)
  Do[co = 2 co^2 - 1, {k}];
  co]

Plot[testCos[z] - Cos[z], {z, -Pi, Pi}, PlotRange -> All]

El Abs[za] > 1/4 criterio fue determinado por el trazado de la Padé approximant y determinar el intervalo en donde la diferencia entre éste y el coseno fue "suficientemente pequeño". Usted tendrá que experimentar con su aplicación en particular.

fedja's consejos en los comentarios debe destacarse un poco: si usted toma la de Taylor o de Padé de la ruta, vale la pena poner su polinómica o racional en función de Horner forma. Menos esfuerzo es necesario en la evaluación, y puede ser más preciso que el polinomio expandido o función racional.

Answer 2

Este es probablemente más una cuestión de StackOverflow, porque ¿cómo algoritmos eficientes depende de la arquitectura del procesador, se tiene que el valor de tablas en contra de cálculos directos y los programadores son realmente buenos en eso.

No es de extrañar, entonces, que ya hay una pregunta que se encarga de su problema bastante bien: http://stackoverflow.com/questions/2088194/fast-sin-cos-using-a-pre-computed-translation-array. La mayoría de las soluciones no ceder su exactitud, pero se puede comprobar después y aumentar la precisión, si no es lo suficientemente alto.

Answer 3

Padé aproximaciones son mejor que Taylor aproximaciones para el mismo número de términos, sino porque es probable que se preocupan más sobre la media o error máximo en un rango de interés, más que en torno a un punto específico, en la práctica los diferentes polinomios o funciones racionales son utilizados. Ella a menudo se derivan de la utilización de la Remez cambio de algoritmo.

Para ejemplos de funciones que se usan en la práctica ver fdlibm o Impulso de Matemáticas.

También he conseguido sacar un papel recordé haber leído sobre el uso de los algoritmos genéticos para evolucionar mejoras a Padé aproximaciones: Hacia una Mejor Onda Sinusoidal, Mateo Streeter y Lee A. Becker, 2001 Genética y la Computación Evolutiva de la Conferencia Finales de Romper Papeles, pp398-404.

Answer 4

He aquí una pregunta muy importante: ¿cuál es el alcance de tus entradas? Si son de tamaño considerable (por ejemplo, ~2^100), a continuación, con precisión de tomar modulo 2*pi (para reducir el rango de a donde su serie de Taylor es exacta) dominará el esfuerzo computacional.

Como para el núcleo de la función, me gustaría segundo el Remez algoritmo para la generación de polinomios.

Un método más fácil sería la de generar el polinomio de mínimos cuadrados para el intervalo de tiempo que usted está interesado en. Es básico de álgebra lineal: estás proyectando su vector (coseno) en un conjunto de vectores de la base (los polinomios x^0...x^n), con el producto interior(a,B) se define como la integral definida de Una*B en el intervalo de tiempo que usted está interesado en. De esta manera se consigue que el polinomio con el mínimo total de cuadrados de error de la función coseno de un grado determinado.

Si usted está interesado en mirar el código, tengo un par de ejemplos de este tipo de cosas para la función seno: https://github.com/jeremysalwen/vectrig

Answer 5

Pues parece que necesita el seno y coseno (cardenal) en su aplicación, otro método que puede utilizar se basa en la identidad

$$\begin{align*}\cos\,x&=\frac{1-\tan^2\frac{x}{2}}{1+\tan^2\frac{x}{2}}\\\sin\,x&=\frac{2\tan\frac{x}{2}}{1+\tan^2\frac{x}{2}}\end{align*}$$

and the double angle identity

$$\tan\,2x=\frac{2\tan\,x}{1-\tan^2 x}$$

El método es similar a la del coseno método me dio anteriores; reducir a la mitad el argumento de un número apropiado de veces en que el error de la Taylor o Padé approximant evaluados en el que la reducción de argumento es pequeño, evaluar la approximant, repetidamente aplicar el doble del ángulo de la fórmula, y se transforman en el seno y coseno del uso de las identidades.

Aquí está una Mathematica demostración:

testCS[z_?InexactNumberQ] := Module[{ta, za = z/2, k = 0},
  (* repeated halving *)
  While[Abs[za] > 1/4, za /= 2; k++];
  (* Padé approximant *)
  ta = za (1 + (za^2/105 - 1) (za/3)^2)/(1 + (za^2/7 - 4) (za/3)^2);
  (* double-angle identity *)
  Do[ta = 2 ta/(1 - ta^2), {k}];
  (* cosine and sine *)
  {(1 - ta^2)/(1 + ta^2), 2 ta/(1 + ta^2)}]

GraphicsGrid[{{
   Plot[First[testCS[z]] - Cos[z], {z, -Pi/6, Pi/6}, 
        PlotRange -> All], 
   Plot[Last[testCS[z]] - Sin[z], {z, -Pi/6, Pi/6}, 
        PlotRange -> All]
               }}]