Fast Fourier transform: Difference between revisions

{{task}}

=={{header|Ada}}==

 

generic

new Ada.Numerics.Generic_Complex_Arrays (<>);

function Generic_FFT (X : Complex_Vector) return Complex_Vector;

 

function Generic_FFT (X : Complex_Vector) return Complex_Vector is

function FFT (X : Complex_Vector; N, S : Positive)

return Complex_Vector is

return FFT (X, X'Length, 1);

end Generic_FFT;

with Ada.Numerics.Complex_Arrays; use Ada.Numerics.Complex_Arrays;

with Ada.Complex_Text_IO; use Ada.Complex_Text_IO;

with Ada.Text_IO; use Ada.Text_IO;

with Ada.Numerics.Complex_Elementary_Functions;

with Generic_FFT;

X : Complex_Vector := (1..4 => (1.0, 0.0), 5..8 => (0.0, 0.0));

Y : Complex_Vector := FFT (X);

New_Line;

end loop;

<pre>

X FFT X

( 0.000, 0.000) ( 1.000, 2.414)

</pre>

 

=={{header|C}}==

#include <math.h>

#include <complex.h>

cplx out[n];

for (int i = 0; i < n; i++) out[i] = buf[i];

_fft(buf, out, n, 1);

}

int main()

{

PI = atan2(1, 1) * 4;

cplx buf[] = {1, 1, 1, 1, 0, 0, 0, 0};

fft(buf, 8);

return 0;

 

=={{header|C++}}==

#include <iostream>

#include <valarray>

typedef std::valarray<Complex> CArray;

 

void fft(CArray& x)

{

for (size_t k = 0; k < N/2; ++k)

{

x[k ] = even[k] + t;

x[k+N/2] = even[k] - t;

}

}

 

CArray data(test, 8);

 

fft(data);

 

for (int i = 0; i < 8; ++i)

{

}

<pre>

(4,0)

(1,-2.41421)

(0,0)

(1,2.41421)

</pre>

 

=={{header|D}}==

 

}

 

void main() {

 

=={{header|GAP}}==

# In GAP, E(n) = exp(2*i*pi/n), a primitive root of the unity.

 

 

InverseFourier(last);

 

=={{header|Go}}==

 

import (

"fmt"

"math"

)

 

ditfft2(x[s:], y[n/2:], n/2, 2*s)

for k := 0; k < n/2; k++ {

y[k], y[k+n/2] = y[k]+tf, y[k]-tf

}

fmt.Printf("%8.4f\n", c)

}

<pre>

( 4.0000 +0.0000i)

( 0.0000 +0.0000i)

( 1.0000 +2.4142i)

</pre>

 

=={{header|J}}==

 

rou =: ^@j.@o.@(% #)@i.@-: NB. roots of unity

floop =: 4 : 'for_r. i.#$x do. (y=.{."1 y) ] x=.(+/x) ,&,:"r (-/x)*y end.'

 

Example:

 

 

 

 

Fourier[{1,1,1,1,0,0,0,0}, FourierParameters->{1,-1}]

 

 

=={{header|OCaml}}==

This is a simple implementation of the Cooley-Tukey pseudo-code

 

 

let merge l r n =

let z = List.rev (snd (List.fold_left f (0,[]) r)) in

 

let fft lst =

let rec ditfft2 a n s =

if n = 1 then [List.nth lst a] else

ditfft2 0 (List.length lst) 1;;

 

let indata = [one;one;one;one;zero;zero;zero;zero] in

show indata;

 

<pre>

(1.000000 0.000000) (1.000000 0.000000) (1.000000 0.000000) (1.000000 0.000000) (0.000000 0.000000) (0.000000 0.000000) (0.000000 0.000000) (0.000000 0.000000)

(4.000000 0.000000) (1.000000 -2.414214) (0.000000 0.000000) (1.000000 -0.414214) (0.000000 0.000000) (1.000000 0.414214) (0.000000 0.000000) (1.000000 2.414214)

</pre>

 

=={{header|PARI/GP}}==

Naive implementation, using the same testcase as Ada:

<pre>[4.0000000000000000000000000000000000000, 1.0000000000000000000000000000000000000 - 2.4142135623730950488016887242096980786*I, 0.E-37 + 0.E-38*I, 1.0000000000000000000000000000000000000 - 0.41421356237309504880168872420969807856*I, 0.E-38 + 0.E-37*I, 0.99999999999999999999999999999999999997 + 0.41421356237309504880168872420969807860*I, 4.701977403289150032 E-38 + 0.E-38*I, 0.99999999999999999999999999999999999991 + 2.4142135623730950488016887242096980785*I]</pre>

 

 

return @_ if @_ == 1;

}

 

 

 

 

=={{header|Python}}==

 

def fft(x):

even = fft(x[0::2])

odd = fft(x[1::2])

 

 

 

>>> from numpy import array

>>> print( ' '.join("%5.3f" % abs(f) for f in fft(a)) )

 

=={{header|R}}==

The function "fft" is readily available in R

<pre>4+0.000000i 1-2.414214i 0+0.000000i 1-0.414214i 0+0.000000i 1+0.414214i 0+0.000000i 1+2.414214i</pre>