---
tags: sysprog
---

# 隱藏的傅立葉轉換

## 從洗牌談起

{%youtube o8LKXbGm94A%}

洗牌演算法是針對給定數列的隨機重新排列的過程。一個好的洗牌算法應要屏除 [bias](https://en.wikipedia.org/wiki/Bias_(statistics))，也就是說，每種排列出現機率應相等。

我們來看 [Fisher–Yates 洗牌演算法](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)，時間複雜度是 $O(n)$, 空間複雜度是 $O(1)$，也易於實作：

function shuffle(array) {
    var n = array.length, t, i;
    while (n) {
        i = Math.random() * n-- | 0; // 0 ≤ i < n
        t = array[n];
        array[n] = array[i];
        array[i] = t;
    }
    return array;
}

演算法的過程見下圖:

圖中每條線代表一個數字，線的傾斜程度代表數的大小，線越往左傾斜表示數值越小，反之，越往右傾斜表示數值越大。

不難發現，該演算法將陣列劃分為兩個部分：右半邊是已洗牌區域 (用黑線表示)，左半邊是待洗牌區域 (用灰線表示)。每步從左邊的待洗牌區域隨機選擇一個元素並將其移動到右側，如此循環下去直到待洗牌區域無陣列的元素，才會終止。

Fisher–Yates 洗牌演算法簡單且正確，但不是每個簡單的洗牌演算法一定會正確。以下是個錯誤示範:

function shuffle(array) {
    return array.sort(function(a, b) {
        return Math.random() - .5; // ಠ_ಠ
    });
}

先來解讀程式碼: `array.sort()` 表示對陣列進行排序，一般情況下是按照陣列元素的大小 (例如整數型態) 或者是按照字典排列順序 (例如字串) 進行排序。當然我們也可以自定義規則，也就是自行定義一個 `comparator` 函式，再依據返回值來確定待排元素的大小關係:
* 返回值大於 0 表明第一個參數更大;
* 返回值小於 0 表明第二個參數更大;
* 返回值為 0 表明相等;

上方程式碼定義了這樣的 `comparator` 函式，從陣列中隨機取兩個元素 `a` 和 `b`，然後隨機返回 `[-0.5, 0.5)` 之間的一個值，也就是說元素 `a` 和 `b` 之間的大小關係是隨機的，所以它們之間的順序也是隨機的，這樣遍歷完整個陣列後所有元素的順序都是隨機的。

但真的是如此嗎？當然不！這個演算法存在嚴重的缺陷。首先，任意兩個元素之間的順序隨機性並不能保證整體的順序隨機性。同時，一個比較器應該滿足傳遞性，如果有 `a > b` 且 `b > c`，那麼就有 `a > c` 的關係。但上述程式碼的隨機比較器破壞了這個特性，導致 `array.sort()` 行為不可確定，所以最後的結果也不可靠。

那麼它的結果到底如何呢？見下面這張圖:

乍看似乎是隨機，但要注意有些東西由人眼看起來隨機，實際上卻非如此。

為了更直觀衡量演算法的品質，我們換個方式思考。

一個好的洗牌演算法應該保證沒有 bias，也就是說保證每個元素在洗牌結束後出現在陣列的任何位置的機率為 $\frac{1}{n}$，其中 n 為陣列元素個數。當然準確的計算這個機率有點困難，但我們可以從統計意義上來計算這個機率。也就是把洗牌演算法執行幾千次，統計原先在位置 `i` 的元素在洗牌後出現在位置 `j` 的次數，繪製為如下圖例:

圖片的橫軸表示個別元素在洗牌前的位置，縱軸則表示元素在洗牌後的位置。顏色表示機率，綠色表示正偏，也就是出現次數高於預期。紅色表示負偏，也就是其出現次數低於預期。

而 Fisher–Yates 洗牌演算法的結果就好多了:

圖中無明顯的規律可循，個別偏差肇因於統計的方法，與演算法本身無關。

延伸閱讀:
* [Visualizing Algorithms](https://bost.ocks.org/mike/algorithms/)
<!-- 連結已死 待補充
* [完美洗牌演算法](https://www.ctolib.com/docs/sfile/the-art-of-programming-by-july/02.09.html) -->

## 等等，說好的傅立葉轉換呢？

1986 年論文 [SHUFFLING CARDS AND STOPPING TIMES](https://statweb.stanford.edu/~cgates/PERSI/papers/aldous86.pdf)

下方冒出各式驚喜！

[傅立葉轉換](https://hackmd.io/@sysprog/fourier-transform) 出現在洗牌演算法中。

* [C. Ramus 等式](https://proofwiki.org/wiki/Ramus%27s_Identity)

## 傅立葉轉換可用於乘法運算

* [Using Fourier Transforms To Multiply Numbers - Interactive Examples](http://blog.robertelder.org/fast-multiplication-using-fourier-transform/)
* [FFT-Based Integer Multiplication, Part 1](https://psun.me/post/fft1/)
* [FFT-Based Integer Multiplication, Part 2](https://psun.me/post/fft2/)
* [數論轉換 (NTT)](https://observablehq.com/@andy0130tw/ntt)