快速數論變換詳解

一、介紹

快速數論變換（FFT）是一種計算多項式的方法，它能夠將一組點值轉換為其在另一組點處的值，從而降低了計算複雜度。這個算法最初是由高德納和圖靈在1965年提出，並在之後幾十年間被廣泛應用於數字信號處理、圖像處理、密碼學、物理模擬等領域。

FFT算法雖然有多種版本，但它們的思想基本都是相同的，即將多項式拆分成小規模的部分來進行計算。這樣可以提高計算效率，使得計算複雜度從原來的O(n^2)降低至O(nlogn)。在實際應用中，FFT算法已經成為了計算高精度乘法的主要手段，因為它能夠快速、高效地完成大量的運算工作。

二、算法原理

要理解FFT算法的核心思想，需要先從多項式的點值表示開始。給定一個多項式P(x)，我們可以將其在給定的n個點處計算出其值。這些點通常是2的次冪，因為這樣可以使得FFT算法的運行效率最高。

假設我們要在2個點處計算多項式的值，即P(0)和P(1)，可以將多項式分解為兩部分：P(x)=P_even(x^2)+x*P_odd(x^2)，這裡P_even和P_odd分別為偶次項和奇次項的多項式。根據這個式子，可以得到兩個簡單的等式：P(0)=P_even(0)+0*P_odd(0)，P(1)=P_even(1)+1*P_odd(1)。這樣就將P(x)與兩個小規模的多項式P_even(x^2)和P_odd(x^2)聯繫了起來。

如果我們需要在4個點處計算多項式的值，可以將其分解為四個部分：P(x)=P_even(x^4)+x^2*P_odd(x^4)+x*P_even(x^2)+P_odd(x^2)，其中P_even和P_odd分別為偶次項和奇次項的多項式。同樣，這個式子可以化為四個等式，分別計算P(0)、P(1)、P(2)和P(3)的值。

FFT算法的核心思想就是通過這種分治的方式，將一個大規模的多項式拆分成多個小規模的子多項式，並通過不斷遞歸的方式將計算複雜度降低至O(nlogn)。具體來說，算法的實現分為兩個步驟：

三、FFT算法步驟

1. 計算點值

算法的第一步是將多項式用點值表示。給定一個n次多項式P(x)，我們需要在n個點處計算其值。為了使計算複雜度最小，通常需要使用n的整數次冪作為點數。

對於給定的n個點，我們可以使用著名的歐拉公式來計算每個點的值：P(x)=\sum_{i=0}^{n-1}a_ix^i=\sum_{i=0}^{n/2-1}a_{2i}x^i+\sum_{i=0}^{n/2-1}a_{2i+1}x^i*x^{n/2}，其中第一部分為偶次項的多項式，第二部分為奇次項的多項式。

通過這樣的分治，我們可以將每個多項式遞歸地拆分成兩個小規模的多項式，並在最後的葉子結點處計算出其值。這個過程可以通過以下代碼實現：

/* 計算多項式P(x)在所有n次單位根處的值 */
void FFT(complex P[], int n, int inv)
{
    if(n == 1) return;

    /* 將P(x)分解成偶次項和奇次項多項式 */
    complex even[n/2], odd[n/2];
    for(int i = 0, j = 0; i < n; i += 2, j ++)
        even[j] = P[i], odd[j] = P[i+1];

    /* 遞歸計算子問題 */
    FFT(even, n/2, inv);
    FFT(odd, n/2, inv);

    /* 合併子問題的結果 */
    for(int i = 0; i < n/2; i ++)
    {
        /* 計算單位根的值 */
        complex w = polar(1.0, inv*2*PI*i/n);
        P[i] = even[i] + w*odd[i];
        P[i+n/2] = even[i] - w*odd[i];
    }
}

其中，inv表示FFT變換的方向，可以為1表示正變換，-1表示逆變換。該算法的時間複雜度為O(nlogn)。

2. 求解係數

得到多項式P在所有n次單位根處的值之後，我們可以使用插值公式來求解出P(x)的係數。由於n次單位根存在周期性，因此我們只需要在前一半的單位根上計算係數即可。

插值公式的具體形式為：P(x)=\sum_{i=0}^{n-1}y_i*\prod_{j=0,j!=i}^{n-1}(x-x_j)/(x_i-x_j)，其中y_i為P在第i個單位根處的值。通過這樣的插值計算，我們可以將點值表示的多項式P(x)轉換為係數表示，從而完成FFT算法的整個計算過程。

這個過程可以通過以下代碼實現：

/* 將多項式從點值表示轉換為係數表示 */
void IFFT(complex P[], int n)
{
    reverse(P+1, P+n);
    FFT(P, n, -1);
    for(int i = 0; i < n; i ++)
        P[i] /= n;
}

該算法的時間複雜度也為O(nlogn)。

四、應用舉例

FFT算法在實際應用中有很多用途，其中最常見的就是計算多項式乘法。由於n次多項式的乘法需要進行n^2次乘法操作，因此當n很大時，直接計算會非常耗時。FFT算法可以將計算複雜度降低至O(nlogn)，因此它在計算高精度乘法時非常有用。

下面是使用FFT算法計算多項式乘法的代碼：

const int N = 1 << 18;
complex A[N], B[N], C[N], D[N];

/* 計算多項式乘法 */
void poly_mul(int a[], int b[], int n)
{
    /* 初始化點值表示的多項式 */
    for(int i = 0; i < n; i ++)
        A[i] = a[i], B[i] = b[i];

    /* 計算點值多項式 */
    FFT(A, n, 1), FFT(B, n, 1);
    for(int i = 0; i < n; i ++)
        C[i] = A[i] * B[i];

    /* 轉換為係數表示 */
    IFFT(C, n);
    for(int i = 0; i < 2 * n; i ++)
        printf("%d ", (int)(C[i].real() + 0.5));
}

五、總結

FFT算法是一種基於分治思想的高效計算多項式的算法，它將多項式拆分成小規模的子問題，並通過不斷遞歸的方式將計算複雜度降低至O(nlogn)。FFT算法在實際應用中有着廣泛的用途，其中最常見的就是計算高精度乘法。