MULTIDIGIT MULTIPLICATION FOR MATHEMATICIANS
MULTIDIGIT MULTIPLICATION FOR MATHEMATICIANS
复制标题
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
D. Bernstein
中科院分区：
文献类型：
--
作者：
D. Bernstein
本文综述了各种交换环元素相乘的技术。它涵盖了卡拉楚巴乘法、对偶卡拉楚巴乘法、图姆乘法、对偶图姆乘法、快速傅里叶变换技巧、扭曲快速傅里叶变换技巧、分裂基快速傅里叶变换技巧、古德技巧、绍恩哈格 - 施特拉森技巧、绍恩哈格技巧、努斯鲍默技巧、循环绍恩哈格 - 施特拉森技巧以及康托尔 - 卡尔托芬定理。它强调了潜在的环同态。
This paper surveys techniques for multiplying elements of various commutative rings. It covers Karatsuba multiplication, dual Karatsuba multiplication, Toom multiplication, dual Toom multiplication, the FFT trick, the twisted FFT trick, the split-radix FFT trick, Good’s trick, the SchönhageStrassen trick, Schönhage’s trick, Nussbaumer’s trick, the cyclic SchönhageStrassen trick, and the Cantor-Kaltofen theorem. It emphasizes the underlying ring homomorphisms.