Calcola il coseno di una sequenza

Question

devo calcolare:

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

totalN è un gran numero, così desidero fare questo in modo più efficiente. C'è un modo per migliorare questo? Sospetto che ci sia, perché, dopo tutto, sappiamo qual è il risultato di cos (n), per n = 1..N, quindi forse c'è qualche teorema che mi permette di calcolarlo in un modo più veloce. Gradirei davvero qualche suggerimento.

Grazie in anticipo,

Federico

Answer 1

Utilizzando uno dei più bei formule della matematica, Euler's formula
exp(i*x) = cos(x) + i*sin(x),

sostituendo 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

Potenza ^n è moltiplicazioni ripetute n. Pertanto è possibile calcolare cos(n*phi) e contemporaneamente sin(n*phi) ripetendo la moltiplicazione complessa per exp(i*phi) a partire da (1+i*0).

Esempi di codice:

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

È possibile farlo utilizzando i numeri complessi.

se si definisce x = sin (y) + i cos (y), cos (y * i) sarà la parte reale di x^i.

È possibile calcolare tutto ciò in modo iterativo. Il multiplo complesso è di 2 moltiplicazioni più due aggiunte.

Answer 3

Sapere cos (n) non aiuta - la tua biblioteca matematica fa già questo tipo di cose banali.

Sapendo che cos ((i + 1) y) = cos (i y + y) = cos (i y) cos (y) -sin (i y) sin (y) può aiutare , se precalcoli cos (y) e sin (y), e tieni traccia di entrambi i cos (i y) e sin (i * y) lungo la strada. Potrebbe tuttavia comportare una perdita di precisione, ma dovrai controllare.

Answer 4

Ecco un metodo, ma utilizza un po 'di memoria per il peccato. Esso utilizza le identità trigonometriche:

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

Poi ecco il codice:

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; 

} 

Se non ho fatto errori, allora che dovrebbe farlo. Ovviamente potrebbero esserci problemi di arrotondamento, quindi sii consapevole di ciò. L'ho implementato in Python ed è abbastanza accurato.

Answer 5

io non sono sicuro di che tipo di accuratezza rispetto a prestazioni compromessi si è disposti a fare, ma ci sono ampie discussioni su varie tecniche di approssimazione sinusoide a questi collegamenti:

Divertimento con sinusoidi - http://www.audiomulch.com/~rossb/code/sinusoids/
rapida e precisa seno/coseno - http://www.devmaster.net/forums/showthread.php?t=5784

Edit (credo che questo è il link "Don Croce" che è rotto sulla pagina "Divertimento con sinusoidi"):

Ottimizzazione Trig Calcoli - http://groovit.disjunkt.com/analog/time-domain/fasttrig.html

Answer 6

Quanto preciso è necessario il cos (x) risultante? Se riesci a conviverci con qualcuno, puoi creare una tabella di ricerca, campionare il cerchio unitario a intervalli 2 * PI/N e quindi interpolare tra due punti adiacenti. N verrebbe scelto per raggiungere un certo livello di accuratezza desiderato.

Quello che non so è se un'interpolazione sia effettivamente meno costosa del calcolo di un coseno. Dal momento che solitamente viene fatto in microcodice nelle moderne CPU, potrebbe non esserlo.

Answer 7

Forse la formula più semplice è

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

Se si precomputa la costante 2 * cos (y), allora ciascun valore cos (n + y) può essere calcolato dai precedenti 2 valori con una singola moltiplicazione e una sottrazione. cioè in pseudocodice

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

ci sono alcune buone risposte qui, ma sono tutti ricorsivo. Il calcolo ricorsivo non funzionerà per la funzione coseno quando si utilizza l'aritmetica in virgola mobile; invariabilmente riceverai errori di arrotondamento che si accumulano rapidamente.

Considerare il calcolo y = 45 gradi, totaleN 10 000. Non si otterrà 1 come risultato finale.

Answer 9

Per affrontare le preoccupazioni di Kirk: tutte le soluzioni in base alla ricorrenza per cos e il peccato si riducono al calcolo

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

dove r è il la matrice che ruota con ye x (0) è il vettore unitario (1, 0). Se il risultato vero per k - 1 è x '(k - 1) e il risultato vero per k è x' (k), allora l'errore va da e (k - 1) = x (k - 1) - x ' (k - 1) a e (k) = R x (k - 1) - R x '(k - 1) = R e (k - 1) per linearità. Poiché R è quella che viene chiamata una matrice ortogonale , R e (k - 1) ha la stessa norma di e (k - 1) e l'errore aumenta molto lentamente. (Il motivo per cui cresce è dovuto al round-off, la rappresentazione computerizzata di R è in generale quasi, ma non del tutto ortogonale, quindi sarà necessario riavviare la ricorrenza utilizzando le operazioni trig di volta in volta a seconda della precisione richiesto.Questo è ancora molto, molto più veloce dell'uso dei trig ops per calcolare ogni valore.)