利用FFT算法计算 [英] Using the FFT algorithm to calculate

问题描述

给定一组n个粒子的电荷载体创立上的点（1,0），（2,0），....（N，0）在一个平面上。 在点发现的粒子电荷（I，0）记为奇。在颗粒上起作用的力由下式给出：

Given a set of n particles electric charge carriers founds on the points (1,0), (2,0), .... (n,0) on a plane. The particle charge that found in point (i,0) is noted as Qi. the force that act on the particle is given by the formula:

C是库仑常数。

C is a Coulomb's constant.

给出一个算法来计算网络连接，所有的总复杂度为O（nlgn）的颗粒。 提示：使用FFT算法

Give an algorithm to calculate Fi, for all of the particles in total complexity O(nlgn). Hint: use FFT algorithm.

似乎连接已分割为偶数和奇数点..

It seems that Fi is already divided to the even and odd points..

我想过将每一笔计算FFT（但划分到什么..？）和 然后总和总是一半的点（因为这是什么原因FFT），然后减去上式，鉴于和的结果。

I thought about to divide each sum to calculate the FFT (but divide until what..?) and then sum always half of the points (cause this is what FFT cause) and then subtract the result of the sums that given on the formula..

如何做的更好什么想法？

any idea of how to do it better?

推荐答案

看起来像功课所以没有实际的$ C $下您的情况，而不是提供一些示例和提示。
对于FFT样算法：

looks like homework so no actual code for your case is provided instead some example and hints.
for FFT-like algorithms:

1.设置数据集大小为2的幂零填充

1.set the dataset size to power of 2 by zero padding

• 所以分工半很简单（没有余数）

2.创建递归函数来计算您的FFT一样的东西

2.create recursive function to compute your FFT-like stuff

• 在它重新排序的数据集
• 将其划分为两个部分
• 和递归调用它的自我2次（每次用不同的一半数据）
• 添加if语句开始
  • 如果数据集大小＆LT; = 1或2，然后返回直接计算值
  • 要确保递归停止
  • in it reorder the data set
  • divide it to two halves
  • and recursively call it self 2 times (each with the different half of data)
  • and add if statement to start
    • if dataset size <=1 or 2 then return directly computed value
    • to ensure that recursion stops

    3.取出的，如果需要的结果补零

    3.remove zero padding from the result if needed

    例如，这是NTT怎么我的样子（数论变换）

    For example this is how mine NTT looks like (Number theoretic transform)

    //---------------------------------------------------------------------------
    void fourier_NTT:: NTT_fast(DWORD *dst,DWORD *src,DWORD n,DWORD w)
        {
        // recursion stop condition if the data is single number ...
        if (n<=1) { if (n==1) dst[0]=src[0]; return; }
        DWORD i,j,a0,a1,n2=n>>1,w2=modmul(w,w);
        // reorder even,odd to dst array
        for (i=0,j=0;i<n2;i++,j+=2) dst[i]=src[j];
        for (    j=1;i<n ;i++,j+=2) dst[i]=src[j];
        // recursion
        NTT_fast(src   ,dst   ,n2,w2);  // even
        NTT_fast(src+n2,dst+n2,n2,w2);  // odd
        // restore results
        for (w2=1,i=0,j=n2;i<n2;i++,j++,w2=modmul(w2,w))
            {
            a0=src[i];
            a1=modmul(src[j],w2);
            dst[i]=modadd(a0,a1);
            dst[j]=modsub(a0,a1);
            }
        }
    //---------------------------------------------------------------------------
    

    • 在完整的源$ C ​​$ c和详细信息是这里
    • full source code and more info is here

    始终与比较缓慢执行快速执行的结果！

    • 在某些系数或索引一个小错误可能会导致巨大差异的结果
    • 在不断增长的数据集大小

    这是缓慢的实现上述功能的NTT：

    this is slow implementation for above NTT function:

    //---------------------------------------------------------------------------
    void fourier_NTT:: NTT_slow(DWORD *dst,DWORD *src,DWORD n,DWORD w)
        {
        DWORD i,j,wj,wi,a,n2=n>>1;
        for (wj=1,j=0;j<n;j++)
            {
            a=0;
            for (wi=1,i=0;i<n;i++)
                {
                a=modadd(a,modmul(wi,src[i]));
                wi=modmul(wi,wj);
                }
            dst[j]=a;
            wj=modmul(wj,w);
            }
        }
    //---------------------------------------------------------------------------
    

    [注意事项]

    1.now你有你的分离式

    1.now you have your separation equation

    • 在获得直接计算值之间的系数diferentce
    • 和价值2倍半递归调用
    计算
    • ，并相应地恢复你的结果使输出相匹配的正确的结果

    这篇关于利用FFT算法计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！