From: Christian Szegedy <szegedy@...>
Date: 2002-04-20T00:09:08+09:00
Subject: Ruby golf (FFT)  Was: Freshmeat article about Ruby

Jack Herrington wrote:


> Next time, I think I will use a Fast Fourier Transform algorithm as the
> example just to really bake your noodle.  Try golfing with that! (Without a
> call to a library function.) ;-)


I start the golf game:

(The function fft modifies the vals array in place.
  It must hold 2**n complex numbers.)

require "complex"

def fft(vals,n)
   size = 2**n
   j=0
   vals.map { |x| x/Math.sqrt(size) }
   0.upto(size-1) do |i|
     vals[j],vals[i] = vals[i],vals[j] if i<=j
     m = size/2
     while (j>=m && m>1) do
       j-=m; m/=2
     end
     j+=m
   end
   k=1
   while(k<size)
     incr=2*k
     mul=Complex.polar(1,Math::PI/k)
     w=Complex.new(1)
     0.upto(k-1) do |i|
       i.step(size-1,incr) do |j|
         tmp=vals[j+k]*w
         vals[j+k],vals[j]=vals[j]-tmp,vals[j]+tmp
       end
       w *= mul;
     end
     k=incr
   end
end