Next  |  Prev  |  Up  |  Top  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

FFT Convolution vs. Direct Convolution

Let's compare the number of operations needed to perform the convolution of

2 length $ N$ sequences:

N FFT Direct Convolution
4 176 16
32 2560 1024
64 5888 4096
128 13,312 16,384
256 29,696 65,536
2048 311,296 4,194,304

In this example (from Strum and Kirk), the FFT (software) beats direct time-domain convolution at length 128 and higher


Next  |  Prev  |  Up  |  Top  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

Download ReviewFourier.pdf
Download ReviewFourier_2up.pdf
Download ReviewFourier_4up.pdf
[Comment on this page via email]

``Review of the Discrete Fourier Transform (DFT)'', by Julius O. Smith III, (From Lecture Overheads, Music 421).
Copyright © 2018-04-10 by Julius O. Smith III
Center for Computer Research in Music and Acoustics (CCRMA),   Stanford University
CCRMA  [Automatic-links disclaimer]