Algorithms For Programmers Ideas And Source Code


E-Book Content

Algorithms for programmers ideas and source code This document is work in progress: read the ”important remarks” near the beginning J¨org Arndt [email protected] This document1 was LATEX’d at March 26, 2003 1 This document is online at http://www.jjj.de/fxt/. It will stay available online for free. Contents Some important remarks about this document 1 The Fourier transform 8 10 1.1 The discrete Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 Symmetries of the Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3 Summary of definitions of Fourier transforms * . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4 Radix 2 FFT algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4.1 A little bit of notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4.2 Decimation in time (DIT) FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4.3 Decimation in frequency (DIF) FFT . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Saving trigonometric computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.5.1 Using lookup tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.5.2 Recursive generation of the sin/cos-values . . . . . . . . . . . . . . . . . . . . . . . 19 1.5.3 Using higher radix algorithms . . . . . . . . . . . . . . . . . . . . . . . . .
You might also like

Laboratory In Software Engineering (eecs 6170)
Authors: Daniel Jackson , Rob Miller    163    0


Concise Algorithmics: The Basic Toolbox
Authors: Mehlhorn K. , Sanders P.    126    0


Invitation To Fixed-parameter Algorithms
Authors: Rolf Niedermeier    116    0



Image Processing In C
Authors: Dwayne Phillips    163    0


Programming In Haskell
Authors: Graham Hutton    158    0


Professional Programmer's Guide To Fortran 77
Authors: Page C    137    0


Molecular Evolution: Computer Analysis Of Protein And Nucleic Acid Sequences
Authors: Abelson J.N. , Simon M.I. , Doolittle R.F. (eds.)    146    0


C# Essentials
Authors: Ben Albahari , Peter Drayton , Brad Merrill    105    0


Oracle9i Recovery Manager Reference
Authors: Ashdown L.    223    0