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

David Alan Black wrote:


>>
>>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.

You are completely right. I tested my code with the following function
("sft" stands for slow Fourier transform) wich contains the same error...)

This function does the same, but in a quadratic running time...
(You can recognize, that I have mad the mistake here, therefore I have not
recognized this bug.

def sft(vals,n)
   size = 2**n
   vals.map { |x| x/Math.sqrt(size) }
   result = []
   mul=Complex.polar(1.0,2.0*Math::PI/size)
   mul2 = 1.0
   0.upto(size-1) do |i|
     result[i] = Complex.new(.0)
     w=Complex.new(1.0)
     0.upto(size-1) do |j|
       result[i] += vals[j]*w;
       w *= mul2
     end
     mul2 *= mul;
   end
   0.upto(size-1) do |i|
     vals[i] = result[i]
   end
end