Nov, 2023
利用二进制多项式根指数表示的整数列表进行的二进制补码加法快速乘法
Fast multiplication by two's complement addition of numbers represented as a set of polynomial radix 2 indexes, stored as an integer list for massively parallel computation
Mark Stocks
TL;DR基于多项式基数 2 索引存储的整数列表，我们展示了一种乘法方法。通过实现一套基于 Python 代码的 “多项式整数索引乘法” 算法，我们证明了该方法在一定位范围内的乘法比数论变换（NTT）和 Karatsuba 更快。同时，我们还通过与多项式基数 2 整数方法进行比较来实现 Python 代码。我们证明了任何整数或实数都可以表示为整数索引列表，代表二进制中的有限级数。整数索引的有限级数表示可以分布在多个 CPU / GPU 上进行存储和分发。我们展示了加法和乘法操作可以作为补码加法应用于索引整数表示，并且可以完全分布在给定的 CPU / GPU 体系结构上。我们证明了完全分布式计算方法可以克服并行乘法方法的当前限制，即需要共享共同的核心内存和磁盘来计算结果和中间结果。