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:

Continue reading “Phép biến đổi Fourier nhanh (Fast Fourier Transform)”