Вычислите косинус последовательности
Я должен вычислить следующее:
float2 y = CONSTANT;
for (int i = 0; i < totalN; i++)
h[i] = cos(y*i);
totalN является большим количеством, таким образом, я хотел бы сделать это более эффективным способом. Там какой-либо путь состоит в том, чтобы улучшить это? Я подозреваю, что существует, потому что, в конце концов, мы знаем то, что является результатом because(n) для n=1.. N, поэтому возможно, существует некоторая теорема, которая позволяет мне вычислять это более быстрым способом. Я был бы очень признателен за любую подсказку.
Заранее спасибо,
Federico
9 ответов
Используя одну из самых красивых формул математики, Эйлера формула
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 повторных умножений.
Таким образом, вы можете вычислить cos (n * phi) и одновременно sin (n * phi) путем многократного комплексного умножения на exp (i * 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);
}
}
Я не уверен, какой компромисс между точностью и производительностью вы готовы пойти, но по этим ссылкам есть подробные обсуждения различных методов приближения синусоид:
Развлечения с синусоидами - http: / /www.audiomulch.com/~rossb/code/sinusoids/
Быстрый и точный синус / косинус - http://www.devmaster.net/forums/showthread.php?t=5784
Править (Я думаю, что это ссылка «Дон Кросс», которая не работает на странице «Развлечения с синусоидами»):
Оптимизация расчетов триггеров - http://groovit.disjunkt.com/analog/time-domain/fasttrig .html
Возможно, самая простая формула -
cos (n + y) = 2cos (n) cos (y) - cos (n-y).
Если вы предварительно вычислите константу 2 * cos (y), то каждое значение cos (n + y) может быть вычислено из двух предыдущих значений с помощью одного единственного умножения и одного вычитания. Т.е. в псевдокоде
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]
Вот метод, но он использует немного памяти для греха. Он использует идентификаторы триггеров:
cos(a + b) = cos(a)cos(b)-sin(a)sin(b)
sin(a + b) = sin(a)cos(b)+cos(a)sin(b)
Тогда вот код:
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;
}
Если я не делал никаких ошибок, то это должно сработать. Конечно, могут возникнуть проблемы с округлением, так что имейте это в виду. Я реализовал это на Python, и это довольно точно.
Это можно сделать с помощью комплексных чисел.
Если вы определите x = sin(y) + i cos(y), cos(y*i) будет действительной частью x^i.
Вы можете вычислять для всех i итеративно. Комплексное умножение - это 2 умножения плюс два сложения.
Знание cos(n) не поможет - ваша математическая библиотека уже делает такие тривиальные вещи за вас.
Знание того, что cos((i+1)y)=cos(iy+y)=cos(iy)cos(y)-sin(iy)sin(y) может помочь, если вы предварительно вычислите cos(y) и sin(y), и будете следить за cos(iy) и sin(i*y) по пути. Однако это может привести к некоторой потере точности - вам придется проверить.
Насколько точным должен быть результирующий cos (x)? Если вы можете жить с некоторыми из них, вы можете создать справочную таблицу, выбирая единичный круг с интервалами 2 * PI / N, а затем интерполируя между двумя соседними точками. N будет выбран для достижения желаемого уровня точности.
Я не знаю, действительно ли интерполяция менее затратна, чем вычисление косинуса. Поскольку это обычно делается в микрокоде в современных процессорах, это может быть не так.
Здесь есть несколько хороших ответов, но все они рекурсивны. Рекурсивное вычисление не будет работать для функции косинуса при использовании арифметики с плавающей запятой; вы всегда будете получать ошибки округления, которые быстро усугубляются.
Рассмотрим расчет y = 45 градусов, всего N 10 000. Вы не получите 1 в качестве окончательного результата.
Чтобы решить проблемы Кирка: все решения, основанные на повторении для cos и sin, сводятся к вычислению
x (k) = R x (k - 1),
где R - матрица, которая вращается по y, а x (0) - единичный вектор (1, 0). Если истинный результат для k - 1 равен x '(k - 1), а истинный результат для k равен x' (k), тогда ошибка идет от e (k - 1) = x (k - 1) - x ' (k - 1) в e (k) = R x (k - 1) - R x '(k - 1) = R e (k - 1) по линейности. Поскольку R - это так называемая ортогональная матрица , R e (k - 1) имеет ту же норму, что и e (k - 1), и ошибка растет очень медленно. (Причина, по которой он вообще растет, связана с округлением; компьютерное представление R в целом почти, но не совсем ортогонально, поэтому потребуется время от времени перезапускать повторение, используя операции триггера, в зависимости от точности Это все еще намного быстрее, чем использование триггеров для вычисления каждого значения.)