Toom-Cook乘法算法实现

我有一个任务来实现Toom-Cook 3-way乘法算法。我正在关注维基百科http://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication的描述，并且我设法将两个大数字存储到字符串中，并根据维基百科页面上的“拆分”步骤将字符串拆分为较小的数字。下一步是“评估”，我必须计算一个新的数字p0 = m0 + m2（Bordrato的“快速评估” - 可在同一页上找到），其中m0和m2是我通过分割大数字创建的数字（在前面的步骤中）。问题是我不能简单地加上m0和m2，因为这两个数字仍然很大，不可能以标准方式加在一起。这是否意味着我必须实现我自己的算法来添加大量数据（以及减少和分割，因为它们也是需要的），还是我错过了一些东西？如果任何人都可以链接我一个可能的实现，甚至一个伪代码，这将不胜感激。Toom-Cook乘法算法实现

来源

2013-05-08 Marko

加两个大整数非常简单。添加和运载，添加和运载，添加和运载...减法同样容易。 Division稍微强硬一些，但它基本上只是在阵列上进行长时间的划分。 – Patashu 2013-05-08 00:28:37

我假设你说你存储的字符串中的数字，你的意思是一些适当的大k（如32）基数2^k数字的数组。使用字符串会很愚蠢。对于bignum操作，为什么不使用像'gmp'或者'mini-gmp'这样的已建立的C库？ – Gene 2018-01-02 01:06:25

@Gene你是什么意思的“基数2^k数字数组”？你能给个例子吗？ – Marko 2018-01-02 02:36:28

LibTomMath是开源的，包含Toom-Cook乘法;看一看。

来源

2013-05-08 00:37:08

难以阅读所有的在线错误处理。 – greybeard 2018-01-01 19:04:07

你必须实现你自己的方法，用于加，减，模等等。前一段时间我试图实现一个BigInteger库，我发现了一些可能对你有用的资源。

BIGNUM数学书（如指出由以前的答案）
的Java OpenJDK的 BigInteger implementation，与文档
算法和数据结构的基本工具箱，（我认识到这本书的Karatsube）。

顺便说一下，我建议您使用base 2作为您的号码（see here.），因为您可以利用计算机的性质使您的操作更加轻松快捷。

来源

2013-05-08 03:16:36 rendon

Toom-Cook乘法算法实现

回答

相关问题