fast Fourier transforms (FFT)

Naive "school-book" implimentation.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27:

open System
open System.Numerics

let rec fft = function
  | []  -> []
  | [x] -> [x] 
  | x ->
    x
    |> List.mapi (fun i c -> i % 2 = 0, c)
    |> List.partition fst
    |> fun (even, odd) -> fft (List.map snd even), fft (List.map snd odd)
    ||> List.mapi2 (fun i even odd -> 
        let btf = odd * Complex.FromPolarCoordinates(1., -2. * Math.PI * (float i / float x.Length ))
        even + btf, even - btf)
    |> List.unzip
    ||> List.append
  
// use

let input = [for x in 0. .. 15. -> cos(x)  + cos(4.0 * x)]
    
let output = 
    input
    |> List.map (fun r -> Complex(r, 0.)) 
    |> fft
    |> List.map (fun c -> c.Real)

namespace System

namespace System.Numerics

val fft : _arg1:Complex list -> Complex list

Full name: Script.fft

val x : Complex

val x : Complex list

Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>

val mapi : mapping:(int -> 'T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.mapi

val i : int

val c : Complex

val partition : predicate:('T -> bool) -> list:'T list -> 'T list * 'T list

Full name: Microsoft.FSharp.Collections.List.partition

val fst : tuple:('T1 * 'T2) -> 'T1

Full name: Microsoft.FSharp.Core.Operators.fst

val even : (bool * Complex) list

val odd : (bool * Complex) list

val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map

val snd : tuple:('T1 * 'T2) -> 'T2

Full name: Microsoft.FSharp.Core.Operators.snd

val mapi2 : mapping:(int -> 'T1 -> 'T2 -> 'U) -> list1:'T1 list -> list2:'T2 list -> 'U list

Full name: Microsoft.FSharp.Collections.List.mapi2

val even : Complex

val odd : Complex

val btf : Complex

Multiple items
type Complex =
  struct
    new : real:float * imaginary:float -> Complex
    member Equals : obj:obj -> bool + 1 overload
    member GetHashCode : unit -> int
    member Imaginary : float
    member Magnitude : float
    member Phase : float
    member Real : float
    member ToString : unit -> string + 3 overloads
    static val Zero : Complex
    static val One : Complex
    ...
  end

Full name: System.Numerics.Complex

--------------------
Complex()
Complex(real: float, imaginary: float) : unit

Complex.FromPolarCoordinates(magnitude: float, phase: float) : Complex

type Math =
  static val PI : float
  static val E : float
  static member Abs : value:sbyte -> sbyte + 6 overloads
  static member Acos : d:float -> float
  static member Asin : d:float -> float
  static member Atan : d:float -> float
  static member Atan2 : y:float * x:float -> float
  static member BigMul : a:int * b:int -> int64
  static member Ceiling : d:decimal -> decimal + 1 overload
  static member Cos : d:float -> float
  ...

Full name: System.Math

field Math.PI = 3.14159265359

Multiple items
val float : value:'T -> float (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.float

--------------------
type float = Double

Full name: Microsoft.FSharp.Core.float

--------------------
type float<'Measure> = float

Full name: Microsoft.FSharp.Core.float<_>

property List.Length: int

val unzip : list:('T1 * 'T2) list -> 'T1 list * 'T2 list

Full name: Microsoft.FSharp.Collections.List.unzip

val append : list1:'T list -> list2:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.append

val input : float list

Full name: Script.input

val x : float

val cos : value:'T -> 'T (requires member Cos)

Full name: Microsoft.FSharp.Core.Operators.cos

val output : float list

Full name: Script.output

val r : float

property Complex.Real: float

Raw view Test code New version

More information

Link:	http://fssnip.net/dC
Posted:	12 years ago
Author:	Kaspar
Tags:	mathematics , algorithms