FFT Multiplication Calculator
Multiply large integers using FFT-based convolution with O(n log n) complexity.
Enter Numbers
FFT Algorithm
1. Represent numbers as polynomials
2. Apply FFT to both polynomials
3. Multiply pointwise in frequency domain
4. Apply inverse FFT
5. Propagate carries for final result
Convolution Theorem
a * b = IFFT(FFT(a) · FFT(b))
Convolution becomes pointwise multiplication in frequency domain.
Complexity
Traditional: O(n²)
FFT-based: O(n log n)
Fastest known algorithm for large integers!
12345 × 67890
= 838,102,050
FFT Size
16
Verified
Yes
Complexity Comparison
Traditional O(n²)25 ops
FFT O(n log n)64 ops
Speedup0.39x
FFT Sample Values
First 8 frequency components:
| k | FFT(a)[k] | FFT(b)[k] |
|---|---|---|
| 0 | 15.00 + 0.00i | 30.00 + 0.00i |
| 1 | 11.58 + 6.50i | 16.65 + 21.57i |
| 2 | 5.41 + 7.24i | -4.59 + 19.31i |
| 3 | 2.56 + 4.05i | -8.68 + 5.29i |
| 4 | 3.00 + 2.00i | -2.00 + 2.00i |
| 5 | 3.20 + 1.81i | -2.63 + 5.98i |
| 6 | 2.59 + 1.24i | -7.41 + 3.31i |
| 7 | 2.66 + 0.26i | -5.34 + -1.75i |
Verification
Direct: 838,102,050
Results match!
Applications
- Arbitrary precision arithmetic (GMP)
- Signal processing
- Polynomial multiplication
- Large integer factorization