Changes between Version 28 and Version 29 of Examples/Fft2dHighpass


Ignore:
Timestamp:
Nov 11, 2010, 4:16:12 AM (14 years ago)
Author:
Ben Lippmeier
Comment:

--

Legend:

Unmodified
Added
Removed
Modified

  • Examples/Fft2dHighpass

    v28 v29  
    1111== Code ==
    1212
    13 The main algorithm is at [http://code.haskell.org/repa/repa-head/repa-algorithms/Data/Array/Repa/Algorithms/FFT.hs FFT.hs]
     13The main algorithm is at [http://code.ouroborus.net/repa/repa-head/repa-algorithms/Data/Array/Repa/Algorithms/FFT.hs FFT.hs]
    1414
    15 The wrapper is at [http://code.haskell.org/repa/repa-head/repa-examples/FFT/HighPass/src/Main.hs Main.hs]
     15The wrapper is at [http://code.ouroborus.net/repa/repa-head/repa-examples/FFT/HighPass/src/Main.hs Main.hs]
    1616
    1717== Test Data ==
    … …  
    2020|| lena.bmp || lena-high2.bmp ||
    2121|| [[Image(Examples/Fft2dHighpass:lena-thumb.jpg)]] || [[Image(WikiStart:lena-high2-thumb.jpg)]] ||
    22 || [http://code.haskell.org/repa/wiki/images/lena.bmp full size] || [http://code.haskell.org/repa/wiki/images/lena-high2.bmp full size] ||
     22|| [http://code.ouroborus.net/repa/wiki/images/lena.bmp full size] || [http://code.ouroborus.net/repa/wiki/images/lena-high2.bmp full size] ||
    2323
    2424== Runtime ==
    … …  
    4242
    4343|| Version || Time(s) || Source ||
    44 || Using Data.Vector.Unboxed || 2.88 || [http://code.haskell.org/repa/repa-head/repa-examples/FFT/HighPass/legacy/vector/FFT.hs FFT.hs] ||
    45 || Using Jones's inplace C implementation || 0.24 || [http://code.haskell.org/repa/repa-head/repa-examples/FFT/HighPass/legacy/c/Jones.c Jones.c] ||
    46 || Using FFTW using Estimate mode || 0.09 || [http://code.haskell.org/repa/repa-head/repa-examples/FFT/HighPass/legacy/c/FFTW.c FFTW.c] ||
     44|| Using Data.Vector.Unboxed || 2.88 || [http://code.ouroborus.net/repa/repa-head/repa-examples/FFT/HighPass/legacy/vector/FFT.hs FFT.hs] ||
     45|| Using Jones's inplace C implementation || 0.24 || [http://code.ouroborus.net/repa/repa-head/repa-examples/FFT/HighPass/legacy/c/Jones.c Jones.c] ||
     46|| Using FFTW using Estimate mode || 0.09 || [http://code.ouroborus.net/repa/repa-head/repa-examples/FFT/HighPass/legacy/c/FFTW.c FFTW.c] ||
    4747
    4848The vector version uses the same recursive radix-2 decimation in time (DIT) algorithm as the Repa version, but is not rank generalised. It applies a recursive 1d FFT to each row and then transposes the matrix, twice each. Recursive FFT algorithms tend to be slower than in-place ones because intermediate data is written into new vectors at each recursion. A 512 point FFT is built from two 256 point FFTs, which are built from 4 128 point FFTs and so on. The result of each FFT is a new vector which needs to be allocated, filled, then unboxed again during the next recursion. The base case is a 2 point vector, so there are 256 of them to allocate then unbox at the lowest step.