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

https://github.com/coells/100days

#### algorithm

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)))

#### run

> mult('987324', '23487')

'23189278788'