From: David Alan Black <dblack@...>
Date: 2002-04-20T01:11:54+09:00
Subject: Re: Ruby golf (FFT)  Was: Freshmeat article about Ruby

Hello --

On Sat, 20 Apr 2002, Christian Szegedy wrote:

> I start the golf game:

I highly recommend including the following disclaimer in every
golf-related post:

  DISCLAIMER: I do not believe that reducing code to the
  smallest possible size is always or even usually a good
  idea.  However, I tend to learn a lot about Ruby from
  this kind of exercise, and that's why I do it.

:-)

> (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) }

Shouldn't that be map! ?  Otherwise the result gets thrown away.

Anyway, here's some compression.  Another disclaimer: I have no idea
what your code does (due to my ignorance, not the code).  So this is a
very abstract golf game for me :-)

  def fft(v,n)
     s,j=2**n,0
     v.map!{|x|x/Math.sqrt(s)}
     0.upto(s-1){|i|
       v[j],v[i]=v[i],v[j] if i<=j
       m=s/2
       j-=m&&m/=2 while j>=m&&m>1
       j+=m}
     k=1
     while(k<s)
       n,m,w=2*k,Complex.polar(1,Math::PI/k),Complex.new(1)
       0.upto(k-1){|i|
	 i.step(s-1,n){|j|
	   x=j+k
	   t=v[x]*w
	   v[x],v[j]=v[j]-t,v[j]+t}
	 w*=m}
       k=n
     end
  end


David

-- 
David Alan Black
home: dblack@candle.superlink.net
work: blackdav@shu.edu
Web:  http://pirate.shu.edu/~blackdav