Fast Fourier transform: Difference between revisions
Content added Content deleted
Line 984: | Line 984: | ||
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 *(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] = { |
def fft(f: List[Complex]): List[Complex] = { |
||
import Stream._ |
|||
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!") |
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 { |
f.size match { |