模算法與NTT(有限域DFT)優(yōu)化我想使用NTT進(jìn)行快速平方(參見快速大平方計(jì)算)，但是即使對于非常大的數(shù)字，結(jié)果也是緩慢的。超過12000位。所以我的問題是：有辦法優(yōu)化我的NTT變換嗎？我并不打算通過并行(線程)來加快它的速度；這只是低級層。有辦法加速我的模塊運(yùn)算嗎？這是我的(已經(jīng)優(yōu)化的)C+的NTT源代碼(它是完整的，100%工作在C+白化任何需要第三方庫，也應(yīng)該是線程安全的。請注意，源數(shù)組被用作臨時的！，它也不能將數(shù)組轉(zhuǎn)換為自身)。//---------------------------------------------------------------------------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);    }優(yōu)化后的一些度量(當(dāng)前代碼、較低的遞歸參數(shù)大小/計(jì)數(shù)以及更好的模塊化算法)：檢查NTTmul和NTTsqr時間(我的優(yōu)化使它加快了3倍多)。它只有1倍的循環(huán)，所以它不是很精確(誤差~10%)，但加速比即使現(xiàn)在也是明顯的(通常我會循環(huán)它1000倍或更多，但我的NTT太慢了)。你可以自由使用我的代碼.。只需保留我的Nick和/或鏈接到這個頁面的某個地方(rem in code，README.txt，約或諸如此類)。希望能幫上忙.。(我在任何地方都沒有看到用于快速NTT的C+源代碼，所以我不得不自己編寫它)。統(tǒng)一的根測試了所有接受的N，見fourier_NTT::init(DWORD n)功能。