cfft.cpp

The Spectral Toolkit is a C++ spectral transform library written by Rodney James and Chuck Panaccion

	  t1.re = w1.re*x1[i].re-w1.im*x1[i].im;
	  t1.im = w1.re*x1[i].im+w1.im*x1[i].re;
	  t2.re = w2.re*x2[i].re-w2.im*x2[i].im;
	  t2.im = w2.re*x2[i].im+w2.im*x2[i].re;
	  t3.re = w3.re*x3[i].re-w3.im*x3[i].im;
	  t3.im = w3.re*x3[i].im+w3.im*x3[i].re;
	  t4.re = w4.re*x4[i].re-w4.im*x4[i].im;
	  t4.im = w4.re*x4[i].im+w4.im*x4[i].re;
	  t5.re = w5.re*x5[i].re-w5.im*x5[i].im;
	  t5.im = w5.re*x5[i].im+w5.im*x5[i].re;
	  s0.re=t0.re+t3.re;
	  s0.im=t0.im+t3.im;
	  s1.re=t0.re-t3.re;
	  s1.im=t0.im-t3.im;
	  s2.re=t1.re+t2.re+t4.re+t5.re;
	  s2.im=t1.im+t2.im+t4.im+t5.im;
	  s3.re=t1.re-t2.re-t4.re+t5.re;
	  s3.im=t1.im-t2.im-t4.im+t5.im;
	  s4.re=t1.re+t2.re-t4.re-t5.re;
	  s4.im=t1.im+t2.im-t4.im-t5.im;
	  s5.re=t1.re-t2.re+t4.re-t5.re;
	  s5.im=t1.im-t2.im+t4.im-t5.im;
	  t0.re=s0.re+s2.re;
	  t0.im=s0.im+s2.im;
	  t1.re=s1.re+a*s3.re;
	  t1.im=s1.im+a*s3.im;
	  t2.re=s0.re-a*s2.re;
	  t2.im=s0.im-a*s2.im;
	  t3.re=s1.re-s3.re;
	  t3.im=s1.im-s3.im;
	  t4.re=b*s4.re;
	  t4.im=b*s4.im;
	  t5.re=b*s5.re;
	  t5.im=b*s5.im;
	  y0[i].re=t0.re;
	  y0[i].im=t0.im;
	  y1[i].re=t1.re+t4.im;
	  y1[i].im=t1.im-t4.re;
	  y2[i].re=t2.re+t5.im;
	  y2[i].im=t2.im-t5.re;
	  y3[i].re=t3.re;
	  y3[i].im=t3.im;
	  y4[i].re=t2.re-t5.im;
	  y4[i].im=t2.im+t5.re;
	  y5[i].re=t1.re-t4.im;
	  y5[i].im=t1.im+t4.re;
	  t1.re=omega.re*w1.re+w1.im*omega.im+w1.re;
	  t1.im=omega.re*w1.im-w1.re*omega.im+w1.im;
	  w1.re=t1.re;
	  w1.im=t1.im;
        }
    }
}  

/// Internal radix-8 butterfly forward transform.
/// \param x input array
/// \param y output array
/// \param L accumulation product of previous factors
/// \param N remaining sequence length from node down

void cfft::node::analysis_radix8(complex *x,complex *y,int L,int N)
{
  complex w1,w2,w3,w4,w5,w6,w7;
  complex s0,s1,s2,s3,s4,s5,s6,s7;
  complex t0,t1,t2,t3,t4,t5,t6,t7;
  complex *x0,*x1,*x2,*x3,*x4,*x5,*x6,*x7;
  complex *y0,*y1,*y2,*y3,*y4,*y5,*y6,*y7;
  const real c=0.5L*root2;
    
  int j,i;
  for(j=0;j<N;j++)
    { 
      x0=x+j*L;
      x1=x0+L*N;
      x2=x1+L*N;
      x3=x2+L*N;
      x4=x3+L*N;
      x5=x4+L*N;
      x6=x5+L*N;
      x7=x6+L*N;
      y0=y+8*L*j;
      y1=y0+L;
      y2=y1+L;
      y3=y2+L;
      y4=y3+L;
      y5=y4+L;
      y6=y5+L;
      y7=y6+L;
      t0.re=x0[0].re;
      t0.im=x0[0].im;
      t1.re=x1[0].re;
      t1.im=x1[0].im;
      t2.re=x2[0].re;
      t2.im=x2[0].im;
      t3.re=x3[0].re;
      t3.im=x3[0].im;
      t4.re=x4[0].re;
      t4.im=x4[0].im;
      t5.re=x5[0].re;
      t5.im=x5[0].im;
      t6.re=x6[0].re;
      t6.im=x6[0].im;
      t7.re=x7[0].re;
      t7.im=x7[0].im;
      s0.re=t0.re-t4.re;
      s0.im=t0.im-t4.im;
      s1.re=t1.re-t5.re;
      s1.im=t1.im-t5.im;
      s2.re=t2.re-t6.re;
      s2.im=t2.im-t6.im;
      s3.re=t3.re-t7.re;
      s3.im=t3.im-t7.im;
      s4.re=t0.re+t4.re;
      s4.im=t0.im+t4.im;
      s5.re=t1.re+t5.re;
      s5.im=t1.im+t5.im;
      s6.re=t2.re+t6.re;
      s6.im=t2.im+t6.im;
      s7.re=t3.re+t7.re;
      s7.im=t3.im+t7.im;
      t0.re=s4.re+s6.re;
      t0.im=s4.im+s6.im;
      t1.re=s5.re+s7.re;
      t1.im=s5.im+s7.im;
      t2.re=s4.re-s6.re;
      t2.im=s4.im-s6.im;
      t3.re=s5.re-s7.re;
      t3.im=s5.im-s7.im;
      t4.re=s0.re+s2.im;
      t4.im=s0.im+s2.re;
      t5.re=c*(s1.re-s3.re);
      t5.im=c*(s1.im-s3.im);
      t6.re=s0.re-s2.im;
      t6.im=s0.im-s2.re;
      t7.re=c*(s1.re+s3.re);
      t7.im=c*(s1.im+s3.im);
      y0[0].re=t0.re+t1.re;
      y0[0].im=t0.im+t1.im;
      y1[0].re=t4.re+t5.re+t7.im;
      y1[0].im=t6.im+t5.im-t7.re;
      y2[0].re=t2.re+t3.im;
      y2[0].im=t2.im-t3.re;
      y3[0].re=t6.re-t5.re+t7.im;
      y3[0].im=t4.im-t5.im-t7.re;
      y4[0].re=t0.re-t1.re;
      y4[0].im=t0.im-t1.im;
      y5[0].re=t4.re-t5.re-t7.im;
      y5[0].im=t6.im-t5.im+t7.re;
      y6[0].re=t2.re-t3.im;
      y6[0].im=t2.im+t3.re;
      y7[0].re=t6.re+t5.re-t7.im;
      y7[0].im=t4.im+t5.im+t7.re;
      w1.re=omega.re+1.0;
      w1.im=omega.im;
      for(i=1;i<L;i++)
        {
	  w2.re=w1.re*w1.re-w1.im*w1.im;
	  w2.im=2.0*w1.re*w1.im;
	  w3.re=w2.re*w1.re-w2.im*w1.im;
	  w3.im=w2.re*w1.im+w2.im*w1.re; 
	  w4.re=w3.re*w1.re-w3.im*w1.im;
	  w4.im=w3.re*w1.im+w3.im*w1.re; 
	  w5.re=w4.re*w1.re-w4.im*w1.im;
	  w5.im=w4.re*w1.im+w4.im*w1.re; 
	  w6.re=w5.re*w1.re-w5.im*w1.im;
	  w6.im=w5.re*w1.im+w5.im*w1.re; 
	  w7.re=w6.re*w1.re-w6.im*w1.im;
	  w7.im=w6.re*w1.im+w6.im*w1.re; 
	  s0.re=x0[i].re;
	  s0.im=x0[i].im;
	  s1.re=x1[i].re;
	  s1.im=x1[i].im;
	  s2.re=x2[i].re;
	  s2.im=x2[i].im;
	  s3.re=x3[i].re;
	  s3.im=x3[i].im;
	  s4.re=x4[i].re;
	  s4.im=x4[i].im;
	  s5.re=x5[i].re;
	  s5.im=x5[i].im;
	  s6.re=x6[i].re;
	  s6.im=x6[i].im;
	  s7.re=x7[i].re;
	  s7.im=x7[i].im;
	  t0.re=s0.re;
	  t0.im=s0.im;
	  t1.re=w1.re*s1.re-w1.im*s1.im;
	  t1.im=w1.re*s1.im+w1.im*s1.re;
	  t2.re=w2.re*s2.re-w2.im*s2.im;
	  t2.im=w2.re*s2.im+w2.im*s2.re;
	  t3.re=w3.re*s3.re-w3.im*s3.im;
	  t3.im=w3.re*s3.im+w3.im*s3.re;
	  t4.re=w4.re*s4.re-w4.im*s4.im;
	  t4.im=w4.re*s4.im+w4.im*s4.re;
	  t5.re=w5.re*s5.re-w5.im*s5.im;
	  t5.im=w5.re*s5.im+w5.im*s5.re;
	  t6.re=w6.re*s6.re-w6.im*s6.im;
	  t6.im=w6.re*s6.im+w6.im*s6.re;
	  t7.re=w7.re*s7.re-w7.im*s7.im;
	  t7.im=w7.re*s7.im+w7.im*s7.re;
	  s0.re=t0.re-t4.re;
	  s0.im=t0.im-t4.im;
	  s1.re=t1.re-t5.re;
	  s1.im=t1.im-t5.im;
	  s2.re=t2.re-t6.re;
	  s2.im=t2.im-t6.im;
	  s3.re=t3.re-t7.re;
	  s3.im=t3.im-t7.im;
	  s4.re=t0.re+t4.re;
	  s4.im=t0.im+t4.im;
	  s5.re=t1.re+t5.re;
	  s5.im=t1.im+t5.im;
	  s6.re=t2.re+t6.re;
	  s6.im=t2.im+t6.im;
	  s7.re=t3.re+t7.re;
	  s7.im=t3.im+t7.im;
	  t0.re=s4.re+s6.re;
	  t0.im=s4.im+s6.im;
	  t1.re=s5.re+s7.re;
	  t1.im=s5.im+s7.im;
	  t2.re=s4.re-s6.re;
	  t2.im=s4.im-s6.im;
	  t3.re=s5.re-s7.re;
	  t3.im=s5.im-s7.im;
	  t4.re=s0.re+s2.im;
	  t4.im=s0.im+s2.re;
	  t5.re=c*(s1.re-s3.re);
	  t5.im=c*(s1.im-s3.im);
	  t6.re=s0.re-s2.im;
	  t6.im=s0.im-s2.re;
	  t7.re=c*(s1.re+s3.re);
	  t7.im=c*(s1.im+s3.im);
	  y0[i].re=t0.re+t1.re;
	  y0[i].im=t0.im+t1.im;
	  y1[i].re=t4.re+t5.re+t7.im;
	  y1[i].im=t6.im+t5.im-t7.re;
	  y2[i].re=t2.re+t3.im;
	  y2[i].im=t2.im-t3.re;
	  y3[i].re=t6.re-t5.re+t7.im;
	  y3[i].im=t4.im-t5.im-t7.re;
	  y4[i].re=t0.re-t1.re;
	  y4[i].im=t0.im-t1.im;
	  y5[i].re=t4.re-t5.re-t7.im;
	  y5[i].im=t6.im-t5.im+t7.re;
	  y6[i].re=t2.re-t3.im;
	  y6[i].im=t2.im+t3.re;
	  y7[i].re=t6.re+t5.re-t7.im;
	  y7[i].im=t4.im+t5.im+t7.re;
	  t1.re=omega.re*w1.re-w1.im*omega.im+w1.re;
	  t1.im=omega.re*w1.im+w1.re*omega.im+w1.im;
	  w1.re=t1.re;
	  w1.im=t1.im;
        }
    }
}  

/// Internal radix-8 butterfly backward transform.
/// \param x input array
/// \param y output array
/// \param L accumulation product of previous factors
/// \param N remaining sequence length from node down

void cfft::node::synthesis_radix8(complex *x,complex *y,int L,int N)
{
  complex w1,w2,w3,w4,w5,w6,w7;
  complex s0,s1,s2,s3,s4,s5,s6,s7;
  complex t0,t1,t2,t3,t4,t5,t6,t7;
  complex *x0,*x1,*x2,*x3,*x4,*x5,*x6,*x7;
  complex *y0,*y1,*y2,*y3,*y4,*y5,*y6,*y7;
  const real c=0.5L*root2;
  int j,i;
    
  for(j=0;j<N;j++)
    { 
      x0=x+j*L;
      x1=x0+L*N;
      x2=x1+L*N;
      x3=x2+L*N;
      x4=x3+L*N;
      x5=x4+L*N;
      x6=x5+L*N;
      x7=x6+L*N;
      y0=y+8*L*j;
      y1=y0+L;
      y2=y1+L;
      y3=y2+L;
      y4=y3+L;
      y5=y4+L;
      y6=y5+L;
      y7=y6+L;
      t0.re=x0[0].re;
      t0.im=x0[0].im;
      t1.re=x1[0].re;
      t1.im=x1[0].im;
      t2.re=x2[0].re;
      t2.im=x2[0].im;
      t3.re=x3[0].re;
      t3.im=x3[0].im;
      t4.re=x4[0].re;
      t4.im=x4[0].im;
      t5.re=x5[0].re;
      t5.im=x5[0].im;
      t6.re=x6[0].re;
      t6.im=x6[0].im;
      t7.re=x7[0].re;
      t7.im=x7[0].im;
      s0.re=t0.re-t4.re;
      s0.im=t0.im-t4.im;
      s1.re=t1.re-t5.re;
      s1.im=t1.im-t5.im;
      s2.re=t2.re-t6.re;
      s2.im=t2.im-t6.im;
      s3.re=t3.re-t7.re;
      s3.im=t3.im-t7.im;
      s4.re=t0.re+t4.re;
      s4.im=t0.im+t4.im;
      s5.re=t1.re+t5.re;
      s5.im=t1.im+t5.im;
      s6.re=t2.re+t6.re;
      s6.im=t2.im+t6.im;
      s7.re=t3.re+t7.re;
      s7.im=t3.im+t7.im;
      t0.re=s4.re+s6.re;
      t0.im=s4.im+s6.im;
      t1.re=s5.re+s7.re;
      t1.im=s5.im+s7.im;
      t2.re=s4.re-s6.re;
      t2.im=s4.im-s6.im;
      t3.re=s5.re-s7.re;
      t3.im=s5.im-s7.im;
      t4.re=s0.re+s2.im;
      t4.im=s0.im+s2.re;
      t5.re=c*(s1.re-s3.re);
      t5.im=c*(s1.im-s3.im);
      t6.re=s0.re-s2.im;
      t6.im=s0.im-s2.re;
      t7.re=c*(s1.re+s3.re);
      t7.im=c*(s1.im+s3.im);
      y0[0].re=t0.re+t1.re;
      y0[0].im=t0.im+t1.im;
      y1[0].re=t6.re+t5.re-t7.im;
      y1[0].im=t4.im+t5.im+t7.re;
      y2[0].re=t2.re-t3.im;
      y2[0].im=t2.im+t3.re;
      y3[0].re=t4.re-t5.re-t7.im;
      y3[0].im=t6.im-t5.im+t7.re;
      y4[0].re=t0.re-t1.re;
      y4[0].im=t0.im-t1.im;
      y5[0].re=t6.re-t5.re+t7.im;
      y5[0].im=t4.im-t5.im-t7.re;
      y6[0].re=t2.re+t3.im;
      y6[0].im=t2.im-t3.re;
      y7[0].re=t4.re+t5.re+t7.im;
      y7[0].im=t6.im+t5.im-t7.re;
      w1.re=omega.re+1.0;
      w1.im=-omega.im;
      for(i=1;i<L;i++)
        {
	  w2.re=w1.re*w1.re-w1.im*w1.im;
	  w2.im=2.0*w1.re*w1.im;
	  w3.re=w2.re*w1.re-w2.im*w1.im;
	  w3.im=w2.re*w1.im+w2.im*w1.re;
	  w4.re=w3.re*w1.re-w3.im*w1.im;
	  w4.im=w3.re*w1.im+w3.im*w1.re; 
	  w5.re=w4.re*w1.re-w4.im*w1.im;
	  w5.im=w4.re*w1.im+w4.im*w1.re; 
	  w6.re=w5.re*w1.re-w5.im*w1.im;
	  w6.im=w5.re*w1.im+w5.im*w1.re; 
	  w7.re=w6.re*w1.re-w6.im*w1.im;
	  w7.im=w6.re*w1.im+w6.im*w1.re; 
	  s0.re=x0[i].re;
	  s0.im=x0[i].im;
	  s1.re=x1[i].re;
	  s1.im=x1[i].im;
	  s2.re=x2[i].re;
	  s2.im=x2[i].im;
	  s3.re=x3[i].re;
	  s3.im=x3[i].im;
	  s4.re=x4[i].re;
	  s4.im=x4[i].im;
	  s5.re=x5[i].re;
	  s5.im=x5[i].im;
	  s6.re=x6[i].re;
	  s6.im=x6[i].im;
	  s7.re=x7[i].re;
	  s7.im=x7[i].im;
	  t0.re=s0.re;
	  t0.im=s0.im;
	  t1.re=w1.re*s1.re-w1.im*s1.im;
	  t1.im=w1.re*s1.im+w1.im*s1.re;
	  t2.re=w2.re*s2.re-w2.im*s2.im;
	  t2.im=w2.re*s2.im+w2.im*s2.re;
	  t3.re=w3.re*s3.re-w3.im*s3.im;
	  t3.im=w3.re*s3.im+w3.im*s3.re;
	  t4.re=w4.re*s4.re-w4.im*s4.im;
	  t4.im=w4.re*s4.im+w4.im*s4.re;
	  t5.re=w5.re*s5.re-w5.im*s5.im;
	  t5.im=w5.re*s5.im+w5.im*s5.re;
	  t6.re=w6.re*s6.re-w6.im*s6.im;
	  t6.im=w6.re*s6.im+w6.im*s6.re;
	  t7.re=w7.re*s7.re-w7.im*s7.im;
	  t7.im=w7.re*s7.im+w7.im*s7.re;
	  s0.re=t0.re-t4.re;
	  s0.im=t0.im-t4.im;
	  s1.re=t1.re-t5.re;
	  s1.im=t1.im-t5.im;
	  s2.re=t2.re-t6.re;
	  s2.im=t2.im-t6.im;
	  s3.re=t3.re-t7.re;
	  s3.im=t3.im-t7.im;
	  s4.re=t0.re+t4.re;
	  s4.im=t0.im+t4.im;
	  s5.re=t1.re+t5.re;
	  s5.im=t1.im+t5.im;
	  s6.re=t2.re+t6.re;
	  s6.im=t2.im+t6.im;
	  s7.re=t3.re+t7.re;
	  s7.im=t3.im+t7.im;
	  t0.re=s4.re+s6.re;
	  t0.im=s4.im+s6.im;
	  t1.re=s5.re+s7.re;
	  t1.im=s5.im+s7.im;
	  t2.re=s4.re-s6.re;
	  t2.im=s4.im-s6.im;
	  t3.re=s5.re-s7.re;
	  t3.im=s5.im-s7.im;
	  t4.re=s0.re+s2.im;
	  t4.im=s0.im+s2.re;
	  t5.re=c*(s1.re-s3.re);
	  t5.im=c*(s1.im-s3.im);
	  t6.re=s0.re-s2.im;
	  t6.im=s0.im-s2.re;
	  t7.re=c*(s1.re+s3.re);
	  t7.im=c*(s1.im+s3.im);
	  y0[i].re=t0.re+t1.re;
	  y0[i].im=t0.im+t1.im;
	  y1[i].re=t6.re+t5.re-t7.im;
	  y1[i].im=t4.im+t5.im+t7.re;
	  y2[i].re=t2.re-t3.im;
	  y2[i].im=t2.im+t3.re;
	  y3[i].re=t4.re-t5.re-t7.im;
	  y3[i].im=t6.im-t5.im+t7.re;
	  y4[i].re=t0.re-t1.re;
	  y4[i].im=t0.im-t1.im;
	  y5[i].re=t6.re-t5.re+t7.im;
	  y5[i].im=t4.im-t5.im-t7.re;
	  y6[i].re=t2.re+t3.im;
	  y6[i].im=t2.im-t3.re;
	  y7[i].re=t4.re+t5.re+t7.im;
	  y7[i].im=t6.im+t5.im-t7.re;
	  t1.re=omega.re*w1.re+w1.im*omega.im+w1.re;
	  t1.im=omega.re*w1.im-w1.re*omega.im+w1.im;
	  w1.re=t1.re;
	  w1.im=t1.im;
        }
    }
}

/// Internal general radix butterfly forward transform.
/// \param x input array
/// \param y output array
/// \param L accumulation product of previous factors
/// \param N remaining sequence length from node down

void cfft::node::analysis_radixg(complex *x,complex *y,int L,int N)
{
  complex w,z,a,b;
  int l,k,j,i;
    
  for(j=0;j<N;j++)
    {
      w.re=1.0;
      w.im=0.0;
      for(i=0;i<L;i++)
        {
	  z.re=1.0;
	  z.im=0.0;
	  for(k=0;k<r;k++)
            {
	      T[k].re=x[i+j*L+k*N*L].re*z.re-x[i+j*L+k*N*L].im*z.im;
	      T[k].im=x[i+j*L+k*N*L].im*z.re+x[i+j*L+k*N*L].re*z.im;
	      a.re=z.re*w.re-z.im*w.im;
	      a.im=z.re*w.im+z.im*w.re;
	      z.re=a.re;
	      z.im=a.im;
            } 
	  for(k=0;k<r;k++)
            {
	      z.re=z.im=0.0;
	      a.re=1.0;
	      a.im=0.0;
	      for(l=0;l<r;l++)
                {
		  z.re=z.re+T[l].re*a.re-T[l].im*a.im;
		  z.im=z.im+T[l].re*a.im+T[l].im*a.re;
		  b.re=a.re*R[k].re-a.im*R[k].im;
		  b.im=a.re*R[k].im+a.im*R[k].re;
		  a.re=b.re;
		  a.im=b.im;
                }
	      y[i+j*r*L+k*L].re=z.re;
	      y[i+j*r*L+k*L].im=z.im;
            }
	  z.re=omega.re*w.re-omega.im*w.im+w.re;
	  z.im=omega.re*w.im+omega.im*w.re+w.im; 
	  w.re=z.re;
	  w.im=z.im;
        }
    }
}

/// Internal general radix butterfly backward transform.
/// \param x input array
/// \param y output array
/// \param L accumulation product of previous factors
/// \param N remaining sequence length from node down

void cfft::node::synthesis_radixg(complex *x,complex *y,int L,int N)
{
  complex w,z,a,b;
  int l,k,j,i;
    
  for(j=0;j<N;j++)
    {
      w.re=1.0;
      w.im=0.0;
      for(i=0;i<L;i++)
        {
	  z.re=1.0;
	  z.im=0.0;
	  for(k=0;k<r;k++)
            {
	      T[k].re=x[i+j*L+k*N*L].re*z.re-x[i+j*L+k*N*L].im*z.im;
	      T[k].im=x[i+j*L+k*N*L].im*z.re+x[i+j*L+k*N*L].re*z.im;
	      a.re=z.re*w.re-z.im*w.im;
	      a.im=z.re*w.im+z.im*w.re;
	      z.re=a.re;
	      z.im=a.im;
            } 
	  for(k=0;k<r;k++)
            {
	      z.re=z.im=0.0;
	      a.re=1.0;
	      a.im=0.0;
	      for(l=0;l<r;l++)
                {
		  z.re=z.re+T[l].re*a.re+T[l].im*a.im;
		  z.im=z.im-T[l].re*a.im+T[l].im*a.re;
		  b.re=a.re*R[k].re-a.im*R[k].im;
		  b.im=a.re*R[k].im+a.im*R[k].re;
		  a.re=b.re;
		  a.im=b.im;
                }
	      y[i+j*r*L+k*L].re=z.re;
	      y[i+j*r*L+k*L].im=z.im;
            }
	  z.re=omega.re*w.re+omega.im*w.im+w.re;
	  z.im=omega.re*w.im-omega.im*w.re+w.im; 
	  w.re=z.re;
	  w.im=z.im;
        }
    }
}