John Randall wrote: > This is one of the ideas behind the discrete Fourier transform.
I realize I was not totally coherent on my prior explanation. Here's another shot. For a given set of distinct points, polynomial evaluation and polynomial interpolation are inverses. require 'numeric' L=:] %. [ ^/ [: i. [: # [ NB. Lagrange interpolation a=:1 3 4 5 b=:3 1 _3 1 c=:a p.~ b d=:a L c >./|b-d 1.98952e_13 This shows that a&L is the inverse of a&p.~ . The Fourier transform F and its inverse IF are examples of this with a specific choice of a, namely the roots of unity. NB. roots of unity ru=:r.@:(_2p1&*)@:(i. % ])@:# F =:clean@(p. ru) IF =:clean@(L~ ru) b-:F IF b 1 b-:IF F b 1 The inverse transform can be expressed in terms of evaluation: IF2=:# %~ clean@(p. [EMAIL PROTECTED]) b-:F IF2 b 1 b-:IF2 F b 1 Best wishes, John ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
