Thành phố Cuồng loạn

Trong lĩnh vực khoa học máy tính và toán học ứng dụng, các thuật toán đa thức đóng một vai trò quan trọng. Bài viết này sẽ giới thiệu hai kỹ thuật mạnh mẽ để thực hiện phép nhân đa thức một cách hiệu quả: Biến đổi Fourier nhanh (FFT) và Biến đổi số học nhanh (NTT). Biến đổi Fourier nhanh (FFT) 1.1 Biểu diễn đa thức và nhân đa thức Một đa thức ...

Phép Nhân Đa Thức Biến Đổi Fourier Nhanh (FFT): struct ComplexNumber { double real, imag; ComplexNumber operator + (const ComplexNumber &a) { return {real + a.real, imag + a.imag}; } ComplexNumber operator - (const ComplexNumber &a) { return {real - a.real, imag - a.imag}; } ComplexNumber operator * ( ...

Giới thiệu chung Vấn đề cốt lõi của tích chập là tìm một dãy số $h$ từ hai dãy $f$ và $g$, sao cho thỏa mãn công thức: \[ h_x = \sum_{i \oplus j = x} f_i \cdot g_j \] Tại đây, ký hiệu $\oplus$ đại diện cho phép toán cụ thể dùng để phân biệt các dạng tích chập khác nhau. Thông thường, việc tính toán trực tiếp sẽ có độ phức tạp là $O(n^2)$. Mụ ...

Trong lĩnh vực đại số máy tính và toán học rời rạc, việc xử lý các phép toán trên đa thức với hiệu suất cao là rất quan trọng. Các thuật toán như biến đổi Fourier nhanh (FFT) và biến đổi số lý thuyết (NTT) là nền tảng cho nhiều phép toán đa thức phức tạp hơn. Bài viết này sẽ đi sâu vào một số kỹ thuật nâng cao sử dụng các công cụ này. Phép Nhâ ...