c - Tom-Cook 乘法算法实现

Question

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

Answer 1

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

• BigNum 数学书（如上一个答案所指出的）
• Java OpenJdk BigInteger 实现，带文档
• 算法和数据结构 基本工具箱，（我学过这本书的 Karatsube）。

顺便说一句，我建议您使用以 2 为底的数字（请参阅此处。），因为您可以利用计算机的特性使您的操作更加轻松快捷。

Answer 2

LibTomMath是开源的，包括一个 Tom-Cook 乘法；看一看。