Cấu trúc dữ liệu và Giải thuật Bài 71: Biến đổi Fourier Nhanh (Fast Fourier Transform - FFT) - Nhân đa thức siêu tốc trong $O(N \log N)$.

Tiếp tục hành trình trong Chương 15: Toán học hệ thống và Đại số cấu trúc, chúng ta đối mặt với một trong những thuật toán vĩ đại nhất của thế kỷ 20, có ảnh hưởng sâu rộng từ xử lý tín hiệu số cho đến mật mã học hiện đại: Biến đổi Fourier Nhanh (Fast Fourier Transform - FFT).

Hãy tưởng tượng bạn cần thực hiện phép nhân hai đa thức có bậc lớn, hoặc nhân hai số nguyên cực lớn chứa hàng triệu chữ số (ví dụ: trong các hệ thống tính toán khoa học hoặc mã hóa bất đối xứng).

• Phương pháp nhân thông thường (nhân từng hệ số chéo nhau theo kiểu học sinh tiểu học) đòi hỏi độ phức tạp thời gian lên tới $O(N^2)$.

• Khi $N = 10^5$, $N^2$ chạm mốc $10^{10}$ phép tính, làm hệ thống quá tải và đơ cứng.

Thuật toán FFT ra đời để giải quyết triệt để nút thắt cổ chai này, ép thời gian nhân đa thức xuống mức $O(N \log N)$ chớp nhoáng.

1. Bản chất của Đa thức và Ý tưởng Đột phá của FFT

Một đa thức độ dài $N$ có thể được biểu diễn dưới hai hình thái toán học:

1. Dạng hệ số (Coefficient Form):

   $$A(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_{n-1} x^{n-1}$$

2. Dạng giá trị (Point-Value Form): Một đa thức bậc $N-1$ được xác định duy nhất bởi $N$ điểm độc lập trên mặt phẳng tọa độ:

   $$(x_0, y_0), (x_1, y_1), \dots, (x_{n-1}, y_{n-1}) \quad \text{với } y_i = A(x_i)$$

Bí mật của sự tăng tốc:

• Nếu nhân hai đa thức ở Dạng hệ số, ta tốn $O(N^2)$.

• Nhưng nếu chuyển chúng sang Dạng giá trị, ta chỉ cần nhân trực tiếp các tung độ $y_i$ tương ứng với nhau ($y_3 = a_3 \cdot b_3$), tốn thời gian cực kỳ nhỏ là $O(N)$!

Tuy nhiên, việc chuyển đổi từ Dạng hệ số sang Dạng giá trị (Evaluation) và ngược lại (Interpolation) nếu làm theo cách thông thường vẫn tốn $O(N^2)$. FFT chính là thuật toán Chia để trị (Divide and Conquer) khai thác tính chất đối xứng của các Căn nguyên đơn vị phức (Roots of Unity) để thực hiện việc chuyển đổi hai chiều này trong thời gian $O(N \log N)$.

2. Triển khai FFT và Nhân đa thức bằng Golang

Dưới đây là mã nguồn chuẩn mực sử dụng số phức (math/cmplx) để hiện thực hóa thuật toán FFT và áp dụng vào bài toán nhân đa thức siêu tốc:

Go

package main

import (
	"fmt"
	"math"
	"math/cmplx"
)

// Thực hiện Biến đổi Fourier Nhanh (FFT) và Biến đổi ngược (IFFT)
// invert = false: Chuyển từ Hệ số sang Giá trị (FFT)
// invert = true: Chuyển từ Giá trị về Hệ số (Inverse FFT)
func fft(a []complex128, invert bool) {
	n := len(a)
	if n <= 1 {
		return
	}

	// Chia đa thức thành hai phần: Hệ số chẵn và Hệ số lẻ
	a0 := make([]complex128, n/2)
	a1 := make([]complex128, n/2)
	for i := 0; i < n/2; i++ {
		a0[i] = a[2*i]
		a1[i] = a[2*i+1]
	}

	// Đệ quy giải quyết các bài toán con
	fft(a0, invert)
	fft(a1, invert)

	// Hệ số góc (Roots of Unity)
	ang := 2 * math.Pi / float64(n)
	if invert {
		ang = -ang
	}
	w := cmplx.Rect(1, ang)
	wn := complex(1, 0)

	for i := 0; i < n/2; i++ {
		u := a0[i]
		v := wn * a1[i]
		a[i] = u + v
		a[i+n/2] = u - v
		if invert {
			a[i] /= 2
			a[i+n/2] /= 2
		}
		wn *= w
	}
}

// Hàm nhân hai đa thức sử dụng FFT trong O(N log N)
func MultiplyPolynomials(a, b []int) []int {
	// 1. Tìm kích thước N nhỏ nhất là lũy thừa của 2 đủ chứa kết quả (len(a) + len(b) - 1)
	n := 1
	for n < len(a)+len(b) {
		n <<= 1
	}

	fa := make([]complex128, n)
	fb := make([]complex128, n)

	for i := 0; i < len(a); i++ {
		fa[i] = complex(float64(a[i]), 0)
	}
	for i := 0; i < len(b); i++ {
		fb[i] = complex(float64(b[i]), 0)
	}

	// 2. Chuyển đổi sang dạng giá trị (Forward FFT)
	fft(fa, false)
	fft(fb, false)

	// 3. Nhân các giá trị tương ứng trên miền tần số trong O(N)
	for i := 0; i < n; i++ {
		fa[i] *= fb[i]
	}

	// 4. Chuyển ngược lại dạng hệ số (Inverse FFT)
	fft(fa, true)

	// 5. Làm tròn kết quả thực tế về mảng số nguyên
	resultLen := len(a) + len(b) - 1
	result := make([]int, resultLen)
	for i := 0; i < resultLen; i++ {
		result[i] = int(math.Round(real(fa[i])))
	}

	return result
}

func main() {
	// Đa thức A: 1 + 2x + 3x^2 (Biểu diễn bằng mảng hệ số [1, 2, 3])
	polyA := []int{1, 2, 3}
	// Đa thức B: 2 + 4x (Biểu diễn bằng mảng hệ số [2, 4])
	polyB := []int{2, 4}

	res := MultiplyPolynomials(polyA, polyB)
	fmt.Printf("Kết quả nhân đa thức: %v\n", res)
	// Mong đợi: (1 + 2x + 3x^2)(2 + 4x) = 2 + 4x + 4x^2 + 8x^2 + 6x^3 + 12x^3 ... 
	// Kết quả chuẩn: [2, 8, 14, 12]
}

3. Phân tích Hiệu năng (Big-O)

• Thời gian (Time Complexity): $O(N \log N)$. Nhờ cấu trúc phân rã chia để trị giống như cây nhị phân (tương tự thuật toán Merge Sort), số lượng phép tính giảm từ bình phương xuống logarit cơ số 2.

• Không gian (Space Complexity): $O(N)$ để cấp phát các mảng số phức trung gian trong quá trình đệ quy FFT.

4. Ứng dụng Thực tế trong Kỹ thuật Phần mềm

FFT không chỉ là một bài toán lý thuyết nâng cao, nó là trái tim của nhiều hệ thống công nghệ cốt lõi:

• Nhân số nguyên lớn (Arbitrary-Precision Arithmetic / BigInt): Các thư viện toán học bignum trong các ngôn ngữ lập trình hoặc hệ thống mã hóa sử dụng FFT để nhân các số nguyên có hàng triệu chữ số với tốc độ cao.

• Xử lý Tín hiệu Số (Digital Signal Processing - DSP): Lọc nhiễu âm thanh, chuyển đổi tín hiệu từ miền thời gian sang miền tần số trong các ứng dụng Equalizer, nén ảnh JPEG/Audio MP3.

• Truyền thông Không dây (OFDM): Các mạng di động 4G, 5G và Wi-Fi hiện đại sử dụng biến đổi Fourier để ghép kênh phân chia tần số trực giao, truyền tải dữ liệu dung lượng lớn qua không gian vô tuyến mà không bị nhiễu sóng.