arb-fft- Pure Haskell arbitrary length FFT library

Safe HaskellNone



Mixed-radix FFT calculation.

Arbitrary input vector lengths are handled using a mixed-radix Cooley-Tukey decimation in time algorithm with residual prime length vectors being treated using Rader's algorithm or hand-coded codelets for small primes.



fft :: Vector v (Complex Double) => v (Complex Double) -> IO (v (Complex Double))Source

Forward FFT with embedded plan calculation.

ifft :: Vector v (Complex Double) => v (Complex Double) -> IO (v (Complex Double))Source

Inverse FFT with embedded plan calculation.

fftWith :: Vector v (Complex Double) => Plan -> v (Complex Double) -> v (Complex Double)Source

Forward FFT with pre-computed plan.

ifftWith :: Vector v (Complex Double) => Plan -> v (Complex Double) -> v (Complex Double)Source

Inverse FFT with pre-computed plan.

plan :: Int -> IO PlanSource

Plan calculation for a given problem size.

planFromFactors :: Int -> (Int, Vector Int) -> IO PlanSource

Plan calculation for a given problem factorisation.

execute :: Plan -> Direction -> VCD -> VCDSource

Main FFT plan execution driver.

data Plan Source

A FFT plan. This depends only on the problem size and can be pre-computed and reused to transform (and inverse transform) any number of vectors of the given size.




plDLInfo :: Vector (Int, Int, VVVCD, VVVCD)

Size information and diagonal matrix entries for Danielson-Lanczos recursive decomposition of problem size.

plPermute :: Maybe VI

Input vector permutation to use before base transformation and recursive Danielson-Lanczos composition.

plBase :: BaseTransform

Base transformation used for each sub-vector before performing recursive Danielson-Lanczos steps to form the full FFT result.


data Direction Source

Transform direction: Forward is the normal FFT, Inverse is inverse FFT.



data BaseTransform Source

A base transform used at the bottom of the recursive Cooley-Tukey decomposition of the input problem size: either a simple DFT, a special hard-coded small problem size case, or a Rader prime-length FFT invocation.



Hard-coded small-size base transform.


baseSize :: Int

Simple DFT base transform, giving problem size and powers of roots of unity needed for transform.


baseSize :: Int
dftWsFwd :: VCD
dftWsInv :: VCD

Prime-length Rader FFT base transform, giving problem size, output index permutation (the input index permutation is folded into the main input permutation of the full transform), pre-transformed Rader b sequence for forward and inverse problems, the (padded or not) problem size for Rader sequence convolution and a sub-plan (either of size baseSize-1 or the next larger power of two) for computing the Rader convolution.


baseSize :: Int
raderOutPerm :: VI
raderBFwd :: VCD
raderBInv :: VCD
raderConvSize :: Int
raderConvPlan :: Plan