Skip to content

Instantly share code, notes, and snippets.

@davidmweber
Created July 16, 2014 12:24
Show Gist options
  • Save davidmweber/429b8de3d568116284de to your computer and use it in GitHub Desktop.
Save davidmweber/429b8de3d568116284de to your computer and use it in GitHub Desktop.
FFT in Scala based on Rosetta Code's implementation but using Spire Complex implementation
package co.horn.services
import spire.math._
import spire.implicits._
/**
* Not the fastest FFT in the world, but we use it just for testing. Based on code from
* http://rosettacode.org/wiki/Fast_Fourier_transform#Scala
*/
object FFT extends App {
def _fft(cSeq: Seq[Complex[Float]], direction: Complex[Float], scalar: Int): Seq[Complex[Float]] = {
if (cSeq.length == 1) {
return cSeq
}
val n = cSeq.length
assume(n % 2 == 0, "The Cooley-Tukey FFT algorithm only works when the length of the input is a power of two.")
val evenOddPairs = cSeq.grouped(2).toSeq
val evens = _fft(evenOddPairs map (_(0)), direction, scalar)
val odds = _fft(evenOddPairs map (_(1)), direction, scalar)
def leftRightPair(k: Int): (Complex[Float], Complex[Float]) = {
val base = evens(k) / Complex(scalar.toFloat)
val offset = exp(direction * (pi[Complex[Float]] * Complex(k.toFloat / n.toFloat))) * odds(k) / scalar
(base + offset, base - offset)
}
val pairs = (0 until n/2) map leftRightPair
val left = pairs map (_._1)
val right = pairs map (_._2)
left ++ right
}
def forward(cSeq: Seq[Complex[Float]]): Seq[Complex[Float]] = _fft(cSeq, Complex(0.0f, 2.0f), 1)
def reverse(cSeq: Seq[Complex[Float]]): Seq[Complex[Float]] = _fft(cSeq, Complex(0.0f, -2.0f), 2)
def test() = {
val data = Seq(Complex(1.0f, 0.0f), Complex(1.0f, 0.0f), Complex(1.0f, 0.0f), Complex(1.0f, 0.0f),
Complex(0.0f, 0.0f), Complex(0.0f, 2.0f), Complex(0.0f, 0.0f), Complex(0.0f, 0.0f))
val test = FFT.reverse(FFT.forward(data))
data zip test foreach ( x => assert(abs(x._1 - x._2).real < 1e-4))
}
test()
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment