Reply by glen herrmannsfeldt●November 10, 20092009-11-10
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
Reply by robert bristow-johnson●November 10, 20092009-11-10
On Nov 10, 2:06�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 �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
Reply by HyeeWang●November 10, 20092009-11-10
On Nov 10, 3:30�am, Clay <c...@claysturner.com> wrote:
> On Nov 9, 4:26�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" �can be get?
>
> > 3. �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?
Reply by Clay●November 9, 20092009-11-09
On Nov 9, 4:26�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" �can be get?
>
> 3. �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
Reply by Rune Allnor●November 9, 20092009-11-09
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
Reply by HyeeWang●November 9, 20092009-11-09
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