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

double PI;
typedef double complex cplx;

//<summary>Вычисление среднего квадратического, сложность O(n)</summary>
//<param name="v">Массив данных</param>
//<param name="n">Размер массива</param>
//<returns>Среднее квадратическое</returns>
double rms(double* v, int n)
{
    int i;
    double sum = 0.0;
    for (i = 0; i < n; i++)
        sum += v[i] * v[i];
    return sqrt(sum / n);
}

void _fft(cplx buf[], cplx out[], int n, int step)
{
    if (step < n) {
        _fft(out, buf, n, step * 2);
        _fft(out + step, buf + step, n, step * 2);

        for (int i = 0; i < n; i += 2 * step) {
            cplx t = cexp(-I * PI * i / n) * out[i + step];
            buf[i / 2]     = out[i] + t;
            buf[(i + n)/2] = out[i] - t;
        }
    }
}

//<summary>Быстрое преобразование Фурье, сложность O(n log n)</summary>
//<param name="buf[]">Массив данных комплексных чисел (C99)</param>
//<param name="n">Размер массива(размер должен быть степенью двойки)</param>
void fft(cplx buf[], int n)
{
    cplx out[n];
    for (int i = 0; i < n; i++) out[i] = buf[i];

    _fft(buf, out, n, 1);
}

//<summary>Пример алгоритма с квадратичной временной сложностью O(n*n)</summary>
void n2Sample(double* v, int n)
{
    int i;
    int j;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            v[j] += 0;
        }
    }
}

int main(void)
{

    double v[16000];//Датчик 8000гц, частота дискретизации должна быть в 2 раза выше = 16000гц, значит 16 000 значений в секунду
                    //их можно буферизировать в течении секунды, производить обработку и отсылать в сеть результат.
    rms(v, sizeof(v) / sizeof(double)); //Сложность O(n)
    n2Sample(v, sizeof(v) / sizeof(double));//Сложность O(n*n)

    //Пример для быстрого преобразования фурье
    PI = atan2(1, 1) * 4;
    cplx buf[16384];//Массив комплексных чисел, можно заполнять как обычный напимер buf[0]=1.0; buf[1] = 2;
    fft(buf, 16384);//Сложность O(n log n)

    return 0;
}