M2（R）中的多項式乘法？

我試圖在M2（R）中實現基於FFT的乘法算法。基本上是一種算法，它將輸入的兩個元素作爲矩陣給出元素，並構建乘積多項式。但是，即使該算法應該起作用，因爲它看起來與我之前在常規編號上編寫的版本完全相同，但它沒有。係數總是偏離一點。M2（R）中的多項式乘法？

我還沒有在M2（C）中找到關於統一根的文章，但我發現（在紙上）選擇eps =（（cos（2PI/n），i sin（2PI/n）），（i sin（2PI/n），cos（2PI/n））），我得到一個很好的循環。

我的方法有什麼問題嗎？

下面是代碼：

struct FFT { 

    PolyC To, Aux[17][2], Res[17][2], AC, BC, ResC, ResD, ArgA, ArgB; 

    void fft(PolyC V, var depth, var n, PolyC To, MatC step) { 
     if(n == 1) { 
      To[0] = V[0]; 
     } else { 

      MatC eps = matCHelper.I2; 

      //We "split" the poly in 2 
      for(var i=0; i<n; i++) 
       Aux[depth+1][i&1][i>>1] = V[i]; 

      //We recursively apply FFT to the components 
      fft(Aux[depth+1][0], depth+1, n/2, Res[depth+1][0], step*step); 
      fft(Aux[depth+1][1], depth+1, n/2, Res[depth+1][1], step*step); 

      //We compute the result for the n roots 
      for(var i=0; i<n/2; i++) { 
       To[i] = Res[depth+1][0][i] + eps * Res[depth+1][1][i]; 
       To[n/2+i] = Res[depth+1][0][i] - eps * Res[depth+1][1][i]; 
       eps = eps * step; 
      } 
     } 
    } 

    void FFTMultiply(Poly Res, Poly A, Poly B, var n1, var n2) { 

     var M; 
     for(M = 1; M <= 2*n1 || M <= 2*n2; M <<= 1); 

     for(var i=0; i<n1; i++) ArgA[i] = A[i]; 
     for(var i=n1; i<M; i++) ArgA[i] = matCHelper.O2; 

     for(var i=0; i<n2; i++) ArgB[i] = B[i]; 
     for(var i=n2; i<M; i++) ArgB[i] = matCHelper.O2; 

     MatC step(Complex(cos(2*PI/M), 0) , Complex(0, sin(2*PI/M)), 
        Complex(0, sin(2*PI/M)) , Complex(cos(2*PI/M), 0)); 

     fft(ArgA, 0, M, AC, step); 
     fft(ArgB, 0, M, BC, step); 

     for(var i=0; i<M; i++) { 
      RezC[i] = AC[i] * BC[i]; 
     } 

     step.b = -step.b; 
     step.c = -step.c; 

     fft(RezC, 0, M, RezD, step); 

     for(var i=0; i<M; i++) { 
      // Now I divided everything by M and copied every element of ResD to Res modulo some number 
     } 
    } 
};

來源

2015-06-10 lbicsi

DFFT使用[NTT]（http://stackoverflow.com/q/18577076/2521214），如果可以它具有相同的屬性，但所有的計算都是整數（可以使用固定如果動態範圍不是太高，則指向浮點數），如果不能使用NTT，請嘗試使用更高精度的變量。這實際上不是我的專業領域，所以要以偏見來處理我的評論（相反，請將其視爲提示） – Spektre

你不能指望這個方法，如果你的係數矩陣不與你的矩陣step通勤工作。要使其正確工作，請使用對應於乘以標量exp(i*2*PI/M)的對角矩陣。

來源

2015-06-12 16:17:34 LutzL

M2（R）中的多項式乘法？

回答

相關問題