Scala example source code file (fft.scala)

This example Scala source code file (fft.scala) is included in the DevDaily.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Java - Scala tags/keywords

array, array, boxed, boxed, complex, complex, double, fft, int, int, long, processing, test

The Scala fft.scala source code

/*
 * http://local.wasp.uwa.edu.au/~pbourke/miscellaneous/dft/
   Modification of Paul Bourkes FFT code by Peter Cusack 
   to utilise the Microsoft complex type.

   This computes an in-place complex-to-complex FFT 
   x and y are the real and imaginary arrays of 2^m points.
   dir =  1 gives forward transform
   dir = -1 gives reverse transform 
*/

import Math.{sqrt, pow}

/** Test that specialization handles tuples. Perform FFT transformation
 *  using pairs to represent complex numbers.
 */
object Test  {
  type Complex = (Double, Double)

  def swap(x: Array[Complex], i: Int, j: Int) {
    val tmp = x(i)
    x(i) = x(j)
    x(j) = tmp
  }

  def times(x: Complex, y: Complex): Complex = 
    (x._1 * y._1 - x._2 * y._2, x._1 * y._2 + x._2 * y._1)
    
  def div(x: Complex, y: Complex): Complex = {
    val num = pow(y._1, 2) + pow(y._2, 2)
    ((x._1 * y._1 + x._2 * y._2)/num,
     (x._2 * y._1 - x._1 * y._2)/num)
  }

  def div(x: Complex, y: Long) = 
    (x._1 / y, x._2 / y)

  def add(x: Complex, y: Complex) = 
    (x._1 + y._1, x._2 + y._2)

  def minus(x: Complex, y: Complex) =
    (x._1 - y._1, x._2 - y._2)

  def FFT(dir: Int, m: Long, x: Array[(Double, Double)]) {
    var i, i1, i2,j, k, l, l1, l2, n = 0l
//   complex <double> tx, t1, u, c;
    var tx, t1, u, c = (0.0, 0.0)

   /*Calculate the number of points */
   n = 1
   for (i <- 0l until m) 
      n <<= 1   

   /* Do the bit reversal */
   i2 = n >> 1
   j = 0

   for (i <- 0l until (n - 1)) {
      if (i < j)
         swap(x, i.toInt, j.toInt);

      k = i2;

      while (k <= j) {
         j -= k;
         k >>= 1;
      }

      j += k;
   }

   /* Compute the FFT */
   // c.real(-1.0);
   // c.imag(0.0);
   c = (-1.0, 0.0)
   l2 = 1
   for (l <- 0l until m) {
     l1 = l2
     l2 <<= 1;
      // u.real(1.0);
      // u.imag(0.0);
     u = (1.0, 0.0)

     for (j <- 0l until l1) {
       for (i <- j.until(n, l2)) {
         i1 = i + l1;
         t1 = times(u, x(i1.toInt))
         x(i1.toInt) = minus(x(i.toInt), t1) 
         x(i.toInt) = add(x(i.toInt), t1)
       }

       u = times(u,  c)
    }

     // c.imag(sqrt((1.0 - c.real()) / 2.0));
     c = (c._1, sqrt( (1.0 - c._1) / 2.0 ))
     // if (dir == 1)
     //    c.imag(-c.imag());
     if (dir == 1) 
       c = (c._1, -c._2)

      // c.real(sqrt((1.0 + c.real()) / 2.0));
      c = (sqrt( (1.0 + c._1) / 2.0), c._2)
   }

   /* Scaling for forward transform */
   if (dir == 1) {
     for (i <- 0l until n)
       x(i.toInt) = div(x(i.toInt), n)      
   }   
  }

  def run() {
    FFT(1, 16, data)
  }
  var data: Array[Complex] = null

  def inputFileName = {
    val cwd = System.getProperty("partest.cwd")
    if (cwd ne null) cwd + java.io.File.separator + "input2.txt"
    else "input2.txt"
  }

  def setUp {
//    print("Loading from %s.. ".format(inputFileName))
    val f = io.Source.fromFile(inputFileName)
    val lines = f.getLines
    val n = lines.next.toInt
    data = new Array[Complex](n)
    var i = 0
    for (line <- lines if line != "") {
      val pair = line.trim.split(" ")
      data(i) = (pair(0).trim.toDouble, pair(1).trim.toDouble)
      i += 1
    }
//    println("[loaded]")
    println("Processing " + n + " items")
  }

  def main(args: Array[String]) {
    setUp
    run()

    println("Boxed doubles: " + runtime.BoxesRunTime.doubleBoxCount)
    println("Boxed ints: " + runtime.BoxesRunTime.integerBoxCount)
    println("Boxed longs: " + runtime.BoxesRunTime.longBoxCount)
  }
}