-2

给定一个 n 位整数和一个 m 位整数。如何使用列表、数组或任何其他 lisp 特定数据类型在 LISP 中将它们相乘？

例如;

a(1)a(2)...a(n)

b(1)b(2)...b(m)

结果为；

r(1)r(2)...r(m+n)

4

3 回答 3

6

Common Lisp 已经有原生的bignums。你为什么不使用它们？

您基本上不必特别声明任何东西，它们“神奇地”发生：

 % sbcl
 This is SBCL 1.0.56.0.debian, an implementation of ANSI Common Lisp.

 * (defun fact (n) (if (< n 1) 1 (* n (fact (- n 1)))))
 FACT

 * (fact 50)
 30414093201713378043612608166064768844377641568960512000000000000

因此，使用 Common Lisp，您基本上不必费心......

附加物

而高效的bignum算法是一个非常困难的问题；高效算法比简单算法具有更好的复杂性；您可以找到解释它们的困难书籍（基础数学非常困难）。另请参阅此答案。

如果你想做一个有竞争力的 bignum 实现，准备好几年努力工作，把它做成博士论文。

于 2012-04-28T21:12:47.603 回答
4

一个简单的算法就是模仿你在手动计算乘法时所做的事情：

  123 x
  456 =
  ---
  738
 615
492
-----
56088

第一步是实现乘以单个“数字”（例如123 x 6 = 738）。

之后，移位当然是微不足道的（只需滑动列表中的元素），因此可以使用加法功能完成乘法运算。

请注意，这不是计算两个大数的乘积的最快方法（例如，参见Karatsuba 算法）。

PS：思考如何手动计算两个大数的乘积也解释了一些“惊人”的结果，例如 111111111*111111111 = 12345678987654321

         111111111 x
         111111111 =
         ---------
         111111111
        111111111
       111111111
      111111111
     111111111
    111111111
   111111111
  111111111
 111111111
 -----------------
 12345678987654321
于 2012-04-29T09:18:16.977 回答
3 
(* 1234567890123456789123456789 1234567890123456789123456789)

大整数是 Common Lisp 原生的。

于 2012-04-28T21:10:06.573 回答