indutny/fft.js

The fastest JS Radix-4/Radix-2 FFT implementation

fft.js's Issues

create complex array

I have trouble finding public API for creating complex array filling Real and Imaginary parts.
f.toComplexArray(input, arr) seems to take real input array as argument.
Do I miss something?

Benchmark against other libraries

This library is most likely one of the fastest implementations of Cooley-Tukey FFT algorithm. It would be interesting to see how it compares to other JS implementations.

Real Number FFT

My input data has all real numbers and I am trying to do a realTransform on the input. The docs have an inconsistency, and I'm not sure which part of the output array to look at to get the real value output.

1. In the Usage section, the docs say "realTransform fills just the left half of the out"
2. In the realTransform section, the docs say "perform FFT transformation on it, filling the left half of the output with complex values "

If I only want to look at the real (non-imaginary) output values, do I look at the left half or the right half of the output array?

Thank you!

No example of expected output

There is no example of expected output. I'm pretty sure the following is wrong, but I have nothing to compare it to.

-2.7350754211020335e+37,
0,
-2.74791941673057e+37,
1.7924465771967297e+35,
-2.746905263214394e+37,
3.543421938934245e+35,
-2.745614364226398e+37,
5.223895408963396e+35,
-2.744560770814082e+37,
6.823236792035908e+35,
-2.7445039397166733e+37,
8.335100408925063e+35,
-2.750007665709478e+37,
9.503987944167054e+35,
-2.7362066697780583e+37,
1.2031876673943803e+36,
-2.740032083855111e+37,
1.346091445541995e+36,
-2.7410313849063947e+37,
1.5144149620484113e+36,
-2.741017338984276e+37,
1.6922964485080548e+36,
-2.7399726599251418e+37,
1.8758977693295546e+36....

2D FFT

What is the most efficient way to perform a 2D FFT using this library?

Incorrect output for `transform` function

Related to #25, I am not always getting the correct output from the regular fft.transform function. See this example:

let fft = new FFT(8)
let out = fft.createComplexArray()
fft.transform(out, [1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0])
console.log(out)
// [36, 0, -4, 9.65685424949238, -4, 4, -4, 1.6568542494923797, -4, 0, -3.9999999999999996, -1.6568542494923797, -4, -4, -3.999999999999999, -9.65685424949238]

I believe the result should be:
[36, 0, -4, 12, -4, 4, -4, 4, -4, 0, -4, -4, -4, -4, -4, -12].

ES5 version

I see that library uses const, let, Array.fill constructs that makes it non ES5 compatible.
Is any performance (other) reasons not to use just plain ES5?
In our application we are still running ES5.1 compatible iojs-1.2.1 run-time.

Incorrect output for `realTransform` (size >4)

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/

Entire output is NaN

Hey there, I'm having a bit of an odd issue when running the realTransform on accelerometer data: the data looks like [-0.338591208,-0.785074071,-1.147213186,0.221686656,...], and my code is as follows:

function fftData(realData) {
  const fftableData = [...] // data array of length 4096

  const f = new FFT(fftableData.length);
  const fftData = f.createComplexArray();
  f.realTransform(fftData, fftableData);
  const output = new Array(fftableData.length);
  f.fromComplexArray(fftData, output);
  return output;
}

Here's the data-- it's just a JSON file inside a ZIP, because GitHub doesn't allow JSON uploads.

However, output is always full of NaN values-- no real values in sight. Any ideas what's going on?

Window Functions

Do you plan to add window functions? If so, the following document provides a really good description and a lot of windows https://holometer.fnal.gov/GH_FFT.pdf.

number-theoretic transform?

hey @indutny,

incredible work as always.

I'm wondering if you've considered implementing the number-theoretic transform---i.e. the FFT in a prime field F_q which admits high-order 2-adic roots of unity. There's also a version where the input "signal" is a vector of points on an elliptic curve E(F_p) of order q.

For example, consider the elliptic curve altbn_128, used in Ethereum precompiles---see here for an implementation built off your elliptic package. See herumi / ate-pairing for more details (it's called "CurveSNARK" there).

The order q of this curve is such that the field F_q admits 2^n-order modular-multiplicative roots of unity for n as high as 28. Thus one can take FFTs of power-of-2-length vectors consisting either of elements of F_q or of curve points.

Of course this isn't hard to implement manually but I'd enjoy your optimizations. Also happy to contribute if you'd be interested in going this direction.

An example would be nice...

I have an array of 512 different amplitude values,
the values are sampled 60 times per second.
How can I know the main (stronger) frequency?

As of now I did:
f=new FFT(512);
input=f.toComplexArray(MYARRAY);
out=Array(1024);
f.transform(out,input);

what then?

Try Split-Radix FFT

See: https://en.wikipedia.org/wiki/Split-radix_FFT_algorithm

This algorithm is probably faster than radix-4 that we use right now.