Calculate MACs in MATLAB
in [DSP]
|
Prev: Is 44.1 KHz sample-rate enough to cover the entire human hearing range?
Next: Is 44.1 KHz sample-rate enough to cover the entire human hearing range?
From: markt on 6 May 2008 17:45 >An interesting statement. O() notation gives the order as >N goes to infinity, and it may or may not be of any use >for small N. Now, is infinity prime or composite? I was reading this thinking "yeah, it's probably not very good for small N" then I got to the last bit and had to laugh. :) Mark
From: glen herrmannsfeldt on 6 May 2008 03:12 Steven G. Johnson wrote: (snip) > Short answer: FFTW uses the prime-factor algorithm for small sizes (<= > 16) within its codelets at the leaves of its recursion. Larger > composite sizes are broken down into smaller sizes using mixed-radix > Cooley-Tukey. It is O(N log N) for all N. An interesting statement. O() notation gives the order as N goes to infinity, and it may or may not be of any use for small N. Now, is infinity prime or composite? -- glen
From: Jerry Avins on 7 May 2008 00:41 glen herrmannsfeldt wrote: > Steven G. Johnson wrote: > (snip) > >> Short answer: FFTW uses the prime-factor algorithm for small sizes (<= >> 16) within its codelets at the leaves of its recursion. Larger >> composite sizes are broken down into smaller sizes using mixed-radix >> Cooley-Tukey. It is O(N log N) for all N. > > An interesting statement. O() notation gives the order as > N goes to infinity, and it may or may not be of any use > for small N. Now, is infinity prime or composite? Composite, of course. Primes get scarcer as numbers increase. By the time infinity is reached, they are vanishingly scarce. Aint logic wunnerful? Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
From: markt on 7 May 2008 12:05
>If you look at the definition of asymptotic (O) notation, you'll see >that there's no need to say whether "infinity" is prime or composite. I think he was intentionally being funny. ;) >In practice, the O(N log N) prime-size algorithms already have clear >advantage for N > 100. In principle, you usually have enough freedom >to choose your transform to be a composite size, but many people >apparently find it useful to not have to worry about resizing their >data, without being afraid that if they are unlucky the FFT will be >thousands of times slower (as opposed to just a factor of 10). I played around with FFTW quite a bit a few years ago (you and I traded emails about my efforts, and my company actually bought a license at the time) and I can say that this is at the very least, empirically true. >And even optimality in terms of flop counts is not proven; no one >knows tight lower bounds. There isn't even any proof that you can't >do better than O(N log N) for an FFT (although no counterexamples are >known). Though I suppose the fact that O(N log N) is called an estimation implies this statement, I did not know this explicitly. Particularly the second statement. Learn something new every day. Do you suppose it is an unprovable problem? >Yes, especially for large N I'm not aware of any implementation of the >minimal-known-flop FFT algorithm(s) that is competitive in practice >with highly optimized implementations. You just have too many other >things to worry about that are more important than arithmetic these >days. On the other hand, to be fair, I doubt that the highly >optimized implementations sacrifice more than 10-15% in the flop count >compared to the lowest known flop counts. Too bad. It's not difficult for other math functions, such as a complex multiply or magnitude function (which is what FFTW's SIMD code does), which are then ordered in memory for fast access and a consistently full pipeline. Once you have to stride or do a corner turn, the effort just ain't worth it, not for the 10% at least. Mark |