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.