快速数论变换详解

发布时间：2023-05-22

一、介绍

快速数论变换（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)+xP_odd(x^2)，这里P_even和P_odd分别为偶次项和奇次项的多项式。根据这个式子，可以得到两个简单的等式：P(0)=P_even(0)+0P_odd(0)，P(1)=P_even(1)+1P_odd(1)。这样就将P(x)与两个小规模的多项式P_even(x^2)和P_odd(x^2)联系了起来。 如果我们需要在4个点处计算多项式的值，可以将其分解为四个部分：P(x)=P_even(x^4)+x^2P_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)=∑{i=0}^{n-1}a_ix^i=∑{i=0}^{n/2-1}a_{2i}x^i+∑{i=0}^{n/2-1}a{2i+1}x^i*x^{n/2}，其中第一部分为偶次项的多项式，第二部分为奇次项的多项式。 通过这样的分治，我们可以将每个多项式递归地拆分成两个小规模的多项式，并在最后的叶子结点处计算出其值。这个过程可以通过以下代码实现：

/* 计算多项式P(x)在所有n次单位根处的值 */
void FFT(complex<double> P[], int n, int inv)
{
    if(n == 1) return;
    /* 将P(x)分解成偶次项和奇次项多项式 */
    complex<double> 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<double> 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)=∑{i=0}^{n-1}y_i*∏{j=0,j≠i}^{n-1}(x-x_j)/(x_i-x_j)，其中y_i为P在第i个单位根处的值。通过这样的插值计算，我们可以将点值表示的多项式P(x)转换为系数表示，从而完成FFT算法的整个计算过程。 这个过程可以通过以下代码实现：

/* 将多项式从点值表示转换为系数表示 */
void IFFT(complex<double> 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<double> 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算法在实际应用中有着广泛的用途，其中最常见的就是计算高精度乘法。

推荐文章