Mercurial > hg > js-dsp-test

diff fft/nayuki/fft-test.html @ 0:d7c216b6a84f
Pull in some FFT implementations for test
author: Chris Cannam
date: Thu, 01 Oct 2015 15:50:58 +0100
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/fft/nayuki/fft-test.html	Thu Oct 01 15:50:58 2015 +0100
@@ -0,0 +1,180 @@
+<!--
+  - FFT and convolution test (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.
+  -->
+<!DOCTYPE html>
+<html>
+<head>
+<meta charset="UTF-8">
+<title>FFT and convolution test (JavaScript)</title>
+</head>
+<body>
+<script src="fft.js" type="application/javascript"></script>
+<pre>
+<script>
+/* Main and test functions */
+
+function main() {
+    // Test power-of-2 size FFTs
+    for (var i = 0; i <= 12; i++)
+        testFft(1 << i);
+    
+    // Test small size FFTs
+    for (var i = 0; i < 30; i++)
+        testFft(i);
+    
+    // Test diverse size FFTs
+    var prev = 0;
+    for (var i = 0; i <= 100; i++) {
+        var n = Math.round(Math.pow(1500, i / 100.0));
+        if (n > prev) {
+            testFft(n);
+            prev = n;
+        }
+    }
+    
+    // Test power-of-2 size convolutions
+    for (var i = 0; i <= 12; i++)
+        testConvolution(1 << i);
+    
+    // Test diverse size convolutions
+    prev = 0;
+    for (var i = 0; i <= 100; i++) {
+        var n = Math.round(Math.pow(1500, i / 100.0));
+        if (n > prev) {
+            testConvolution(n);
+            prev = n;
+        }
+    }
+    
+    document.write("\nMax log err = " + maxLogError.toFixed(1));
+    document.write("\nTest " + (maxLogError < -10 ? "passed" : "failed"));
+}
+
+
+function testFft(size) {
+    var inputreal = randomReals(size);
+    var inputimag = randomReals(size);
+    
+    var refoutreal = new Array(size);
+    var refoutimag = new Array(size);
+    naiveDft(inputreal, inputimag, refoutreal, refoutimag, false);
+    
+    var actualoutreal = inputreal.slice(0);
+    var actualoutimag = inputimag.slice(0);
+    transform(actualoutreal, actualoutimag);
+    
+    document.write("fftsize=" + size + "  logerr=" + log10RmsErr(refoutreal, refoutimag, actualoutreal, actualoutimag).toFixed(1) + "\n");
+}
+
+
+function testConvolution(size) {
+    var input0real = randomReals(size);
+    var input0imag = randomReals(size);
+    
+    var input1real = randomReals(size);
+    var input1imag = randomReals(size);
+    
+    var refoutreal = new Array(size);
+    var refoutimag = new Array(size);
+    naiveConvolve(input0real, input0imag, input1real, input1imag, refoutreal, refoutimag);
+    
+    var actualoutreal = new Array(size);
+    var actualoutimag = new Array(size);
+    convolveComplex(input0real, input0imag, input1real, input1imag, actualoutreal, actualoutimag);
+    
+    document.write("convsize=" + size + "  logerr=" + log10RmsErr(refoutreal, refoutimag, actualoutreal, actualoutimag).toFixed(1) + "\n");
+}
+
+
+/* Naive reference computation functions */
+
+function naiveDft(inreal, inimag, outreal, outimag, inverse) {
+    if (inreal.length != inimag.length || inreal.length != outreal.length || outreal.length != outimag.length)
+        throw "Mismatched lengths";
+    
+    var n = inreal.length;
+    var coef = (inverse ? 2 : -2) * Math.PI;
+    for (var k = 0; k < n; k++) {  // For each output element
+        var sumreal = 0;
+        var sumimag = 0;
+        for (var t = 0; t < n; t++) {  // For each input element
+            var angle = coef * (t * k % n) / n;  // This is more accurate than t * k
+            sumreal += inreal[t]*Math.cos(angle) - inimag[t]*Math.sin(angle);
+            sumimag += inreal[t]*Math.sin(angle) + inimag[t]*Math.cos(angle);
+        }
+        outreal[k] = sumreal;
+        outimag[k] = sumimag;
+    }
+}
+
+
+function naiveConvolve(xreal, ximag, yreal, yimag, outreal, outimag) {
+    if (xreal.length != ximag.length || xreal.length != yreal.length || yreal.length != yimag.length || xreal.length != outreal.length || outreal.length != outimag.length)
+        throw "Mismatched lengths";
+    
+    var n = xreal.length;
+    for (var i = 0; i < n; i++) {
+        var sumreal = 0;
+        var sumimag = 0;
+        for (var j = 0; j < n; j++) {
+            var k = (i - j + n) % n;
+            sumreal += xreal[k] * yreal[j] - ximag[k] * yimag[j];
+            sumimag += xreal[k] * yimag[j] + ximag[k] * yreal[j];
+        }
+        outreal[i] = sumreal;
+        outimag[i] = sumimag;
+    }
+}
+
+
+/* Utility functions */
+
+var maxLogError = Number.NEGATIVE_INFINITY;
+
+function log10RmsErr(xreal, ximag, yreal, yimag) {
+    if (xreal.length != ximag.length || xreal.length != yreal.length || yreal.length != yimag.length)
+        throw "Mismatched lengths";
+    
+    var err = 0;
+    for (var i = 0; i < xreal.length; i++)
+        err += (xreal[i] - yreal[i]) * (xreal[i] - yreal[i]) + (ximag[i] - yimag[i]) * (ximag[i] - yimag[i]);
+    err = Math.sqrt(err / Math.max(xreal.length, 1));  // Now this is a root mean square (RMS) error
+    err = err > 0 ? Math.log(err) / Math.log(10) : -99;
+    maxLogError = Math.max(err, maxLogError);
+    return err;
+}
+
+
+function randomReals(size) {
+    var result = new Array(size);
+    for (var i = 0; i < result.length; i++)
+        result[i] = Math.random() * 2 - 1;
+    return result;
+}
+
+
+main();
+</script>
+</pre>
+</body>
+</html>
author	Chris Cannam
date	Thu, 01 Oct 2015 15:50:58 +0100
parents
children