论文标题
加速十进制乘法
Speeding up decimal multiplication
论文作者
论文摘要
十进制乘法是在基本$ 10^n中乘以两个数字的任务。$，具体来说，我们专注于算法的数字理论变换（NTT）家族。仅使用便携式技术，我们在MPDECIMAL库上实现了3x-5X的加速。在本文中，我们描述了我们的实施，并讨论了进一步的优化。我们还提出了一种简单的缓存算法，用于原位$ 2N \ times n $或$ n \ times 2n $矩阵换位，在“六步算法”变化中，对矩阵傅立叶算法的变化产生了需求，并且似乎尚不广泛地知道。另一个发现是，即使考虑到增加输入大小的最坏情况，也有意义地使用两个素数，而不是三种模量，并使答案恢复更加简单。
Decimal multiplication is the task of multiplying two numbers in base $10^N.$ Specifically, we focus on the number-theoretic transform (NTT) family of algorithms. Using only portable techniques, we achieve a 3x-5x speedup over the mpdecimal library. In this paper we describe our implementation and discuss further possible optimizations. We also present a simple cache-efficient algorithm for in-place $2n \times n$ or $n \times 2n$ matrix transposition, the need for which arises in the "six-step algorithm" variation of the matrix Fourier algorithm, and which does not seem to be widely known. Another finding is that use of two prime moduli instead of three makes sense even considering the worst case of increasing the size of the input, and makes for simpler answer recovery.
