changeset 17:9619d2da67c2

Add object version of Nayuki code

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/fft/nayuki-obj/fft.js	Mon Oct 05 15:37:41 2015 +0100
@@ -0,0 +1,92 @@
+/* 
+ * Free FFT and convolution (JavaScript)
+ * 
+ * Copyright (c) 2014 Project Nayuki
+ * http://www.nayuki.io/page/free-small-fft-in-multiple-languages
+ * 
+ * (MIT License)
+ * Permission is hereby granted, free of charge, to any person obtaining a copy of
+ * this software and associated documentation files (the "Software"), to deal in
+ * the Software without restriction, including without limitation the rights to
+ * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
+ * the Software, and to permit persons to whom the Software is furnished to do so,
+ * subject to the following conditions:
+ * - The above copyright notice and this permission notice shall be included in
+ *   all copies or substantial portions of the Software.
+ * - The Software is provided "as is", without warranty of any kind, express or
+ *   implied, including but not limited to the warranties of merchantability,
+ *   fitness for a particular purpose and noninfringement. In no event shall the
+ *   authors or copyright holders be liable for any claim, damages or other
+ *   liability, whether in an action of contract, tort or otherwise, arising from,
+ *   out of or in connection with the Software or the use or other dealings in the
+ *   Software.
+ */
+
+"use strict";
+
+function FFTNayuki(n) {
+    this.n = n;
+    this.levels = -1;
+
+    for (var i = 0; i < 32; i++) {
+        if (1 << i == n) {
+            this.levels = i;  // Equal to log2(n)
+	}
+    }
+    if (this.levels == -1) {
+        throw "Length is not a power of 2";
+    }
+
+    this.cosTable = new Array(n / 2);
+    this.sinTable = new Array(n / 2);
+    for (var i = 0; i < n / 2; i++) {
+        this.cosTable[i] = Math.cos(2 * Math.PI * i / n);
+        this.sinTable[i] = Math.sin(2 * Math.PI * i / n);
+    }
+
+    this.forward = function(real, imag) {
+	
+	for (var i = 0; i < n; i++) {
+            var j = reverseBits(i, this.levels);
+            if (j > i) {
+		var temp = real[i];
+		real[i] = real[j];
+		real[j] = temp;
+		temp = imag[i];
+		imag[i] = imag[j];
+		imag[j] = temp;
+            }
+	}
+    
+	for (var size = 2; size <= n; size *= 2) {
+            var halfsize = size / 2;
+            var tablestep = n / size;
+            for (var i = 0; i < n; i += size) {
+		for (var j = i, k = 0; j < i + halfsize; j++, k += tablestep) {
+                    var tpre =  real[j+halfsize] * this.cosTable[k] +
+			        imag[j+halfsize] * this.sinTable[k];
+                    var tpim = -real[j+halfsize] * this.sinTable[k] +
+			        imag[j+halfsize] * this.cosTable[k];
+                    real[j + halfsize] = real[j] - tpre;
+                    imag[j + halfsize] = imag[j] - tpim;
+                    real[j] += tpre;
+                    imag[j] += tpim;
+		}
+            }
+	}
+    
+	function reverseBits(x, bits) {
+            var y = 0;
+            for (var i = 0; i < bits; i++) {
+		y = (y << 1) | (x & 1);
+		x >>>= 1;
+            }
+            return y;
+	}
+    }
+
+    this.inverse = function(real, imag) {
+	forward(imag, real);
+    }
+}
+

--- a/fft/test.html	Mon Oct 05 15:06:39 2015 +0100
+++ b/fft/test.html	Mon Oct 05 15:37:41 2015 +0100
@@ -10,6 +10,7 @@
   </style>
   
   <script src="nayuki/fft.js"></script>
+  <script src="nayuki-obj/fft.js"></script>
   <script src="fft.js/lib/complex.js"></script>
   <script src="jsfft/lib/complex_array.js"></script>
   <script src="jsfft/lib/fft.js"></script>
@@ -32,7 +33,9 @@
     </tr>
     <tr>
       <td>Nayuki</td><td id="nayuki-result"></td><td id="nayuki-1"></td><td id="nayuki-2"></td><td id="nayuki-itr"></td>
-    </tr><tr>
+    </tr><tr> 
+      <td>Nayuki (obj)</td><td id="nayukiobj-result"></td><td id="nayukiobj-1"></td><td id="nayukiobj-2"></td><td id="nayukiobj-itr"></td>
+    </tr><tr> 
       <td>Nockert</td><td id="nockert-result"></td><td id="nockert-1"></td><td id="nockert-2"></td><td id="nockert-itr"></td>
     </tr><tr>
       <td>Dntj</td><td id="dntj-result"></td><td id="dntj-1"></td><td id="dntj-2"></td><td id="dntj-itr"></td>
@@ -47,8 +50,9 @@
 
   <ul>
     <li><b>Nayuki</b>: in-place single-precision complex-complex</li>
+    <li><b>Nayuki (obj)</b>: Nayuki with the sin/cos tables pre-calculated on object construction</li>
     <li><b>Nockert</b>: double-precision real-complex</li>
-    <li><b>Nayuki</b>: double-precision complex-complex. Forward
+    <li><b>Dntj</b>: double-precision complex-complex. Forward
     transform is scaled and I've scaled it back again here, which may
     introduce rounding error.</li>
     <li><b>Cross</b>: double-precision real-complex in C, compiled

--- a/fft/test.js	Mon Oct 05 15:06:39 2015 +0100
+++ b/fft/test.js	Mon Oct 05 15:37:41 2015 +0100
@@ -77,6 +77,33 @@
     report("nayuki", start, middle, end, total);
 }
 
+function testNayukiObj() {
+
+    var fft = new FFTNayuki(size);
+    
+    var start = performance.now();
+    var middle = start;
+    var end = start;
+
+    var total = 0.0;
+
+    for (var i = 0; i < 2*iterations; ++i) {
+	if (i == iterations) {
+	    middle = performance.now();
+	}
+	var real = inputReals(size);
+	var imag = zeroReals(size);
+	fft.forward(real, imag);
+	for (var j = 0; j < size; ++j) {
+	    total += Math.sqrt(real[j] * real[j] + imag[j] * imag[j]);
+	}
+    }
+
+    var end = performance.now();
+
+    report("nayukiobj", start, middle, end, total);
+}
+
 function testNockert() {
     
     var fft = new FFT.complex(size, false);
@@ -192,7 +219,7 @@
     fft.discard();
 }
 
-var tests = [ testNayuki, testNockert, testDntj, testCross, testKissFFT ];
+var tests = [ testNayuki, testNayukiObj, testNockert, testDntj, testCross, testKissFFT ];
 var nextTest = 0;
 var interval;