模算法与NTT(有限域DFT)优化

Question

模算法与NTT(有限域DFT)优化

我想使用NTT进行快速平方(参见快速大平方计算)，但是即使对于非常大的数字，结果也是缓慢的。超过12000位。

所以我的问题是：

1. 有办法优化我的NTT变换吗？我并不打算通过并行(线程)来加快它的速度；这只是低级层。
2. 有办法加速我的模块运算吗？

这是我的(已经优化的)C+的NTT源代码(它是完整的，100%工作在C+白化任何需要第三方库，也应该是线程安全的。请注意，源数组被用作临时的！，它也不能将数组转换为自身)。

//---------------------------------------------------------------------------

class fourier_NTT                                    // Number theoretic transform

    {

public:

    DWORD r,L,p,N;

    DWORD W,iW,rN;

    fourier_NTT(){ r=0; L=0; p=0; W=0; iW=0; rN=0; }

    // main interface

    void  NTT(DWORD *dst,DWORD *src,DWORD n=0);               // DWORD dst[n] = fast  NTT(DWORD src[n])

    void INTT(DWORD *dst,DWORD *src,DWORD n=0);               // DWORD dst[n] = fast INTT(DWORD src[n])

    // Helper functions

    bool init(DWORD n);                                       // init r,L,p,W,iW,rN

    void  NTT_fast(DWORD *dst,DWORD *src,DWORD n,DWORD w);    // DWORD dst[n] = fast  NTT(DWORD src[n])

    // Only for testing

    void  NTT_slow(DWORD *dst,DWORD *src,DWORD n,DWORD w);    // DWORD dst[n] = slow  NTT(DWORD src[n])

    void INTT_slow(DWORD *dst,DWORD *src,DWORD n,DWORD w);    // DWORD dst[n] = slow INTT(DWORD src[n])

    // DWORD arithmetics

    DWORD shl(DWORD a);

    DWORD shr(DWORD a);

    // Modular arithmetics

    DWORD mod(DWORD a);

    DWORD modadd(DWORD a,DWORD b);

    DWORD modsub(DWORD a,DWORD b);

    DWORD modmul(DWORD a,DWORD b);

    DWORD modpow(DWORD a,DWORD b);

    };

//---------------------------------------------------------------------------

void fourier_NTT:: NTT(DWORD *dst,DWORD *src,DWORD n)

    {

    if (n>0) init(n);

    NTT_fast(dst,src,N,W);

//    NTT_slow(dst,src,N,W);

    }

优化后的一些度量(当前代码、较低的递归参数大小/计数以及更好的模块化算法)：

检查NTTmul和NTTsqr时间(我的优化使它加快了3倍多)。它只有1倍的循环，所以它不是很精确(误差~10%)，但加速比即使现在也是明显的(通常我会循环它1000倍或更多，但我的NTT太慢了)。

你可以自由使用我的代码.。只需保留我的Nick和/或链接到这个页面的某个地方(rem in code，README.txt，约或诸如此类)。希望能帮上忙.。(我在任何地方都没有看到用于快速NTT的C+源代码，所以我不得不自己编写它)。统一的根测试了所有接受的N，见fourier_NTT::init(DWORD n)功能。