list - 在方案球拍中乘以大整数

Question

我在方案中实现了一个“big-int”作为列表，所以第一个元素是数字的符号（+ 或 -），以下是数字本身的值，首先是数字，然后是十位等.

例如：(+ 0 0 1)是为100，(- 9 2 3 1)是为-1329等。

我现在需要的是为以这种方式实现的大整数实现加法、减法和乘法。我已经做了加法和减法，有人可以帮我做乘法吗？

Answer 1

把问题分解成更小的部分。首先，编写一个将 Big-int 乘以单个数字的函数。然后，将此（使用 Greg Hewgill 的提示，您可能知道如何在纸上执行此操作）扩展为将 Big-int 乘以数字列表的函数。最后，将它包装在一个接受两个 Big-int 的函数中，去掉符号，然后调用你之前的函数。

我强烈建议您在开发它们之前为这些功能编写测试用例。

Answer 2

这是一个众所周知的大整数乘法的分治法：

http://ozark.hendrix.edu/~burch/csbsju/cs/160/notes/31/1.html

这种方法将这两个数字分成两半并递归处理。它非常快，而且很容易实现，尽管它可能看起来很长的解释。我强烈推荐它。它需要大约 10 行其他语言的代码，在方案中可能更少:)。