limour-blog.github.io/source/_posts/2022-12-23-【迁移】FFT的有趣应用：计算整数乘法.md

---

title: 【迁移】FFT的有趣应用：计算整数乘法 urlname: FFT-de-you-qu-ying-yong-ji-suan-zheng-shu-cheng-fa date: 2022-12-23 23:27:00

tags: ['FFT', '整数乘法']

配置环境

conda create -n scipy -c conda-forge scipy -y
conda activate scipy
conda install -c conda-forge ipykernel -y
python -m ipykernel install --user --name scipy

回答验证

import numpy as np
from scipy.fftpack import fft, ifft
def nextPower2(L):
    return np.power(2,np.ceil(np.log2(L))).astype(int)
def int2Array(n, size):
    res = np.zeros(nextPower2(size), dtype = np.int8)
    i = 0
    while n > 0:
        n, res[i] = divmod(n, 10)
        i += 1
    return res
def array2Int(arr):
    return np.dot(np.around(arr,0),10**np.arange(len(arr)))

a = fft(int2Array(34, 4))
b = fft(int2Array(77, 4))
c = a * b
d = ifft(c)
e = array2Int(d)
a,b,c,d,e
# (array([7.-0.j, 4.-3.j, 1.-0.j, 4.+3.j]),
#  array([14.-0.j,  7.-7.j,  0.-0.j,  7.+7.j]),
#  array([98. -0.j,  7.-49.j,  0. -0.j,  7.+49.j]),
#  array([28.+0.j, 49.+0.j, 21.-0.j,  0.+0.j]),
#  (2618+0j))
 
array2Int(ifft(fft(int2Array(457, 6))*fft(int2Array(756, 6))))
# (345492+0j)