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'
Show your support

Clapping shows how much you appreciated Tomáš Bouda’s story.