algorithm - 计算序列的余弦

Question

我必须计算以下内容:

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

totalN 是一个很大的数字，所以我想以更有效的方式进行。有什么办法可以改善吗？我怀疑有，因为毕竟我们知道 n=1..N 时 cos(n) 的结果是什么，所以也许有一些定理可以让我以更快的方式计算它。如果有任何提示，我将不胜感激。

提前致谢

费德里科

Answer 1

使用最美丽的数学公式之一，Euler's formula
exp(i*x) = cos(x) + i*sin(x),

替换 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

幂 ^n 是 n 次重复乘法。 因此，您可以通过 exp(i*phi) 的重复复数乘法来计算 cos(n*phi) 并同时计算 sin(n*phi)从 (1+i*0) 开始。

代码示例:

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)

或 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);
  }
}