Forums

FFT computation complexity

Started by HyeeWang November 9, 2009
Consider next the fast LMS algotithm. Each N-point FFT (and IFFT)
requires approximately N log2 N real multiplication (Oppenheim and
Scafer 1989),where N = 2M.

Above, it cited from page 454 ,<< Adaptive Filter Theory>> ,Third
edition by Simon Haykin.

1. The contents in brackets, ie., Oppenheim and Scafer 1989, what does
it mean? Does it refer to the famous textbook

"Discrete-time Signal Precessing" ? If not ,then what?

2. Actually ,I am astonished that how the result of FFT computation
complexity "N log2 N"  can be get?

3.  For simple denotation,"N log2 N " in my expression is a log
formula base 2.

Cheers

HyeeWang

On 9 Nov, 10:26, HyeeWang <hyeew...@gmail.com> wrote:
> Consider next the fast LMS algotithm. Each N-point FFT (and IFFT) > requires approximately N log2 N real multiplication (Oppenheim and > Scafer 1989),where N = 2M. > > Above, it cited from page 454 ,<< Adaptive Filter Theory>> ,Third > edition by Simon Haykin. > > 1. The contents in brackets, ie., Oppenheim and Scafer 1989, what does > it mean? Does it refer to the famous textbook > > "Discrete-time Signal Precessing" ? If not ,then what?
Usually, expressions like (AuthorA and AuthorB, SomeYear) refers to the book or article the two authors that was published in the stated year. Books published by the major academic publishers, like the one by Haykin, will have a references list, either at the end of each chapter, or at the end of the book, where the exact details about the books mentioned are listed. Once you find the references list you will find the details about the book you ask about. As for the authors Oppenheim and Schafer, it might pay off to pay attention to detail. They have co-authored a significant number of textbooks with barely discernable titles. Just double and triple check every single detail before you decide which book to get - it is very easy to get the wrong book. Rune
On Nov 9, 4:26&#2013266080;am, HyeeWang <hyeew...@gmail.com> wrote:
> Consider next the fast LMS algotithm. Each N-point FFT (and IFFT) > requires approximately N log2 N real multiplication (Oppenheim and > Scafer 1989),where N = 2M. > > Above, it cited from page 454 ,<< Adaptive Filter Theory>> ,Third > edition by Simon Haykin. > > 1. The contents in brackets, ie., Oppenheim and Scafer 1989, what does > it mean? Does it refer to the famous textbook > > "Discrete-time Signal Precessing" ? If not ,then what? > > 2. Actually ,I am astonished that how the result of FFT computation > complexity "N log2 N" &#2013266080;can be get? > > 3. &#2013266080;For simple denotation,"N log2 N " in my expression is a log > formula base 2. > > Cheers > > HyeeWang
Try graphing N log2(N) and just log2(N) - they are hardly the same. N log2(N) is log2(N^N) Clay
On Nov 10, 3:30&#2013266080;am, Clay <c...@claysturner.com> wrote:
> On Nov 9, 4:26&#2013266080;am, HyeeWang <hyeew...@gmail.com> wrote: > > > > > > > Consider next the fast LMS algotithm. Each N-point FFT (and IFFT) > > requires approximately N log2 N real multiplication (Oppenheim and > > Scafer 1989),where N = 2M. > > > Above, it cited from page 454 ,<< Adaptive Filter Theory>> ,Third > > edition by Simon Haykin. > > > 1. The contents in brackets, ie., Oppenheim and Scafer 1989, what does > > it mean? Does it refer to the famous textbook > > > "Discrete-time Signal Precessing" ? If not ,then what? > > > 2. Actually ,I am astonished that how the result of FFT computation > > complexity "N log2 N" &#2013266080;can be get? > > > 3. &#2013266080;For simple denotation,"N log2 N " in my expression is a log > > formula base 2. > > > Cheers > > > HyeeWang > > Try graphing N log2(N) and just log2(N) - they are hardly the same. > > N log2(N) is log2(N^N) > > Clay- Hide quoted text - > > - Show quoted text -
Thank you! Rune, I saw the book references list and knew that it is indeed "Discrete-time Signal Precessing". I studied that book ,but still not find the exact pages. Thank you! clay. But I did not catch what you said exactly. what is "Try graphing N log2 (N) and just log2(N)"? Anyway,in my expression, N log2 N actually is N*log2 (N), where 2 shoud be in subscript form. In my humble opinion, the N-points FFT computation complexity should be (N/2)* log2 (N) complex multiplication,ie., (2N)* log2 (N) real multiplication. How Oppenheim and Scafer get the N*log2 (N) real multiplication result?
On Nov 10, 2:06&#2013266080;am, HyeeWang <hyeew...@gmail.com> wrote:

> In my humble opinion, the N-points FFT computation complexity should > be (N/2)* log2 (N) complex multiplication,
actually, if you write the DIT or DIF alg so that multiplication by 1 or i (where the real and imaginary parts just get swapped and something is subtracted instead of added), then the number of complex multiplications are (N/2) * log2(N/2)
> ie., (2N)* log2(N) real multiplication.
and i would get (2N)*log2(N) - 2N real multiplies.
> How Oppenheim and Scafer &#2013266080;get the N*log2 (N) real > multiplication result?
dunno. want to tell me a page number or equation number? a while ago someone posted some identity that performs a complex multiplication with 3 real multiplies and a bunch of additions of intermediate terms. but that wouldn't change the 2N to just N. r b-j
HyeeWang <hyeewang@gmail.com> wrote:
 
> Thank you! Rune, I saw the book references list and knew that it is > indeed "Discrete-time Signal Precessing". I studied that book ,but > still not find the exact pages.
> Thank you! clay. > But I did not catch what you said exactly. what is "Try graphing N log2 > (N) and just log2(N)"?
> Anyway,in my expression, N log2 N actually is N*log2 (N), where 2 > shoud be in subscript form.
See: http://en.wikipedia.org/wiki/Big_O_notation While it is normally a subscript in math books, it is rare in computer languages. Fortran has had the ALOG10 function for many years (the A to avoid problems with names starting with L being integer). PL/I has both the LOG10 and LOG2 functions. However, Big O notation ignores any leading constant coefficients, and the difference between log2 and log (natural log in all computer languages that I know of) is just a constant factor.
> In my humble opinion, the N-points FFT computation complexity should > be (N/2)* log2 (N) complex multiplication,ie., (2N)* log2 (N) real > multiplication. How Oppenheim and Scafer get the N*log2 (N) real > multiplication result?
Again a constant factor to ignore. There are, in fact, cases where for real problems, and not in the large N limit, the coefficient becomes important. In those cases, one must do a detailed accounting of the operations needed, maybe also specifying the machine. In the 1960's I remember documentation that gave the whole polynomial for the number of multiplications, additions, and divisions required by an algorithm as a function of N. -- glen
On 10 Nov, 08:06, HyeeWang <hyeew...@gmail.com> wrote:

> Anyway,in my expression, N log2 N actually is N*log2 (N), where 2 > shoud be in subscript form.
That's just a notational convenience. You might want to look at this page for material on the Big-O notation: http://en.wikipedia.org/wiki/Big_O_notation Rune