fft.js

fft.js copied to clipboard

Hi there 👋 While experimenting with your library, I encountered an issue where the output would be different (to numpy's implementation) by a single number. I would greatly appreciate any advice on the matter, thanks!

Reproduction:

import FFT from 'https://cdn.jsdelivr.net/npm/[email protected]/+esm'

const input = new Float32Array(8);
input.fill(1);
const f = new FFT(input.length);

const out = f.createComplexArray();
const a = performance.now();
f.realTransform(out, input);
const b = performance.now();
console.log(out)
// [8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0]
//                                      ^
//                                  incorrect

JSFiddle link (including a comparison with another library, which matches the numpy implementation). https://jsfiddle.net/9ex3bkzt/

If it helps debug, it does work for input size = 4:

import FFT from 'https://cdn.jsdelivr.net/npm/[email protected]/+esm'

const input = new Float32Array(4);
input.fill(1);
const f = new FFT(input.length);

const out = f.createComplexArray();
const a = performance.now();
f.realTransform(out, input);
const b = performance.now();
console.log(b-a, out)
// [4, 0, 0, 0, 0, 0, 0, 0]
// correct

Further investigation shows this only occurs for realTransform:

import FFT from 'https://cdn.jsdelivr.net/npm/[email protected]/+esm'

const input = new Float32Array([1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]);
const f = new FFT(input.length/2);

const out = f.createComplexArray();
const a = performance.now();
f.transform(out, input);
const b = performance.now();
console.log(b-a, Array.from(out))
// [8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Also, if you replace this block of code: https://github.com/indutny/fft.js/blob/4a18cf88fcdbd4ad5acca6eaea06a0b462047835/lib/fft.js#L339-L439

with this block of code: https://github.com/indutny/fft.js/blob/4a18cf88fcdbd4ad5acca6eaea06a0b462047835/lib/fft.js#L151-L222

The output is as expected, so it seems to be an error in the optimization.

I think you have to call f.completeSpectrum(out); as mentioned in the readme, then it correctly sets the values in the right part of the array.

Oh wow, that was it... thanks so much @daniele-roncaglioni!