Axiom, 259, 193, 181, 179 bytes
L(g,n,f)==>[g for i in 1..n|f]
h(a)==(n:=#a;n=1=>a;c:=h(L(a.i,n,odd? i));d:=h(L(a.i,n,even? i));n:=n/2;t:=1>0;v:=L(d.i*%i^(-2*(i-1)/n),n,t);append(L(c.i+v.i,n,t),L(c.i-v.i,n,t)))
Even if h(a) could pass all the test and would be ok as entry for this 'competition'
one has to call h() or hlp() thru fft() below, for checking arguments.
I don't know if this software can be ok because i only had seen what other wrote, and search
the way it could run in Axiom for return some possible right result. Below ungolfed code with few comments:
-- L(g,n,f)==>[g for i in 1..n|f]
-- this macro L, build one List from other list, where in g, there is the generic element of index i
-- (as a.i, or a.i*b.i or a.i*4), n build 1..n that is the range of i, f is the condition
-- for insert the element in the list result.
hlp(a)==
n:=#a;n=1=>a
-- L(a.i,n,odd? i) it means build a list getting "even indices i of a.i as starting from index 0" [so even is odd and odd is even]
-- L(a.i,n,even? i) it means build a list getting "odd indices i of a.i as starting from index 0"
c:=hlp(L(a.i,n,odd? i));d:=hlp(L(a.i,n,even? i))
n:=n/2;t:=1>0
v:=L(d.i*%i^(-2*(i-1)/n),n,t)
append(L(c.i+v.i,n,t),L(c.i-v.i,n,t))
-- Return Fast Fourier transform of list a, in the case #a=2^n
fft(a)==(n:=#a;n=0 or gcd(n,2^30)~=n=>[];hlp(a))
(5) -> h([1,1,1,1])
(5) [4,0,0,0]
Type: List Expression Complex Integer
(6) -> h([1,2,3,4])
(6) [10,- 2 + 2%i,- 2,- 2 - 2%i]
Type: List Expression Complex Integer
(7) -> h([5.24626,3.90746,3.72335,5.74429,4.7983,8.34171,4.46785,0.760139])
(7)
[36.989359, - 6.2118552150 341603904 + 0.3556612739 187363298 %i,
1.85336 - 5.744741 %i, 7.1077752150 341603904 - 1.1333387260 812636702 %i,
- 0.517839, 7.1077752150 341603904 + 1.1333387260 812636702 %i,
1.85336 + 5.744741 %i,
- 6.2118552150 341603904 - 0.3556612739 187363298 %i]
Type: List Expression Complex Float
(8) -> h([%i+1,2,%i-2,9])
(8) [10 + 2%i,3 + 7%i,- 12 + 2%i,3 - 7%i]
Type: List Expression Complex Integer
in the few i had seen h() or fft() would return exact solution, but if the simplification
is not good as in:
(13) -> h([1,2,3,4,5,6,7,8])
(13)
+--+ +--+
(- 4 + 4%i)\|%i - 4 + 4%i (- 4 - 4%i)\|%i - 4 + 4%i
[36, --------------------------, - 4 + 4%i, --------------------------, - 4,
+--+ +--+
\|%i \|%i
+--+ +--+
(- 4 + 4%i)\|%i + 4 - 4%i (- 4 - 4%i)\|%i + 4 - 4%i
--------------------------, - 4 - 4%i, --------------------------]
+--+ +--+
\|%i \|%i
Type: List Expression Complex Integer
than it is enought change the type of only one element of list, as in below writing 8. (Float)
for find the approximate solution:
(14) -> h([1,2,3,4,5,6,7,8.])
(14)
[36.0, - 4.0000000000 000000001 + 9.6568542494 923801953 %i, - 4.0 + 4.0 %i,
- 4.0 + 1.6568542494 92380195 %i, - 4.0, - 4.0 - 1.6568542494 92380195 %i,
- 4.0 - 4.0 %i, - 4.0 - 9.6568542494 923801953 %i]
Type: List Expression Complex Float
I wrote it, seen all other answers because in the link, the page it was too much difficult so I don't know if this code can be right. I'm not one fft expert so all this can (it is probable) be wrong.
2Can you post some example inputs and outputs so we can test our implementations? – FUZxxl – 2015-03-08T11:57:49.393
2Title should have been "Fast and Fourier-s" (Fast and Furious). – clismique – 2016-11-14T07:32:04.717
3This is underspecified. At the very least you need to define the normalisation factors, and you also ought to be aware that any ambiguity will be wilfully misinterpreted. E.g. is "Implement" satisfied by the answer "
FFT
(3 chars): it's in the standard library"? Some test cases would be good too. – Peter Taylor – 2013-08-30T07:24:57.323Does it matter about the order of the output elements, i.e. do we need to implement bit reversed unscrambling or can we leave the output in scrambled order ? – Paul R – 2013-08-30T08:22:00.803
See the edits to the rules. The output should be a list/array with values ordered according to the indices in the standard DFT expression, referenced above. – jakevdp – 2013-08-30T16:05:51.787
Where are the tests cases? – RosLuP – 2017-08-11T21:00:51.120
Instead of point to the page fft O(n^2) why not point to the page fast Fourier transform with O(n*log_2(n)) – RosLuP – 2017-08-11T21:49:54.780
If the problem for fft is the speed why not use some other tag and not "codegolf" tag? I not had identified the problem where this fft is slow... Can someone give some input where this fft functions are slow? – RosLuP – 2017-08-13T21:07:47.630
VTC as no IO requirements mentioned. – user80551 – 2014-04-15T11:14:32.800