I know basically nothing about discrete cosine transforms except what I've learned in the past few minutes from Wikipedia, but apparently an FFT can be turned into a DCT in O(N), and it's not terribly uncommon to use an FFT plus some O(N) ops to compute a DCT.<br>
<br><div class="gmail_quote">On Mon, Aug 2, 2010 at 1:52 PM, Andrei Alexandrescu <span dir="ltr"><<a href="mailto:andrei@erdani.com">andrei@erdani.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
I'll defer answer to this to others, as I haven't used FFT for a long time.<br>
<br>
I do remember, however, that the discrete cosine transform was actually more popular in the circles I frequented. Would it be difficult to adapt your implementation to offer dct?<br>
<br>
<br>
Andrei<br>
<br>
David Simcha wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class="im">
BTW, I've started thinking a little more about big picture issues here, and I'm debating whether it's a higher priority to improve performance on power of 2 sizes, or to try to support other radix values.<br>
<br>
There are two use cases for an FFT that I'm familiar with. The power-of-two limitation isn't severe in either of them.<br>
<br>
1. Getting an idea of what the spectrum of a signal looks like. Here, it's common to pad with zeros because the plots become clearer looking, even if your FFT lib doesn't require it.<br>
<br>
2. Computing a convolution. Here, padding with zeros is necessary anyhow to prevent the signal from being "interpreted" as periodic.<br>
<br>
Are there any major use cases where the power of two limitation is severe, or should I just focus on optimizing powers of 2 and call it a day?<br>
<br></div><div class="im">
On Mon, Aug 2, 2010 at 10:23 AM, Don Clugston <<a href="mailto:dclugston@googlemail.com" target="_blank">dclugston@googlemail.com</a> <mailto:<a href="mailto:dclugston@googlemail.com" target="_blank">dclugston@googlemail.com</a>>> wrote:<br>
<br>
On 2 August 2010 15:41, David Simcha <<a href="mailto:dsimcha@gmail.com" target="_blank">dsimcha@gmail.com</a><br></div><div><div></div><div class="h5">
<mailto:<a href="mailto:dsimcha@gmail.com" target="_blank">dsimcha@gmail.com</a>>> wrote:<br>
> Unfortunately I just downloaded the benchmark program for FFTW<br>
and my FFT is<br>
> a ton slower, depending on how you look at it. Using size 2^20 as my<br>
> benchmark, FFTW takes about 131 seconds to create its plan, even<br>
using<br>
> -oestimate, the fastest planner. However, the plan can be reused if<br>
> performing multiple FFTs of the same size, and once the plan is<br>
created, it<br>
> can do an FFT of size 2^20 in about 53 milliseconds (which I find<br>
almost<br>
> unbelievable because even sorting an array of size 2^20 using a<br>
> well-optimized quick sort takes almost that long, and FFT seems<br>
like it<br>
> should should have a much larger constant than quick sort),<br>
compared to my<br>
> latest improvements to around 730 on the hardware I'm<br>
benchmarking on.<br>
><br>
> On the other hand, for one-off use cases, the lack of needing to<br>
create a<br>
> plan is a big win, both from a speed and a simplicity of API<br>
point of view.<br>
> Benchmarking against R, which doesn't appear to use plans,<br>
making the<br>
> comparison somewhat more relevant, things look better for my FFT:<br>
R takes<br>
> about 610 milliseconds for a size 2^20 pure real FFT.<br>
<br>
All you're seeing is the L2 cache. Did you see the link I posted to<br>
the NG about the internals of FFTW? The graph at the top shows FFTW is<br>
40 times faster than the 'numerical recipes' code for 2^^20. So your<br>
factor of 13 isn't so bad. Based on that graph, if you reduce it to<br>
say 2^^15, the factor should drop significantly. Adding a little bit<br>
of cache awareness (using core.cpuid) should be able to avoid the<br>
performance cliff.<br>
Also, DMD's floating point optimiser is so primitive, you lose up to a<br>
factor of two immediately.<br>
_______________________________________________<br>
phobos mailing list<br></div></div>
<a href="mailto:phobos@puremagic.com" target="_blank">phobos@puremagic.com</a> <mailto:<a href="mailto:phobos@puremagic.com" target="_blank">phobos@puremagic.com</a>><div class="im"><br>
<a href="http://lists.puremagic.com/mailman/listinfo/phobos" target="_blank">http://lists.puremagic.com/mailman/listinfo/phobos</a><br>
<br>
<br>
<br></div>
------------------------------------------------------------------------<div class="im"><br>
<br>
_______________________________________________<br>
phobos mailing list<br>
<a href="mailto:phobos@puremagic.com" target="_blank">phobos@puremagic.com</a><br>
<a href="http://lists.puremagic.com/mailman/listinfo/phobos" target="_blank">http://lists.puremagic.com/mailman/listinfo/phobos</a><br>
</div></blockquote><div><div></div><div class="h5">
_______________________________________________<br>
phobos mailing list<br>
<a href="mailto:phobos@puremagic.com" target="_blank">phobos@puremagic.com</a><br>
<a href="http://lists.puremagic.com/mailman/listinfo/phobos" target="_blank">http://lists.puremagic.com/mailman/listinfo/phobos</a><br>
</div></div></blockquote></div><br>