Thanks so much, Leonardo!

Thanks to Henrik and Sam, also.

Hi Henrik,

You're probably using Mathematica for this. Would you care to post what does it output for just the forward transform of {0,1,2,3}?

Cheers!

Hi Nikolay,

when I do that using Mathematica I get:

But this result is not unique: See documentation on Fourier, in particular the infos under "Details and Options", c.f. FourierParameters.

Regards -- Henrik

Hi Nikolay,

sorry, I have no idea what is going wrong. But I have written a minimal recursive fft implementation - i guess this is what you are having in mind with your sketch?!? (just for demonstration purposes, functions can digest only lists of length 2^n, not optimized in any way!). But maybe this is helpful though:

ClearAll["Global`*"]

fourier[fl_List] := 
 Module[{length, eleOdd, eleEven, fouOdd, fouEven, phase},
  If[(length = Length[fl]) == 1, Return[Sow@fl]];
  {eleOdd, eleEven} = Transpose[Partition[fl, 2]];
  fouOdd = fourier[eleOdd];
  fouOdd = Flatten[{fouOdd, fouOdd}];
  fouEven = fourier[eleEven];
  fouEven = Flatten[{fouEven, fouEven}];
  phase = Table[Exp[-(2 Pi I) n/length], {n, 0, length - 1}];
  Sow[fouOdd + fouEven phase]
  ]

invfourier[fl_List] := 
 Module[{length, eleOdd, eleEven, fouOdd, fouEven, phase},
  If[(length = Length[fl]) == 1, Return[Sow@fl]];
  {eleOdd, eleEven} = Transpose[Partition[fl, 2]];
  fouOdd = invfourier[eleOdd];
  fouOdd = Flatten[{fouOdd, fouOdd}];
  fouEven = invfourier[eleEven];
  fouEven = Flatten[{fouEven, fouEven}];
  phase = Table[Exp[(2 Pi I) n/length], {n, 0, length - 1}];
  Sow[(fouOdd + fouEven phase)/2]
  ]

and then:

Regards -- Henrik

??? - But it does result in the original sequence:

Regards -- Henrik

EDIT: Sorry, I missed that you were talking about WolframAlpha ...