for your info: ch. 11 mbe: fast fourier transforms

On Sun, May 3, 2009 at 3:09 PM, dlakelan <dlakelan at street-artists.org> wrote:

> Robert Dodier wrote:
>> Yes, I saw that. After trying some examples, I guess I don't understand
>> what you're getting at. The results seem to match the definition of the
>> transform stated in the documentation:
>>
>>  y[k]: (1/n) sum (x[j] exp (-2 %i %pi j k / n), j, 0, n-1)
>>
>> i.e. the k'th element is associated with frequency k*2*%pi/n.
>
> If this were true, then when you multiply all coefficients by %i*k*2*%pi/n
> and take the inverse you should get the derivative. In fact you need to
> multiply by a different function that looks like a sawtooth. It ramps up to
> a maximum, then goes to zero, then goes negative maximum and linear ramps up
> towards zero again, as follows.
>
> derivcoefs:float(append(makelist(pi*k,k,0,n/2-1),[0],makelist(pi*k,k,1,n/2-1)-pi*n/2)),
> /* tricky the way the frequencies correspond to k */

Well, I dunno. The computed results match the stated definition --
I've verified that directly. We could pick a different definition, I guess,
if it could make the results more useful or comprehensible.

The coefficients for cos and sin terms are different from those for
complex exp -- is that what you have in mind?
There is some verbiage about that in the fft documentation; I didn't
check whether the formulas are exactly right (they look right).

For the record, Maxima's fft definition is the same as Octave's
except for a constant factor 1/n (Maxima has it, Octave doesn't).
I tried R as well, I forget how it turned out. I don't have other
packages to try.

best

Robert Dodier