drom / fourier

:wavy_dash: Fourier transform in JavaScript

Fourier

Pure JavaScript library discrete transforms, including Discrete Fourier Transform (DFT); It's fast, inverse, and special forms.

Use

Node.js

npm i fourier

var fourier = require('fourier');

Browser

<script src="https://cdn.jsdelivr.net/npm/fourier/fourier.min.js"></script>

Functions

FFT custom

Fast Fourier transform (FFT). Cooley–Tukey algorithm. in-place. Radix-2, Decimation in Time (DIT).

One function for each data type, vector size and coding style

fourier.custom.fft_<type>_<size>_<style>

• data type: f32 or f64
• vector size: 16, 32, ... 1048576
• coding style: 'raw' or asm

example:

// Init
var stdlib = {
    Math: Math,
    Float32Array: Float32Array,
    Float64Array: Float64Array
};

// Create heap for the fft data and twiddle factors
var heap = fourier.custom.alloc(65536, 3);

// Create instance of FFT runner
var fft_f64_65536_asm_runner = fourier.custom.fft_f64_65536_asm(stdlib, null, heap);

// Init twiddle factors
fft_f64_65536_asm_runner.init();

// Run transformations
fft_f64_65536_asm_runner.transform();

Other

fourier.dft(realArray, imagArray); // ⇒ [realArray, imagArray]

$$\large X_k=\sum_{n=0}^{N-1}x_n\cdot e^{-i 2 \pi k n/N}$$

fourier.idft(realArray, imagArray); // ⇒ [realArray, imagArray]

$$\large x_n=\frac{1}{N}\sum_{k=0}^{N-1}X_k\cdot e^{i 2 \pi kn/N}$$

Testing

npm test

License

MIT LICENSE.

fourier's Issues

Initialization

Greetings, @drom !

One question: can I process different data heaps, using the same custom FFT object? Or is each object a "one shot" processor?

better DIT/DIF Radix pictures

radix 4 ,8, 16 version

Some references:
БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ МАЛЫХ ПОРЯДКОВ, О. В. Просеков

Report viewer

JSON -> Graph D3? HTML? SVG?

performance

Current FFT implementation uses classic Decimation in Time, Radix-2, in-place algorithm, which is far from being the best in class. I am comparing Float64, Float32, and Array implementations on three V8 based engines.

Raw benchmarks for (node 0.12.2, 0.10.38; iojs 1.6.3, FF36) can be found in Travis logs here: https://travis-ci.org/drom/fourier

Here are some charts I have crafted from the results on my Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz. most of points are less then ±5% variation:

Using FFT Benchmark Methodology from here: http://www.fftw.org/speed/method.html

Here is the chart from http://www.fftw.org/speed/CoreDuo-3.0GHz-icc64/ :
Which includes some state of art FFT implementations in C.

Double precision:

Single precision:

Obviously this just the beginning and we are x20 slower then the best;
and results are different with different version of V8 engine;
and because of dynamic nature of modern JavaScript run-time speed may suddenly change.

In my list to try:

• higher radix algorithms (4,8,16,...)
• better data / operation flow organisation.
• data type casting techniques like asm.js
• SIMD extensions: https://github.com/johnmccutchan/ecmascript_simd

Any other ideas are welcome!

WebAssembly version

provide precompiled template

SIMD.js version

https://github.com/tc39/ecmascript_simd