<div dir="ltr">hi,<div>I'd like to pick up this thread after stumbling on it in the archive. For the same reason that Matt explained I'd like to see rfft~ working for small blocks of 4 to 32 samples.</div><div>best, marius.</div></div><div class="gmail_extra"><br><div class="gmail_quote">2015-10-19 22:08 GMT+02:00 Matt Barber <span dir="ltr"><<a href="mailto:brbrofsvl@gmail.com" target="_blank">brbrofsvl@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_default" style="font-family:verdana,sans-serif">Seems fine, since the 2-pt FFTs are trivial to compute if needed. And the rfft/rifft objects already throw an error for block < 4.</div><div class="gmail_default" style="font-family:verdana,sans-serif"><br></div><div class="gmail_default" style="font-family:verdana,sans-serif">One use case for the smaller FFTs is that since they can be computed on paper as a direct DFT pretty easily (4 and 8 points especially), the Pd objects make great illustration for teaching purposes. "We did the calculation. Here's what we expect; let's see if Pd agrees."</div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Oct 19, 2015 at 2:26 PM, Miller Puckette <span dir="ltr"><<a href="mailto:msp@ucsd.edu" target="_blank">msp@ucsd.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">I'm not sure, but I think I had limited it to 64 because some older FFT<br>
package I was using had that limit. I'm not sure but I think the rfft<br>
objects require at least 4 points to work properly. So perhaps it would be<br>
OK to impose 4 as a minimum for all the FFT objects.<br>
<br>
In any case, there certainly should have been an error message... it simply<br>
never occurred to me that anyone would want an FFT of fewer than 64 points :)<br>
<span class="m_-2100105557282423746HOEnZb"><font color="#888888"><br>
M<br>
</font></span><div class="m_-2100105557282423746HOEnZb"><div class="m_-2100105557282423746h5"><br>
<br>
On Sat, Oct 17, 2015 at 10:59:00AM +0200, katja wrote:<br>
> OOURA's cdft and rdft function descriptions clearly state that FFT<br>
> size 2 is the minimum. Maybe the data permutation is trickier for<br>
> block size < 64. The old arrangement was weird, you don't get an array<br>
> with complex numbers, but the imaginary output appearing in reversed<br>
> order after the real output. Because the FFT functions are in Pd's API<br>
> it is still rearranged that way (and the object has to rearrange again<br>
> when copying to the outlet). I don't know if this hampers FFT size <<br>
> 64, this is just a wild guess.<br>
><br>
> Anyway I don't like this limitation at all. Small FFT sizes can be<br>
> indispensable in rigid tests and experiments.<br>
><br>
> Katja<br>
><br>
> Katja<br>
><br>
> On Sat, Oct 17, 2015 at 4:17 AM, Matt Barber <<a href="mailto:brbrofsvl@gmail.com" target="_blank">brbrofsvl@gmail.com</a>> wrote:<br>
> > Looking closer, it appears the OOURA fft has special routines for n<64...<br>
> > but it uses those routines regularly as subroutines in larger ffts. In any<br>
> > case it looks like the smaller block sizes are intended to be usable in the<br>
> > code itself, but Miller must've had a reason not to trust them. Here's the<br>
> > main OOURA complex fourier transform subroutine, which calls a bunch of<br>
> > others, which all call smaller ones. The Pd prologue code would make sure<br>
> > that none of the smaller cases at the bottom would ever be called.<br>
> ><br>
> > ==============================<wbr>=========<br>
> > void cftfsub(int n, FFTFLT *a, int *ip, int nw, FFTFLT *w)<br>
> > {<br>
> > void bitrv2(int n, int *ip, FFTFLT *a);<br>
> > void bitrv216(FFTFLT *a);<br>
> > void bitrv208(FFTFLT *a);<br>
> > void cftf1st(int n, FFTFLT *a, FFTFLT *w);<br>
> > void cftrec4(int n, FFTFLT *a, int nw, FFTFLT *w);<br>
> > void cftleaf(int n, int isplt, FFTFLT *a, int nw, FFTFLT *w);<br>
> > void cftfx41(int n, FFTFLT *a, int nw, FFTFLT *w);<br>
> > void cftf161(FFTFLT *a, FFTFLT *w);<br>
> > void cftf081(FFTFLT *a, FFTFLT *w);<br>
> > void cftf040(FFTFLT *a);<br>
> > void cftx020(FFTFLT *a);<br>
> > #ifdef USE_CDFT_THREADS<br>
> > void cftrec4_th(int n, FFTFLT *a, int nw, FFTFLT *w);<br>
> > #endif /* USE_CDFT_THREADS */<br>
> ><br>
> > if (n > 8) {<br>
> > if (n > 32) {<br>
> > cftf1st(n, a, &w[nw - (n >> 2)]);<br>
> > #ifdef USE_CDFT_THREADS<br>
> > if (n > CDFT_THREADS_BEGIN_N) {<br>
> > cftrec4_th(n, a, nw, w);<br>
> > } else<br>
> > #endif /* USE_CDFT_THREADS */<br>
> > if (n > 512) {<br>
> > cftrec4(n, a, nw, w);<br>
> > } else if (n > 128) {<br>
> > cftleaf(n, 1, a, nw, w);<br>
> > } else {<br>
> > cftfx41(n, a, nw, w);<br>
> > }<br>
> > bitrv2(n, ip, a);<br>
> > } else if (n == 32) {<br>
> > cftf161(a, &w[nw - 8]);<br>
> > bitrv216(a);<br>
> > } else {<br>
> > cftf081(a, w);<br>
> > bitrv208(a);<br>
> > }<br>
> > } else if (n == 8) {<br>
> > cftf040(a);<br>
> > } else if (n == 4) {<br>
> > cftx020(a);<br>
> > }<br>
> > }<br>
> > ==============================<wbr>=========<br>
> ><br>
> > On Fri, Oct 16, 2015 at 7:43 PM, Robert Esler <<a href="mailto:robert@urbanstew.org" target="_blank">robert@urbanstew.org</a>> wrote:<br>
> >><br>
> >> Sorry I checked your patch again. I get the same behavior. I had an<br>
> >> older version of Pd I was using.<br>
> >><br>
> >> Yes, I just noticed this too. It appears OOURA limits the calculation to<br>
> >> a block size of 32 or higher. Why? The code is so horribly documented I’d<br>
> >> rather not even try to figure it out.<br>
> >><br>
> >> Pd also has the option of using the FFTW3 library by Thomas Grill, which<br>
> >> on a surface reading doesn’t seem to have a block boundary. But I can’t be<br>
> >> sure w/o trying it. Of course this would require a manual compiling of Pd.<br>
> >><br>
> >> Not sure why the mayer fft lib was removed, but this is one of the few<br>
> >> instances of Pd breaking older patches. Maybe this needs to be a dev<br>
> >> request? At the very least print an error to the Pd window.<br>
> >><br>
> >> -Rob<br>
> >><br>
> >> P.S - I have a C++ version of the old mayer_fft that I could probably wrap<br>
> >> into a Pd object if it seems like this is a big enough problem.<br>
> >><br>
> >><br>
> >> On Oct 16, 2015, at 4:09 PM, Matt Barber <<a href="mailto:brbrofsvl@gmail.com" target="_blank">brbrofsvl@gmail.com</a>> wrote:<br>
> >><br>
> >> OK, looking at the OOURA code, the init routine has this:<br>
> >><br>
> >> ========================<br>
> >> static int ooura_init( int n)<br>
> >> {<br>
> >> n = (1 << ilog2(n));<br>
> >> if (n < 64)<br>
> >> return (0);<br>
> >> ========================<br>
> >><br>
> >><br>
> >> then later in the fft/ifft routine:<br>
> >><br>
> >> ========================<br>
> >> if (!ooura_init(2*n))<br>
> >> return;<br>
> >> ========================<br>
> >><br>
> >> and rfft:<br>
> >> ========================<br>
> >> if (!ooura_init(n))<br>
> >> return;<br>
> >> ========================<br>
> >><br>
> >><br>
> >><br>
> >> since these operate directly on samples in the signal vector, it will pass<br>
> >> signals in small blocks without performing dft. I don't know what this is<br>
> >> supposed to avoid. I've used fft in small block sizes before, and I can't be<br>
> >> the only one whose patches might be broken by this.<br>
> >><br>
> >><br>
> >><br>
> >> On Fri, Oct 16, 2015 at 5:33 PM, katja <<a href="mailto:katjavetter@gmail.com" target="_blank">katjavetter@gmail.com</a>> wrote:<br>
> >>><br>
> >>> If I understand the fft files correctly OOURA is now the default, but<br>
> >>> 'disguised' as mayer fft so the old API should remain valid.<br>
> >>><br>
> >>> (<a href="http://sourceforge.net/p/pure-data/pure-data/ci/master/tree/src/d_fft_fftsg.c" rel="noreferrer" target="_blank">http://sourceforge.net/p/<wbr>pure-data/pure-data/ci/master/<wbr>tree/src/d_fft_fftsg.c</a>).<br>
> >>><br>
> >>> Indeed I get the same result for Matt's test patch with Pd 0.46-5<br>
> >>> which is on my system. Sinusoids for block size 8 and 16, instead of<br>
> >>> spectrum points.<br>
> >>><br>
> >>> A while ago I've been reading in OOURA fft code and what I remember<br>
> >>> is, Pd uses its mixed radix functions. Not sure about it though.<br>
> >>><br>
> >>> Katja<br>
> >>><br>
> >>><br>
> >>> On Fri, Oct 16, 2015 at 10:00 PM, Robert Esler <<a href="mailto:robert@urbanstew.org" target="_blank">robert@urbanstew.org</a>><br>
> >>> wrote:<br>
> >>> ><br>
> >>> > As far as I know Pd stopped using the mayer fft library in .46, which<br>
> >>> > is probably why this is new behavior. I only get what you’re experiencing<br>
> >>> > with a block size of 8. Otherwise, it seems to perform as expected.<br>
> >>> > To really understand if this is a bug or not is to know which fft<br>
> >>> > library is being used for OS X. My guess is it’s the OOURA but it’s not<br>
> >>> > clear from looking at [fft~] object code that comes with distribution.<br>
> >>> > You could also download the old library and recompile Pd, but I doubt<br>
> >>> > it’s worth it.<br>
> >>> > -Rob<br>
> >>> > -------<br>
> >>> > Hi list,<br>
> >>> ><br>
> >>> > There's either a major bug in the [fft~] objects in Pd-0.46.7 (64bit<br>
> >>> > OSX)<br>
> >>> > or I'm going crazy. I'd love to see if others can reproduce it.<br>
> >>> ><br>
> >>> > Basically, for [block~] sizes less than 32 bits, [fft~] doesn't perform<br>
> >>> > --<br>
> >>> > it just passes the signal through unchanged. [ifft~] does the same. The<br>
> >>> > [rfft~]-[rifft~] is a little more complicated -- it passes signal<br>
> >>> > through<br>
> >>> > but zeroes out the last N/2 for [block~] sizes less than 64.<br>
> >>> ><br>
> >>> ><br>
> >>> > See the attached patch, which only shows [fft~]. The saved contents of<br>
> >>> > the<br>
> >>> > tables on opening are the results for [block~ 8] on my machine, for<br>
> >>> > quarter-nyquist at 44100.<br>
> >>> ><br>
> >>> > I've never seen this before in other versions of Pd. Anyone else get<br>
> >>> > this<br>
> >>> > behavior?<br>
> >>> ><br>
> >>> > Matt<br>
> >>> > ______________________________<wbr>_________________<br>
> >>> > <a href="mailto:Pd-list@lists.iem.at" target="_blank">Pd-list@lists.iem.at</a> mailing list<br>
> >>> > UNSUBSCRIBE and account-management -><br>
> >>> > <a href="http://lists.puredata.info/listinfo/pd-list" rel="noreferrer" target="_blank">http://lists.puredata.info/<wbr>listinfo/pd-list</a><br>
> >><br>
> >><br>
> >><br>
> ><br>
><br>
> ______________________________<wbr>_________________<br>
> <a href="mailto:Pd-list@lists.iem.at" target="_blank">Pd-list@lists.iem.at</a> mailing list<br>
> UNSUBSCRIBE and account-management -> <a href="http://lists.puredata.info/listinfo/pd-list" rel="noreferrer" target="_blank">http://lists.puredata.info/<wbr>listinfo/pd-list</a><br>
</div></div></blockquote></div><br></div>
</div></div><br>______________________________<wbr>_________________<br>
<a href="mailto:Pd-list@lists.iem.at">Pd-list@lists.iem.at</a> mailing list<br>
UNSUBSCRIBE and account-management -> <a href="http://lists.puredata.info/listinfo/pd-list" rel="noreferrer" target="_blank">http://lists.puredata.info/<wbr>listinfo/pd-list</a><br>
<br></blockquote></div><br></div>