主题:有人用FFT写过大数乘法吗? -- 面壁
共:💬16 🌺13
多项式变换(PT)是1978年法国著名信号处理与计算机专家H.J.Nussbaumer提出的一种正交离散变换,当时主要用来计算多维数字卷积和多维DFT,引起了国际上普遍关注,著名数学家S.Winograd指出用多项式变换成为计算二维DFT的算法同阿贝尔半单代数有密切关系,并且可能成为处理多维问题的一种有力工具。多项式变换是以多项式M(z)为模的多项式剩余环F[z]/(M[z])上的一种离散傅立叶变换,由于常用的多项式变换的计算不需要乘法运算(只需加法运算),因此已成功用于一维及多维数字卷积、多维DFT、多项式乘积、大整数乘积等快速计算中,其效率高于FFT,而且特别适合并行计算
说来惭愧,这本书买了N年,从来没翻过,今天听你一说,模模糊糊有点印象,正好在手边,翻出来,总算派点用场。
- 相关回复 上下关系8
🙂不敢不敢,面壁这是搜了一个多月后的结果。 面壁 字0 2008-11-19 06:32:19
🙂刚才翻了一下书,说是多项式变换效率更高 1 深空探索 字122 2008-11-19 06:51:22
🙂用汇编写过大数乘法。。。 1 暗香疏影月黄昏 字118 2008-11-19 04:29:27