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）中的多项式乘法？

回答

相关问题