/* fft1024.c  complex data stored  re, im, re, im, re, ... im */

void fft1024(float Z[2048]) /* input data points and output  [0] to [2047] */
{
  static float W[2048];    /* scratch vector, used many times, */
  static float E[1026] =   /* constants for FFT algorithm */
   {1.0, 0.0, 0.999981, 0.00613589,
   0.999925, 0.0122715, 0.999831, 0.0184067,
   0.999699, 0.0245412, 0.999529, 0.0306748,
   0.999322, 0.0368072, 0.999078, 0.0429383,
   0.998796, 0.0490677, 0.998476, 0.0551952,
   0.998118, 0.0613207, 0.997723, 0.0674439,
   0.99729, 0.0735646, 0.99682, 0.0796824,
   0.996313, 0.0857973, 0.995768, 0.091909,
   0.995185, 0.0980171, 0.994565, 0.104122,
   0.993907, 0.110222, 0.993212, 0.116319,
   0.99248, 0.122411, 0.99171, 0.128498,
   0.990903, 0.134581, 0.990058, 0.140658,
   0.989177, 0.14673, 0.988258, 0.152797,
   0.987302, 0.158858, 0.986308, 0.164913,
   0.985278, 0.170962, 0.98421, 0.177004,
   0.983106, 0.18304, 0.981964, 0.189069,
   0.980785, 0.19509, 0.97957, 0.201105,
   0.978318, 0.207111, 0.977028, 0.21311,
   0.975702, 0.219101, 0.974339, 0.225084,
   0.97294, 0.231058, 0.971504, 0.237024,
   0.970031, 0.24298, 0.968522, 0.248928,
   0.966977, 0.254866, 0.965395, 0.260794,
   0.963776, 0.266713, 0.962121, 0.272621,
   0.960431, 0.27852, 0.958704, 0.284408,
   0.95694, 0.290285, 0.955141, 0.296151,
   0.953306, 0.302006, 0.951435, 0.30785,
   0.949528, 0.313682, 0.947586, 0.319502,
   0.945607, 0.32531, 0.943594, 0.331106,
   0.941544, 0.33689, 0.939459, 0.342661,
   0.937339, 0.348419, 0.935184, 0.354164,
   0.932993, 0.359895, 0.930767, 0.365613,
   0.928506, 0.371317, 0.92621, 0.377007,
   0.92388, 0.382683, 0.921514, 0.388345,
   0.919114, 0.393992, 0.916679, 0.399624,
   0.91421, 0.405241, 0.911706, 0.410843,
   0.909168, 0.41643, 0.906596, 0.422,
   0.903989, 0.427555, 0.901349, 0.433094,
   0.898675, 0.438616, 0.895966, 0.444122,
   0.893224, 0.449611, 0.890449, 0.455084,
   0.88764, 0.460539, 0.884797, 0.465977,
   0.881921, 0.471397, 0.879012, 0.476799,
   0.87607, 0.482184, 0.873095, 0.48755,
   0.870087, 0.492898, 0.867046, 0.498228,
   0.863973, 0.503538, 0.860867, 0.50883,
   0.857729, 0.514103, 0.854558, 0.519356,
   0.851355, 0.52459, 0.84812, 0.529804,
   0.844854, 0.534998, 0.841555, 0.540172,
   0.838225, 0.545325, 0.834863, 0.550458,
   0.83147, 0.55557, 0.828045, 0.560662,
   0.824589, 0.565732, 0.821103, 0.570781,
   0.817585, 0.575808, 0.814036, 0.580814,
   0.810457, 0.585798, 0.806848, 0.59076,
   0.803208, 0.595699, 0.799537, 0.600617,
   0.795837, 0.605511, 0.792107, 0.610383,
   0.788346, 0.615232, 0.784557, 0.620057,
   0.780737, 0.62486, 0.776888, 0.629638,
   0.77301, 0.634393, 0.769103, 0.639125,
   0.765167, 0.643832, 0.761202, 0.648514,
   0.757209, 0.653173, 0.753187, 0.657807,
   0.749136, 0.662416, 0.745058, 0.667,
   0.740951, 0.671559, 0.736817, 0.676093,
   0.732654, 0.680601, 0.728464, 0.685084,
   0.724247, 0.689541, 0.720003, 0.693971,
   0.715731, 0.698376, 0.711432, 0.702755,
   0.707107, 0.707107, 0.702755, 0.711432,
   0.698376, 0.715731, 0.693971, 0.720003,
   0.689541, 0.724247, 0.685084, 0.728464,
   0.680601, 0.732654, 0.676093, 0.736817,
   0.671559, 0.740951, 0.667, 0.745058,
   0.662416, 0.749136, 0.657807, 0.753187,
   0.653173, 0.757209, 0.648514, 0.761202,
   0.643832, 0.765167, 0.639125, 0.769103,
   0.634393, 0.77301, 0.629638, 0.776888,
   0.62486, 0.780737, 0.620057, 0.784557,
   0.615232, 0.788346, 0.610383, 0.792107,
   0.605511, 0.795837, 0.600617, 0.799537,
   0.595699, 0.803208, 0.59076, 0.806848,
   0.585798, 0.810457, 0.580814, 0.814036,
   0.575808, 0.817585, 0.570781, 0.821103,
   0.565732, 0.824589, 0.560662, 0.828045,
   0.55557, 0.83147, 0.550458, 0.834863,
   0.545325, 0.838225, 0.540172, 0.841555,
   0.534998, 0.844854, 0.529804, 0.84812,
   0.52459, 0.851355, 0.519356, 0.854558,
   0.514103, 0.857729, 0.50883, 0.860867,
   0.503538, 0.863973, 0.498228, 0.867046,
   0.492898, 0.870087, 0.48755, 0.873095,
   0.482184, 0.87607, 0.476799, 0.879012,
   0.471397, 0.881921, 0.465977, 0.884797,
   0.460539, 0.88764, 0.455084, 0.890449,
   0.449611, 0.893224, 0.444122, 0.895966,
   0.438616, 0.898675, 0.433094, 0.901349,
   0.427555, 0.903989, 0.422, 0.906596,
   0.41643, 0.909168, 0.410843, 0.911706,
   0.405241, 0.91421, 0.399624, 0.916679,
   0.393992, 0.919114, 0.388345, 0.921514,
   0.382683, 0.92388, 0.377007, 0.92621,
   0.371317, 0.928506, 0.365613, 0.930767,
   0.359895, 0.932993, 0.354164, 0.935184,
   0.348419, 0.937339, 0.342661, 0.939459,
   0.33689, 0.941544, 0.331106, 0.943594,
   0.32531, 0.945607, 0.319502, 0.947586,
   0.313682, 0.949528, 0.30785, 0.951435,
   0.302006, 0.953306, 0.296151, 0.955141,
   0.290285, 0.95694, 0.284408, 0.958704,
   0.27852, 0.960431, 0.272621, 0.962121,
   0.266713, 0.963776, 0.260794, 0.965395,
   0.254866, 0.966977, 0.248928, 0.968522,
   0.24298, 0.970031, 0.237024, 0.971504,
   0.231058, 0.97294, 0.225084, 0.974339,
   0.219101, 0.975702, 0.21311, 0.977028,
   0.207111, 0.978318, 0.201105, 0.97957,
   0.19509, 0.980785, 0.189069, 0.981964,
   0.18304, 0.983106, 0.177004, 0.98421,
   0.170962, 0.985278, 0.164913, 0.986308,
   0.158858, 0.987302, 0.152797, 0.988258,
   0.14673, 0.989177, 0.140658, 0.990058,
   0.134581, 0.990903, 0.128498, 0.99171,
   0.122411, 0.99248, 0.116319, 0.993212,
   0.110222, 0.993907, 0.104122, 0.994565,
   0.0980171, 0.995185, 0.091909, 0.995768,
   0.0857973, 0.996313, 0.0796824, 0.99682,
   0.0735646, 0.99729, 0.0674439, 0.997723,
   0.0613207, 0.998118, 0.0551952, 0.998476,
   0.0490677, 0.998796, 0.0429383, 0.999078,
   0.0368072, 0.999322, 0.0306748, 0.999529,
   0.0245412, 0.999699, 0.0184067, 0.999831,
   0.0122715, 0.999925, 0.00613589, 0.999981,
   0.0, 1.0, -0.00613589, 0.999981,
   -0.0122715, 0.999925, -0.0184067, 0.999831,
   -0.0245412, 0.999699, -0.0306748, 0.999529,
   -0.0368072, 0.999322, -0.0429383, 0.999078,
   -0.0490677, 0.998796, -0.0551952, 0.998476,
   -0.0613207, 0.998118, -0.0674439, 0.997723,
   -0.0735646, 0.99729, -0.0796824, 0.99682,
   -0.0857973, 0.996313, -0.091909, 0.995768,
   -0.0980171, 0.995185, -0.104122, 0.994565,
   -0.110222, 0.993907, -0.116319, 0.993212,
   -0.122411, 0.99248, -0.128498, 0.99171,
   -0.134581, 0.990903, -0.140658, 0.990058,
   -0.14673, 0.989177, -0.152797, 0.988258,
   -0.158858, 0.987302, -0.164913, 0.986308,
   -0.170962, 0.985278, -0.177004, 0.98421,
   -0.18304, 0.983106, -0.189069, 0.981964,
   -0.19509, 0.980785, -0.201105, 0.97957,
   -0.207111, 0.978318, -0.21311, 0.977028,
   -0.219101, 0.975702, -0.225084, 0.974339,
   -0.231058, 0.97294, -0.237024, 0.971504,
   -0.24298, 0.970031, -0.248928, 0.968522,
   -0.254866, 0.966977, -0.260794, 0.965395,
   -0.266713, 0.963776, -0.272621, 0.962121,
   -0.27852, 0.960431, -0.284408, 0.958704,
   -0.290285, 0.95694, -0.296151, 0.955141,
   -0.302006, 0.953306, -0.30785, 0.951435,
   -0.313682, 0.949528, -0.319502, 0.947586,
   -0.32531, 0.945607, -0.331106, 0.943594,
   -0.33689, 0.941544, -0.342661, 0.939459,
   -0.348419, 0.937339, -0.354164, 0.935184,
   -0.359895, 0.932993, -0.365613, 0.930767,
   -0.371317, 0.928506, -0.377007, 0.92621,
   -0.382683, 0.92388, -0.388345, 0.921514,
   -0.393992, 0.919114, -0.399624, 0.916679,
   -0.405241, 0.91421, -0.410843, 0.911706,
   -0.41643, 0.909168, -0.422, 0.906596,
   -0.427555, 0.903989, -0.433094, 0.901349,
   -0.438616, 0.898675, -0.444122, 0.895966,
   -0.449611, 0.893224, -0.455084, 0.890449,
   -0.460539, 0.88764, -0.465977, 0.884797,
   -0.471397, 0.881921, -0.476799, 0.879012,
   -0.482184, 0.87607, -0.48755, 0.873095,
   -0.492898, 0.870087, -0.498228, 0.867046,
   -0.503538, 0.863973, -0.50883, 0.860867,
   -0.514103, 0.857729, -0.519356, 0.854558,
   -0.52459, 0.851355, -0.529804, 0.84812,
   -0.534998, 0.844854, -0.540172, 0.841555,
   -0.545325, 0.838225, -0.550458, 0.834863,
   -0.55557, 0.83147, -0.560662, 0.828045,
   -0.565732, 0.824589, -0.570781, 0.821103,
   -0.575808, 0.817585, -0.580814, 0.814036,
   -0.585798, 0.810457, -0.59076, 0.806848,
   -0.595699, 0.803208, -0.600617, 0.799537,
   -0.605511, 0.795837, -0.610383, 0.792107,
   -0.615232, 0.788346, -0.620057, 0.784557,
   -0.62486, 0.780737, -0.629638, 0.776888,
   -0.634393, 0.77301, -0.639125, 0.769103,
   -0.643832, 0.765167, -0.648514, 0.761202,
   -0.653173, 0.757209, -0.657807, 0.753187,
   -0.662416, 0.749136, -0.667, 0.745058,
   -0.671559, 0.740951, -0.676093, 0.736817,
   -0.680601, 0.732654, -0.685084, 0.728464,
   -0.689541, 0.724247, -0.693971, 0.720003,
   -0.698376, 0.715731, -0.702755, 0.711432,
   -0.707107, 0.707107, -0.711432, 0.702755,
   -0.715731, 0.698376, -0.720003, 0.693971,
   -0.724247, 0.689541, -0.728464, 0.685084,
   -0.732654, 0.680601, -0.736817, 0.676093,
   -0.740951, 0.671559, -0.745058, 0.667,
   -0.749136, 0.662416, -0.753187, 0.657807,
   -0.757209, 0.653173, -0.761202, 0.648514,
   -0.765167, 0.643832, -0.769103, 0.639125,
   -0.77301, 0.634393, -0.776888, 0.629638,
   -0.780737, 0.62486, -0.784557, 0.620057,
   -0.788346, 0.615232, -0.792107, 0.610383,
   -0.795837, 0.605511, -0.799537, 0.600617,
   -0.803208, 0.595699, -0.806848, 0.59076,
   -0.810457, 0.585798, -0.814036, 0.580814,
   -0.817585, 0.575808, -0.821103, 0.570781,
   -0.824589, 0.565732, -0.828045, 0.560662,
   -0.83147, 0.55557, -0.834863, 0.550458,
   -0.838225, 0.545325, -0.841555, 0.540172,
   -0.844854, 0.534998, -0.84812, 0.529804,
   -0.851355, 0.52459, -0.854558, 0.519356,
   -0.857729, 0.514103, -0.860867, 0.50883,
   -0.863973, 0.503538, -0.867046, 0.498228,
   -0.870087, 0.492898, -0.873095, 0.48755,
   -0.87607, 0.482184, -0.879012, 0.476799,
   -0.881921, 0.471397, -0.884797, 0.465977,
   -0.88764, 0.460539, -0.890449, 0.455084,
   -0.893224, 0.449611, -0.895966, 0.444122,
   -0.898675, 0.438616, -0.901349, 0.433094,
   -0.903989, 0.427555, -0.906596, 0.422,
   -0.909168, 0.41643, -0.911706, 0.410843,
   -0.91421, 0.405241, -0.916679, 0.399624,
   -0.919114, 0.393992, -0.921514, 0.388345,
   -0.92388, 0.382683, -0.92621, 0.377007,
   -0.928506, 0.371317, -0.930767, 0.365613,
   -0.932993, 0.359895, -0.935184, 0.354164,
   -0.937339, 0.348419, -0.939459, 0.342661,
   -0.941544, 0.33689, -0.943594, 0.331106,
   -0.945607, 0.32531, -0.947586, 0.319502,
   -0.949528, 0.313682, -0.951435, 0.30785,
   -0.953306, 0.302006, -0.955141, 0.296151,
   -0.95694, 0.290285, -0.958704, 0.284408,
   -0.960431, 0.27852, -0.962121, 0.272621,
   -0.963776, 0.266713, -0.965395, 0.260794,
   -0.966977, 0.254866, -0.968522, 0.248928,
   -0.970031, 0.24298, -0.971504, 0.237024,
   -0.97294, 0.231058, -0.974339, 0.225084,
   -0.975702, 0.219101, -0.977028, 0.21311,
   -0.978318, 0.207111, -0.97957, 0.201105,
   -0.980785, 0.19509, -0.981964, 0.189069,
   -0.983106, 0.18304, -0.98421, 0.177004,
   -0.985278, 0.170962, -0.986308, 0.164913,
   -0.987302, 0.158858, -0.988258, 0.152797,
   -0.989177, 0.14673, -0.990058, 0.140658,
   -0.990903, 0.134581, -0.99171, 0.128498,
   -0.99248, 0.122411, -0.993212, 0.116319,
   -0.993907, 0.110222, -0.994565, 0.104122,
   -0.995185, 0.0980171, -0.995768, 0.091909,
   -0.996313, 0.0857973, -0.99682, 0.0796824,
   -0.99729, 0.0735646, -0.997723, 0.0674439,
   -0.998118, 0.0613207, -0.998476, 0.0551952,
   -0.998796, 0.0490677, -0.999078, 0.0429383,
   -0.999322, 0.0368072, -0.999529, 0.0306748,
   -0.999699, 0.0245412, -0.999831, 0.0184067,
   -0.999925, 0.0122715, -0.999981, 0.00613589,
    -1.0, 0.0};
  float Tre, Tim;
  int i, j, k, l, m;

   m = 512;
   l = 1;
   while(1)
   { 
      k = 0;
      j = l;
      i = 0;
      while(1)
      { 
         while(1)
	 {
	   /* W[i+k] = Z[i] + Z[m+i]; complex */
           W[2*(i+k)]   = Z[2*i]   + Z[2*(m+i)];
           W[2*(i+k)+1] = Z[2*i+1] + Z[2*(m+i)+1];

           /* W[i+j] = E[k] * (Z[i] - Z[m+i]); complex */
           Tre = Z[2*i]   - Z[2*(m+i)];
           Tim = Z[2*i+1] - Z[2*(m+i)+1];
           W[2*(i+j)]   = E[2*k] * Tre - E[2*k+1] * Tim;
           W[2*(i+j)+1] = E[2*k] * Tim + E[2*k+1] * Tre; 
           i++;
           if(i >= j) break;
	 }
         k = j;
         j = k+l;
         if(j > m) break;
      }
      l = l+l;
                  /* work back other way without copying */
      k = 0;
      j = l;
      i = 0;
      while(1)
      {
        while(1)
	{
          /* Z[i+k] = W[i] + W[m+i]; complex */
          Z[2*(i+k)]   = W[2*i]   + W[2*(m+i)];
          Z[2*(i+k)+1] = W[2*i+1] + W[2*(m+i)+1];

          /* Z[i+j] = E[k] * (W[i] - W[m+i]); complex */
          Tre = W[2*i]   - W[2*(m+i)];
          Tim = W[2*i+1] - W[2*(m+i)+1];
          Z[2*(i+j)]   = E[2*k] * Tre - E[2*k+1] * Tim;
          Z[2*(i+j)+1] = E[2*k] * Tim + E[2*k+1] * Tre;
          i++;
          if(i >= j) break;
	}
        k = j;
        j = k+l;
        if(j > m) break;
      }
      l = l+l;
      if(l > m) break; // result is in Z
   }
} /* end fft1024 */