Safe Haskell	None
Language	Haskell2010

FFT

Description

Discrete Fourier transforms for polynomial interpolation

Synopsis

type CoeffVec f = [f]
dftNaive :: Num f => f -> CoeffVec f -> DFT f
fft :: GaloisField k => (Int -> k) -> CoeffVec k -> DFT k
fftMult :: GaloisField k => (Int -> k) -> CoeffVec k -> CoeffVec k -> CoeffVec k
fftTargetPoly :: GaloisField k => (Int -> k) -> Int -> VPoly k
interpolate :: GaloisField k => (Int -> k) -> [k] -> VPoly k
inverseDft :: GaloisField k => (Int -> k) -> DFT k -> CoeffVec k

Documentation

Polynomial represented as a coefficient vector, little-endian

Arguments

:: Num f
=> f	principal 2^k-th root of unity
-> CoeffVec f	polynomial coefficients, length should be 2^k for some k
-> DFT f

Naive discrete Fourier transformation performed by evaluating the polynomial at the appropriate roots of unity.

Arguments

:: GaloisField k
=> (Int -> k)	function that gives for input n the principal (2^n)-th root of unity
-> CoeffVec k	length should be n
-> DFT k

Fast Fourier transformation.

Multiply polynomials using FFT

Create a polynomial that goes through the given values.

Inverse discrete Fourier transformation, uses FFT.