Day 20: Linearithmic multiplication
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 domain. Conversions between time and frequency take O(n.log(n)) operations which is also the final complexity.
The very same idea is successfully used in computer graphics when you need to apply large 2D kernels on large images.
def mult(x, y):
nx, ny = len(x), len(y)
# auxiliary x
fx = np.zeros(nx + ny, dtype=np.float64)
fx[:nx] = list(map(int, reversed(x)))
# auxiliary y
fy = np.zeros(nx + ny, np.float64)
fy[:ny] += list(map(int, reversed(y)))
# convolution via FFT
fx = np.fft.fft(fx)
fy = np.fft.fft(fy)
z = np.fft.ifft(fx * fy).real.round().astype(int)
# carry over
for i in range(nx + ny - 1):
z[i + 1] += z[i] // 10
z[i] %= 10
return ''.join(map(str, reversed(z)))
> mult('987324', '23487')