Anonymous user
Fast Fourier transform: Difference between revisions
→{{header|Scala}}
Line 976:
=={{header|Scala}}==
{{works with|Scala|2.9.1}}
</lang>▼
<lang Scala>object FFT extends App {
import scala.math._
case class Complex(re: Double, im: Double = 0.0) {
def +(x: Complex): Complex = Complex((this.re+x.re),(this.im+x.im))
def -(x: Complex): Complex = Complex((this.re-x.re),(this.im-x.im))
def *(x: Complex): Complex = Complex(this.re*x.re-this.im*x.im,this.re*x.im+this.im*x.re)
def r = sqrt(re*re+im*im)
def phi = acos(re/r)
def cis = Complex(cos(phi),sin(phi))
}
def fft(f: List[Complex]): List[Complex] = {
require((f.size==0)||(from(0) map {x=>pow(2,x).toInt}).takeWhile(_<2*f.size).toList.exists(_==f.size)==true,"list size "+f.size+" not allowed!")
f.size match {
case 0 => Nil
case 1 => f
case n => {
val cis: Double => Complex = phi => Complex(cos(phi),sin(phi))
val e = fft(f.zipWithIndex.filter(_._2%2==0).map(_._1))
val o = fft(f.zipWithIndex.filter(_._2%2!=0).map(_._1))
import scala.collection.mutable.ListBuffer
val lb = new ListBuffer[Pair[Int, Complex]]()
for (k <- 0 to n/2-1) {
lb += Pair(k,e(k)+o(k)*cis(-2*Pi*k/n))
lb += Pair(k+n/2,e(k)-o(k)*cis(-2*Pi*k/n))
}
lb.toList.sortWith((x,y)=>x._1<y._1).map(_._2)
}
}
}
fft(List(Complex(1),Complex(1),Complex(1),Complex(1),Complex(0),Complex(0),Complex(0),Complex(0))).foreach(println)
▲}</lang>
Output:
<pre>Complex(4.0,0.0)
Complex(1.0,-2.414213562373095)
Complex(0.0,0.0)
Complex(1.0,-0.4142135623730949)
Complex(0.0,0.0)
Complex(0.9999999999999999,0.4142135623730949)
Complex(0.0,0.0)
Complex(0.9999999999999997,2.414213562373095)</pre>
=={{header|Tcl}}==
| |||