Safe Haskell | None |
---|---|

Language | Haskell2010 |

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

:: 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.

:: 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.

fftMult :: GaloisField k => (Int -> k) -> CoeffVec k -> CoeffVec k -> CoeffVec k Source #

Multiply polynomials using FFT

fftTargetPoly :: GaloisField k => (Int -> k) -> Int -> VPoly k Source #

interpolate :: GaloisField k => (Int -> k) -> [k] -> VPoly k Source #

Create a polynomial that goes through the given values.

inverseDft :: GaloisField k => (Int -> k) -> DFT k -> CoeffVec k Source #

Inverse discrete Fourier transformation, uses FFT.