Оптимизация алгоритма с тригонометрическими функциями

[ArtemKim]

Нужен совет по оптимизации данного алгоритма.
На вход алгоритм получает $N$ чисел $\psi_{1},\psi_{2},\ldots,\psi_{N}$ , $N$ пар $\left(x_{1},y_{1}\right),\left(x_{2},y_{2}\right),\ldots,\left(x_{N},y_{N}\right)$ и $L$ пар $\left(\theta_{1},\varphi_{1}\right),\left(\theta_{2},\varphi_{2}\right),\ldots,\left(\theta_{L},\varphi_{L}\right)$.
Далее вычисления выполняются так:

1. Случайно, с равномерным законом распределения, выбираем индекс $m\in\left[1,N\right]$
2. Вычисляем $B_{m}$ по формуле
   
   $B_{m}=\sum_{n=1}^{N}\sum_{l=1}^{L}e^{i\left(\psi_{n}+\alpha_{ml}-\alpha_{nl}\right)}-Le^{i\psi_{m}},$
   
   где
   
   $\alpha_{pq}=\frac{2\pi}{\lambda}\left(x_{p}\sin\theta_{q}\cos\varphi_{q}+y_{p}\sin\theta_{q}\sin\varphi_{q}\right);$
   
   
3. Вычисляем новое значение $\psi_{m}$ по формуле
   
   $\psi_{m}=\pi+\arg B_{m};$
4. Если еще не все $\psi_{m}$ обработаны, переходим на п.1;
5. Вывод $\left\{ \psi_{1},\psi_{2},\ldots,\psi_{N}\right\}$

В моей задаче $N$ порядка нескольких тысяч, $L=75$, а уложиться надо в несколько миллисекунд на 12-ядерном ксеоне.

Я делаю так: новое значение каждого $\psi_{m}$ вычисляется по формуле $\psi_{m}=\pi+\mathrm{\arctg}\frac{\sum_{l=1}^{L}\sin\alpha_{ml}\sum_{n=1}^{N}\cos\left(\psi_{n}-\alpha_{nl}\right)+\sum_{l=1}^{L}\cos\alpha_{ml}\sum_{n=1}^{N}\sin\left(\psi_{n}-\alpha_{nl}\right)-L\sin\psi_{m}}{\sum_{l=1}^{L}\cos\alpha_{ml}\sum_{n=1}^{N}\cos\left(\psi_{n}-\alpha_{nl}\right)-\sum_{l=1}^{L}\sin\alpha_{ml}\sum_{n=1}^{N}\sin\left(\psi_{n}-\alpha_{nl}\right)-L\cos\psi_{m}}$. Видно , что суммы $\sum_{n=1}^{N}\cos\left(\psi_{n}-\alpha_{nl}\right)$ и $\sum_{n=1}^{N}\sin\left(\psi_{n}-\alpha_{nl}\right)$, а также значения $\cos\alpha_{pq}$ и $\sin\alpha_{pq}$ можно вычислять заранее, параллельно для всех возможных комбинаций индексов. А после вычисления каждого нового значения $\psi_{m}$ заменять соответствующий ему элемент суммы.

Можно ли еще как-то преобразовать алгоритм, чтобы уменьшить количество вычислений тригонометрических функций ?

[Евгений Машеров]

Добавьте два массива SS и SC размерностью L, и до начала вычисления $B_m$ заполните их $ SC_q=\sin\theta_{q}\cos\varphi_{q}$ и $SS_q=\sin\theta_{q}\sin\varphi_{q}$

-- 08 апр 2015, 14:24 --

Этого должно хватить. Непонятно другое - выбираете случайно или так, чтобы перебрать все N значений в случайном порядке?

[ArtemKim]

Евгений Машеров в сообщении #1001576 писал(а):

Непонятно другое - выбираете случайно или так, чтобы перебрать все N значений в случайном порядке?

Перебрать все $m\in\left[1,N\right]$ в равномерно-случайном порядке без повторов. К сожалению не известна оптимальная последовательность перебора при $L>1$.