Phép biến đổi Fourier nhanh (Fast Fourier Transform)

Một trong những ứng dụng thường gặp của phép biến đổi Fourier nhanh (FFT) là nhân hai số nguyên lớn (vì việc này cũng coi như là nhân 2 đa thức biến x = 10).

Fabrice Bellard là một nhà khoa học máy tính người Pháp đã viết được chương trình C tính ra giá trị của: (2 mũ 43112609) – 1. Đây là số nguyên tố lớn nhất cho đến giờ con người tìm ra.

Quy tắc của ông như sau: thay vì phải có (43112609 – 1 = 43112608) phép tính nhân các số 2 lại với nhau, thì nên tận dụng lại các kết quả tính ra trong quá trình đó, thế này: viết 43112609 thành dạng nhị phân 1010010001110110001010000. Ban đầu khởi tạo một biến tích lũy s = 1, đi từ trái qua phải trên dãy nhị phân, nếu gặp bit 1 thì bình phương s rồi nhân với 2. Cứ như vậy cuối cùng s = 2 mũ 43112609.

Phép nhân một số với số 2 ko có gì đáng nói, còn phép bình phương thì chính là ứng dụng trên của FFT. Ở đây đặc biệt là hai số nguyên đem nhân là giống nhau, nên thời gian thực hiện FFT sẽ nhanh hơn.

Code của Fabrice Bellard (compile trên GCC), vâng, cực kì tinh vi và khó hiểu:

int m=167772161,N=1,t[1<<25]={2},a,*p,i,e=34893349,s,c,U=1;g(d,h){for(i=s;i<1<<
24;i*=2)d=d*1LL*d%m;for(p=t;p
=(m+*p-a)*(h?1LL:c)%m,a+=*p,*p++=a%m,c=c*1LL*d%m;}main(){while(e/=2){N*=2;U=U*
1LL*(m+1)/2%m;for(s=N;s/=2;)g(17,0);for(p=t;p
;s<<(e&1),*p++=a%10,a/=10;}while(! *--p);for(t[0]--;p>=t;)putchar(48+*p--);}

Xem thêm về FFT

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s