-- fft1024.adb
with Ada.Numerics.Complex_Types; use Ada.Numerics.Complex_Types;
with Complex_Arrays; use Complex_Arrays;

procedure fft1024(Z : in out Complex_Vector) is --  (0..1023)
  pragma Suppress(All_Checks);
  W: Complex_Vector(0..1023);  -- scratch vector, used many times
  E: Complex_Vector(0..512) :=   -- 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));
  I, J, K, L, M : Integer;
begin

   M := 512;
   L := 1;
   loop
      K := 0;
      J := L;
      I := 0;
      loop
         loop
            W(I+K) := Z(I) + Z(M+I);
            W(I+J) := E(K) * (Z(I) - Z(M+I));
            I := I+1;
            if I >= J then exit; end if;
         end loop;
         K := J;
         J := K+L;
         if J > M then exit; end if;
      end loop;
      L := L+L;
                -- work back other way without copying
      K := 0;
      J := L;
      I := 0;
      loop
        loop
          Z(I+K) := W(I) + W(M+I);
          Z(I+J) := E(K) * (W(I) - W(M+I));
          I := I+1;
          if I >= J then exit; end if;
        end loop;
        K := J;
        J := K+L;
        if J > M then exit; end if;
      end loop;
      L := L+L;
      if L > M then return; end if;  -- result is in Z
   end loop;
end fft1024;