From: Pit Capitain <pit@...>
Date: 2002-04-20T01:07:53+09:00
Subject: Re: Ruby golf (FFT)  Was: Freshmeat article about Ruby

On 20 Apr 2002, at 0:09, Christian Szegedy started the golf game 
for function fft

I know nothing about FFT and didn't analyze your implementation, 
but if you gsub!( /0.upto\((.*?)-1\)/, '\1.times' ) you save 4 
characters. Here's the modified version:

(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) }
   size.times 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


Regards,
Pit