JavaScript DFT 離散傅裡葉變換依賴DFT & DFT的逆

關于 離散傅裡葉變換 DFT 以及 快速傅裡葉變換 FFT 的算法可以在 算法導論第30章 或者 其他人的部落格 裡看到。這裡不做贅述。

我們來看一種函數式的實作：

依賴

複數類

首先，建立一個複數方法類：

// complex methods

// 構造函數，預設為 
complex = (x, y) => { return { x: x || , y: y ||  }; }; 
// 從弧度構造機關複數
complex.fromAngle = (angle) => complex(Math.cos(angle), Math.sin(angle));
// 複數加複數
complex.add = (a, b) => complex(a.x + b.x, a.y + b.y);
// 複數乘複數
complex.mul = (a, b) => complex(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
// 數乘複數
complex.numMul = (n, c) => complex(n * c.x, n * c.y);
// 複數減複數
complex.minus = (a, b) => complex(a.x - b.x, a.y - b.y);
           

注意，這個複數乘複數與複數減複數是備援的：

complex.numMul = (n, c) => complex.mul(complex(n), c);
complex.minus = (a, b) => complex.add(a, complex.numMul(-, b));
           

清單重構

關于清單重構，可以參考我的另一篇博文：JavaScript 清單重構

// array restructuring
flatten = (matrix) => matrix.reduce((pre, cur) => pre.concat(cur), []);
partition = (array, n) => array.reduce((pre, cur, i) => (pre[i % n] = pre[i % n] || []).push(cur) && pre, []);
transpose = (matrix) => partition(flatten(matrix), matrix[].length);
           

DFT & DFT的逆

這裡先很不要臉地給出一行形式的代碼

傳參

目前這個函數尚不類型安全，必須要有嚴格的傳參方式才能保證不出錯。

第一個參數是一個數組：

• 其中每個元素都要有 x 與 y 這兩個屬性。
• 數組的長度是2的幂（1, 2, 4, 8, 16, …）

第二個參數是可判定真假的值，由于存在強制轉換是以不會有問題。

當第二個參數為true時，執行DFT的逆，預設為false。

測試

由于使用了ES6的文法，浏覽器的支援度查詢：Arrow Functions Supported

如果你的浏覽器支援，你可以盡情測試：

var x = [complex), complex), complex), complex)]; // 1 + 2x
var y = [complex), complex), complex), complex)]; // 3 + 4x

var rx = recursiveDFT(x);
recursiveDFT(rx, true); // almost same as x

var ry = recursiveDFT(y); 
recursiveDFT(ry, true); // almost same as y

var rc = rx.map((v, i) => complex.mul(v, ry[i]));
recursiveDFT(rc, true); // almost same as [complex(3), complex(10), complex(8), complex(0)]
           

感興趣的讀者可以自行将那一行代碼婊開看邏輯。

雖然我定義了幾個函數(complex方法類、restructuring方法類)來處理這個問題，但是不難發現這些函數依然可以inline化組合到一起，寫出一個不帶分号的 One Line DFT。