10 days ago I used Karatsuba to multiply two numbers. Another possibility is to use Fourier transform.

While convolution in time domain takes O(n²) operations, it can be done in O(n) operations as point-wise multiplication in frequency…