Thành phố Cuồng loạn

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â ...