hi,
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.
best, marius.
2015-10-19 22:08 GMT+02:00 Matt Barber <brbrof...@gmail.com>:
> 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 <m...@ucsd.edu> 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 <brbrof...@gmail.com>
>> 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 <rob...@urbanstew.org>
>> 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 <brbrof...@gmail.com>
>> 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 <katjavet...@gmail.com>
>> 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 <
>> rob...@urbanstew.org>
>> > >>> 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
>> > >>> > _______________________________________________
>> > >>> > Pd-list@lists.iem.at mailing list
>> > >>> > UNSUBSCRIBE and account-management ->
>> > >>> > http://lists.puredata.info/listinfo/pd-list
>> > >>
>> > >>
>> > >>
>> > >
>> >
>> > _______________________________________________
>> > Pd-list@lists.iem.at mailing list
>> > UNSUBSCRIBE and account-management -> http://lists.puredata.info/
>> listinfo/pd-list
>>
>
>
> _______________________________________________
> Pd-list@lists.iem.at mailing list
> UNSUBSCRIBE and account-management -> http://lists.puredata.info/
> listinfo/pd-list
>
>
_______________________________________________
Pd-list@lists.iem.at mailing list
UNSUBSCRIBE and account-management ->
https://lists.puredata.info/listinfo/pd-list
