Fred Marshall wrote:
> On 4/2/2012 8:10 PM, Les Cargill wrote:
> ....
>
> oh, it's N+M-1 not N+M+1....
>

Yes! Typo - my bad.

> e.g. 3 and 4 convolve to length 6.
>
> Fred


Strangely, Octave uses N+M+1 ( although I used N+M-1
myself ). Octave really uses (N+1)+(M+1)-1....

--
Les Cargill

On 4/2/2012 8:10 PM, Les Cargill wrote:
....

oh, it's N+M-1 not N+M+1....

e.g. 3 and 4 convolve to length 6.

Fred

Fred Marshall wrote:
> On 4/1/2012 5:18 PM, Les Cargill wrote:
>> Les Cargill wrote:
>>> Fred Marshall wrote:
>>>> On 4/1/2012 8:57 AM, Les Cargill wrote:
>>>>> I'm not sure what it's called - the "power of two method?"
>>>>
>>>> Well, I don't hardly use such fancy expressions; only N+M-1 is the
>>>> minimum.
>>>
>>> Correct me if I am wrong, but I believe that both FFT-objects
>>> must be of the same order...
>>>
>>>> You can't go wrong with that.
>>>
>>> I'll try N+M+1 and see if it works.
>>>
>>
>> It works, but as various people have said on them there Innerwebs, a
>> power-of-2 size is considerably ( 3xish in my test case ) faster.
>>
>>>> I guess that my N (the number of samples in a sequence) is your n+1,
>>>> etc.
>>>> Then, if you must have length a power of 2, just pick it to be greater
>>>> than the minimum.
>>>> Of course, that's what your expressions say.
>>>>
>>>> Fred
>>>
>>> --
>>> Les Cargill
>>
>> --
>> Les Cargill
>
> I don/t know about the 3xish faster in the modern world.

it turns out to be true with FFTW. It's a change of one line - either
do all the ceil() stuff to produce the order of the two FFT, or
use (N+M+1). So it's not likely that a sidestream
error occurred - I'd bet  on the one liner.

The FFT are implemented as C++ classes layered over FFTW calls, with
a parameter to override the order of the FFT.

I love this note from the FFTW website:
"Our code generator also produces new algorithms that we do not yet 
completely understand"

http://www.nanophys.kth.se/nanophys/fftw-info/fftw_1.html

> It used to be that n^2 was important.
> I think the world has somewhat passed this by for two reasons:
> 1) the algorithms improved since.
> 2) the relative speed improved since. (i.e. saving time is not the issue
> it once was on a relative basis).
>

Absolutely.

> Fred

--
Les Cargill

On 4/1/2012 5:18 PM, Les Cargill wrote:
> Les Cargill wrote:
>> Fred Marshall wrote:
>>> On 4/1/2012 8:57 AM, Les Cargill wrote:
>>>> I'm not sure what it's called - the "power of two method?"
>>>
>>> Well, I don't hardly use such fancy expressions; only N+M-1 is the
>>> minimum.
>>
>> Correct me if I am wrong, but I believe that both FFT-objects
>> must be of the same order...
>>
>>> You can't go wrong with that.
>>
>> I'll try N+M+1 and see if it works.
>>
>
> It works, but as various people have said on them there Innerwebs, a
> power-of-2 size is considerably ( 3xish in my test case ) faster.
>
>>> I guess that my N (the number of samples in a sequence) is your n+1,
>>> etc.
>>> Then, if you must have length a power of 2, just pick it to be greater
>>> than the minimum.
>>> Of course, that's what your expressions say.
>>>
>>> Fred
>>
>> --
>> Les Cargill
>
> --
> Les Cargill

I don/t know about the 3xish faster in the modern world.
It used to be that n^2 was important.
I think the world has somewhat passed this by for two reasons:
1) the algorithms improved since.
2) the relative speed improved since.  (i.e. saving time is not the 
issue it once was on a relative basis).

Fred

Les Cargill wrote:
> Fred Marshall wrote:
>> On 4/1/2012 8:57 AM, Les Cargill wrote:
>>> I'm not sure what it's called - the "power of two method?"
>>
>> Well, I don't hardly use such fancy expressions; only N+M-1 is the
>> minimum.
>
> Correct me if I am wrong, but I believe that both FFT-objects
> must be of the same order...
>
>> You can't go wrong with that.
>
> I'll try N+M+1 and see if it works.
>

It works, but as various people have said on them there Innerwebs, a
power-of-2 size is considerably ( 3xish in my test case ) faster.

>> I guess that my N (the number of samples in a sequence) is your n+1, etc.
>> Then, if you must have length a power of 2, just pick it to be greater
>> than the minimum.
>> Of course, that's what your expressions say.
>>
>> Fred
>
> --
> Les Cargill

--
Les Cargill

Fred Marshall wrote:
> On 4/1/2012 8:57 AM, Les Cargill wrote:
>> I'm not sure what it's called - the "power of two method?"
>
> Well, I don't hardly use such fancy expressions; only N+M-1 is the
> minimum.

Correct me if I am wrong, but I believe that both FFT-objects
must be of the same order...

> You can't go wrong with that.

I'll try N+M+1 and see if it works.

> I guess that my N (the number of samples in a sequence) is your n+1, etc.
> Then, if you must have length a power of 2, just pick it to be greater
> than the minimum.
> Of course, that's what your expressions say.
>
> Fred

--
Les Cargill

On 3/31/2012 11:05 PM, robert bristow-johnson wrote:
> get linear convolution out of a circular convolving mechanism (which is
> what you get with an FFT)?  the only methods i know of are overlap-add
> (OLA) or overlap-save (OLS).

Only if you're streaming.  Otherwise just make the arrays large enough 
with zero padding.  Looks like that's what Les did.

Fred

On 4/1/2012 8:57 AM, Les Cargill wrote:
> I'm not sure what it's called - the "power of two method?"

Well, I don't hardly use such fancy expressions; only N+M-1 is the 
minimum.  You can't go wrong with that.
I guess that my N (the number of samples in a sequence) is your n+1, etc.
Then, if you must have length a power of 2, just pick it to be greater 
than the minimum.
Of course, that's what your expressions say.

Fred

robert bristow-johnson wrote:
> On 4/1/12 12:02 AM, Les Cargill wrote:
>>
>> Yay! It may not seem that you helped, but you guys did.
>>
>> Octave helped, too. Nice to have a known-good implementation to
>> compare to.
>>
>> Multiplication, as it turns out, is multiplication.
>>
>
> so Les, what did you do to get linear convolution out of a circular
> convolving mechanism (which is what you get with an FFT)? the only
> methods i know of are overlap-add (OLA) or overlap-save (OLS).
>

I'm not sure what it's called - the "power of two method?"

The FFT for both the input data array and the convolution
kernel were dimensioned to be the next power of two up:

D = (n+1) + (m+1) - 1
N = 2 ^ ceil(log2(D))

So if n=2, m=2:
D = (3+3)-1 = 5
ceil(log2(5)) = 3
N = 8

So in the trivial [ 10 10 ] x [ 10 10 ] case,
the vectors to be fft'd would both be:
[ 10 10 0 0 0 0 0 0 ] ( the real parts, anyway )

I picked apart fftfilt.m from Octave...  I suppose
that's cheating, but ... it works :)

The main thing was going back and enforcing better code
hygiene and rigor....

> Phil mentioned this and Dilip aptly recognized that i would resonate
> quickly to the issue (adapting a tool that is circular to do a job that
> is linear). so i am curious about what you did with that.
>

I'll tackle OLA/OLS later on. I think I understand it, but
need to know if you can "reset" a plan in FFTW ( I think
you can ). It then becomes an exercise in buffer slinging.

Small steps. This isn't "for" anything production, just
trying to get to where I can have a feel for the  way
this works.

--
Les Cargill

On 4/1/12 12:02 AM, Les Cargill wrote:
>
> Yay! It may not seem that you helped, but you guys did.
>
> Octave helped, too. Nice to have a known-good implementation to compare to.
>
> Multiplication, as it turns out, is multiplication.
>

so Les, what did you do to get linear convolution out of a circular 
convolving mechanism (which is what you get with an FFT)?  the only 
methods i know of are overlap-add (OLA) or overlap-save (OLS).

Phil mentioned this and Dilip aptly recognized that i would resonate 
quickly to the issue (adapting a tool that is circular to do a job that 
is linear).  so i am curious about what you did with that.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."