如何使用快速傅立叶变换计算数组元素的乘积之和?

How to calculate a sum of products of array elements using a fast Fourier transform?

我有一些二进制数组。例如,让我的数组是:

int a[] = {1, 0, 0, 0, 1, 0, 1, 0, 1}

我想根据这个公式计算值:

如何使用快速傅里叶变换计算此函数?我有一个大数组,我必须多次计算这个函数。所以,我希望能够快速计算出这个函数。

void main()
{
    int i,k,sum=0; 
    for(i=0;i<9;i++)
    {
        for(k=0;k<2*i;k++) 
        {
            sum + =(a[k]*a[2*i-k]; // calculating B
        }
    }
    cout<<sum;
}

你所做的计算基本上是一个卷积,时域中的卷积只是频率的乘法 domain.So 只需得到 a 的 FFT 并将其与自身相乘,然后执行IFFT to return to the time domain.So 总之,可以通过

计算b
b(2*i) = IFFT( FFT(a[0:2*i)]).FFT(a[0:2*i]) )