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