Calcular el coseno de una secuencia

Question

tengo que calcular lo siguiente:

float2 y = CONSTANT; 
for (int i = 0; i < totalN; i++) 
    h[i] = cos(y*i); 

totalN es un número grande, así que me gustaría hacer esto de una manera más eficiente. ¿Hay alguna forma de mejorar esto? Sospecho que sí, porque, después de todo, sabemos cuál es el resultado de cos (n), para n = 1..N, entonces tal vez haya algún teorema que me permita calcular esto de una manera más rápida. Realmente apreciaría cualquier pista.

Gracias de antemano,

Federico

Answer 1

Utilizando una de las más bellas fórmulas de las matemáticas, Euler's formula
exp(i*x) = cos(x) + i*sin(x),

sustituyendo x := n * phi:

cos(n*phi) = Re(exp(i*n*phi))
sin(n*phi) = Im(exp(i*n*phi))

exp(i*n*phi) = exp(i*phi)^n

Poderes n multiplicaciones repetidas. Por lo tanto, puede calcular cos(n*phi) y simultáneamente sin(n*phi) por multiplicación compleja repetida por exp(i*phi) empezando por (1+i*0).

Ejemplos de código:

Python:

from math import * 

DEG2RAD = pi/180.0 # conversion factor degrees --> radians 
phi = 10*DEG2RAD # constant e.g. 10 degrees 

c = cos(phi)+1j*sin(phi) # = exp(1j*phi) 
h=1+0j 
for i in range(1,10): 
    h = h*c 
    print "%d %8.3f"%(i,h.real) 

o C:

#include <stdio.h> 
#include <math.h> 

// numer of values to calculate: 
#define N 10 

// conversion factor degrees --> radians: 
#define DEG2RAD (3.14159265/180.0) 

// e.g. constant is 10 degrees: 
#define PHI (10*DEG2RAD) 

typedef struct 
{ 
    double re,im; 
} complex_t; 


int main(int argc, char **argv) 
{ 
    complex_t c; 
    complex_t h[N]; 
    int index; 

    c.re=cos(PHI); 
    c.im=sin(PHI); 

    h[0].re=1.0; 
    h[0].im=0.0; 
    for(index=1; index<N; index++) 
    { 
    // complex multiplication h[index] = h[index-1] * c; 
    h[index].re=h[index-1].re*c.re - h[index-1].im*c.im; 
    h[index].im=h[index-1].re*c.im + h[index-1].im*c.re; 
    printf("%d: %8.3f\n",index,h[index].re); 
    } 
} 

Answer 2

Puede hacerlo utilizando números complejos.

si defines x = sin (y) + i cos (y), cos (y * i) será la parte real de x^i.

Puede calcular todo de forma iterativa. La multiplicación compleja es 2 multiplicaciones más dos agregaciones.

Answer 3

Conocer cos (n) no ayuda - tu biblioteca de matemáticas ya hace estas cosas triviales para ti.

Sabiendo que cos ((i + 1) y) = cos (i y + y) = cos (i y) cos (y) -sen (i y) sin (y) puedo ayudar , si calcula previamente cos (y) y sin (y), y realiza un seguimiento de ambos cos (i y) y sin (i * y) en el camino. Sin embargo, puede dar lugar a cierta pérdida de precisión, tendrá que comprobar.

Answer 4

Aquí hay un método, pero usa un poco de memoria para el pecado. Utiliza las identidades trigonométricas:

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

Entonces aquí está el código:

h[0] = 1.0; 
double g1 = sin(y); 
double glast = g1; 
h[1] = cos(y); 
for (int i = 2; i < totalN; i++){ 
    h[i] = h[i-1]*h[1]-glast*g1; 
    glast = glast*h[1]+h[i-1]*g1; 

} 

Si no hice ningún error entonces que debe hacerlo. Por supuesto, podría haber problemas de redondeo, así que tenlo en cuenta. Implementé esto en Python y es bastante preciso.

Answer 5

no estoy seguro de qué tipo de precisión vs rendimiento compromisos que está dispuesto a hacer, pero hay discusiones extensas de varias técnicas de aproximación sinusoidal en estos enlaces:

Diversión con Sinusoides - http://www.audiomulch.com/~rossb/code/sinusoids/
rápida y precisa de seno/coseno - http://www.devmaster.net/forums/showthread.php?t=5784

Editar (creo que esto es el enlace "Don Cruz" que se ha roto en la página "Diversión con Sinusoides"):

Optimización Trig Cálculos - http://groovit.disjunkt.com/analog/time-domain/fasttrig.html

Answer 6

¿Qué precisión necesita para que el cos (x) resultante sea? Si puede vivir con algunos, puede crear una tabla de búsqueda, muestreando el círculo de la unidad a intervalos de 2 * PI/N y luego interpolar entre dos puntos adyacentes. N se elegiría para alcanzar el nivel deseado de precisión.

Lo que no sé es si una interpolación es realmente menos costosa que calcular un coseno. Como suele hacerse en microcódigo en CPU modernas, puede que no lo sea.

Answer 7

Tal vez la fórmula más simple es

cos (n + y) = 2cos (n) cos (y) - cos (n-y).

Si calcula previamente el constante 2 * cos (y), cada valor cos (n + y) se puede calcular a partir de los 2 valores anteriores con una sola multiplicación y una resta. es decir, en pseudocódigo

h[0] = 1.0 
h[1] = cos(y) 
m = 2*h[1] 
for (int i = 2; i < totalN; ++i) 
    h[i] = m*h[i-1] - h[i-2] 

Answer 8

hay algunas buenas respuestas aquí, pero todos ellos son recursiva. El cálculo recursivo no funcionará para la función del coseno cuando se usa la aritmética de coma flotante; invariablemente obtendrás errores de redondeo que se combinan rápidamente.

Considere el cálculo y = 45 grados, totalN 10 000. No obtendrá 1 como resultado final.

Answer 9

para abordar las preocupaciones de Kirk: todas las soluciones basadas en la recurrencia de COS y pecado reducen a computar

x (k) = R x (k - 1),

donde R es la la matriz que gira en yyx (0) es el vector unitario (1, 0). Si el resultado verdadero para k - 1 es x '(k - 1) y el resultado verdadero para k es x' (k), entonces el error va de e (k - 1) = x (k - 1) - x ' (k - 1) a e (k) = R x (k - 1) - R x '(k - 1) = R e (k - 1) por linealidad. Dado que R es lo que se llama una matriz ortogonal , R e (k - 1) tiene la misma norma que e (k - 1), y el error crece muy lentamente. (La razón por la que crece se debe al redondeo, la representación de la computadora de R es en general casi, pero no del todo ortogonal, por lo que será necesario reiniciar la recurrencia usando las operaciones trigonométricas de vez en cuando dependiendo de la precisión requerido. Esto todavía es mucho, mucho más rápido que usar las operaciones trigonométricas para calcular cada valor.)