FFT算法

什么是傅里叶变换

傅里叶变换是一种数学工具，用于将一个函数从时域（时间域）转换到频域（频率域）。它是以法国数学家约瑟夫·傅里叶的名字命名的。傅里叶变换可以将一个函数表示为不同频率的正弦和余弦函数的叠加，从而揭示函数在不同频率上的能量分布情况。

傅里叶变换在物理学和工程学中有许多应用。它的基本思想是将一个函数分解为不同特征的正弦函数的和，类似于化学分析中分析化合物的元素成分。对于一个函数，傅里叶变换可以分析其组成部分，确定组成它的基本（正弦函数）成分[1]。

傅里叶变换的定义有多种方式，但一般情况下，我们使用连续傅里叶变换的定义。连续傅里叶变换将一个可积函数表示成复指数函数的积分形式或级数形式。具体地说，对于一个函数f(x)，它的傅里叶变换表示为：

Ff = ∫[-∞, ∞] f(x) e^(-2πixξ) dx [1]

其中ξ为任意实数，ξ的定义域为频域。傅里叶变换将函数从时域转换到频域，将函数在不同频率上的能量分布情况展示出来。

傅里叶变换具有许多基本性质，其中包括线性性质和平移性质。线性性质表示两个函数的傅里叶变换之和等于各自变换之和。平移性质表示如果一个函数的傅里叶变换存在，那么对于任意实数ω0，函数f(x)e^(iω0x)的傅里叶变换也存在，并且满足以下关系：

F[f(x)e^(iω0x)] = F[f](ω - ω0) [1]

傅里叶变换在许多领域都有广泛的应用，包括医学、数据科学、物理学、声学、光学、结构力学、量子力学、数论、组合数学、概率论、统计学、信号处理、密码学、大气科学、海洋学、通讯和金融等。例如，在信号处理中，傅里叶变换可以将复杂的信号分解成具有不同振幅的单一频率分量，并用于滤波等操作。在量子力学中，傅里叶变换可以将位置空间的波函数转换为动量空间的波函数。

Learn more:

简单应用

cpp
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<cmath>
#define N (1<<18)//如果不介意，可以开小点
using namespace std;
struct cmpx{//不一样的结构体，运算符重载
    double r,i;
    cmpx operator + (const cmpx &a)const{return (cmpx){r+a.r,i+a.i};}
    cmpx operator - (const cmpx &a)const{return (cmpx){r-a.r,i-a.i};}
    cmpx operator * (const cmpx &a)const{return (cmpx){r*a.r-i*a.i,r*a.i+i*a.r};}
};
int rev[N];
cmpx A[N],a[N],b[N],c[N];
int L,n;
void DFT(cmpx a[],int f){
     int i,j,k;
     for(i=0;i<L;i++)
     A[i]=a[rev[i]];
     for(i=0;i<L;i++)
     a[i]=A[i];
     for(i=2;i<=L;i<<=1){
                         cmpx wi=(cmpx){cos(2.0*M_PI/i),f*sin(2.0*M_PI/i)};
                         for(k=0;k<L;k+=i){
                                           cmpx w=(cmpx){1.0,0.0},x,y;
                                           for(j=0;j<i/2;j++){
                                                              x=a[k+j];
                                                              y=w*a[k+j+i/2];
                                                              a[k+j]=x+y;
                                                              a[k+j+i/2]=x-y;
                                                              w=w*wi;
                                                              }
                                           }
                         }
  if(f==-1)
  for(i=0;i<L;i++)
  a[i].r/=L;
}
void FFT(cmpx a[],cmpx b[],cmpx c[]){
     int i;
     DFT(a,1);
     DFT(b,1);
     for(i=0;i<L;i++)
     c[i]=a[i]*b[i];
     DFT(c,-1);
}
void init(int tmp){
     int i,t,j;
     for(n=0,L=1;L<tmp;L<<=1)
     n++;
     n++;
     L<<=1;
     for(i=0;i<L;i++)
     for(t=i,j=0;j<n;j++){
         rev[i]<<=1;
         rev[i]|=t&1;
         t>>=1;
         }
}
int ans[N];
void DSC(){//开始处理问题，开始处理问题，开始处理问题，重要的事情说3遍！
     int l1=0,l2=0,i;
     char ch=getchar();
     while(ch>'9'||ch<'0')
     ch=getchar();
     while(ch>='0'&&ch<='9'){
                             a[l1].r=ch-'0';
                             a[l1++].i=0.0;
                             ch=getchar();
                             }
     while(ch>'9'||ch<'0')
     ch=getchar();
     while(ch>='0'&&ch<='9'){
                             b[l2].r=ch-'0';
                             b[l2++].i=0.0;
                             ch=getchar();
                             }
    reverse(a,a+l1);
    reverse(b,b+l2);
    init(max(l1,l2));
    FFT(a,b,c);
    for(i=0;i<L;i++)
    ans[i]=(int)(c[i].r+0.5);
    for(i=0;i<L;i++){
                     ans[i+1]+=ans[i]/10;
                     ans[i]%=10;
                     }
    L=l1+l2+1;
    while(!ans[L]&&L>0)
    L--;
    for(i=L;~i;i--)
    putchar(ans[i]+'0');
    putchar('\n');
}
int main(){//主函数so easy
    DSC();
    return 0;
}

这份代码实现了整数的快速 Fourier 变换(FFT)来进行大整数的乘法。

主要步骤:

定义复数结构体 cmpx,重载基本四则运算。
定义FFT参数:
- rev按位翻转数组,用于快速傅立叶变换复杂度优化。
- A为FFT工作数组。
- init函数初始化FFT参数。
DFT函数实现离散傅立叶变换,参数f区分正变换(1)和逆变换(-1)。
FFT函数调用DFT实现整数 FFT 乘法:
- a,b长度分别FFT
- 点乘得出结果c
- 调用DFT实现FFT乘法
DSC函数开始处理问题:
- 读入整数a,b
- 调用FFT函数乘法
- 整形四舍五入取整数部分
- 返回乘法结果
main函数调用DSC函数,完成大整数乘法运算。

整体采用FFT算法优化整数乘法计算复杂度,使得很大整数进行乘法也能在很短时间内得到结果。实现了详细的注释来解释每一步的目的。

目录

什么是傅里叶变换

简单应用