Lisp 中的算术

Question

如果我尝试在 Chicken Scheme（带有数字扩展名）和 Clisp 中计算表达式 (expt 123456 123456)，则需要相当长的时间（在 Clisp 中更多）。所以我认为计算表达式 (/ (expt 123456 123456) (expt 123456 123456)) 至少需要两倍的时间，因为解释器必须计算两倍的幂函数，然后必须计算一个除法。但是，令人惊讶的是，两个口译员的答案几乎是瞬间就出来了。到底是怎么回事？怎么可能？确切地说，这个表达式是如何计算的？

Answer 1

乘幂是一个相对快速的操作，即使使用大整数也是如此（它需要对数时间，不包括大整数运算的成本）。但是打印数字是一个相对较慢的操作（需要二次方时间）。所以在你的第一个问题中打印结果需要很长时间。在你的第二个问题中，结果是 1，所以时间花在了计算上，这很快。在我的电脑上，第一个问题用时不到 2 秒，然后花几秒钟打印结果，第二个问题用时不到两倍，然后立即打印 1.

Answer 2

CL-USER 2 > (time (progn (/ (expt 123456 123456) (expt 123456 123456))
                         (values)))
Timing the evaluation of (PROGN (/ (EXPT 123456 123456) (EXPT 123456 123456))
                                (VALUES))

User time    =        2.861
System time  =        0.009
Elapsed time =        2.858
Allocation   = 8718224 bytes
228 Page faults

CL-USER 3 > (time (progn (expt 123456 123456)
                         (values)))
Timing the evaluation of (PROGN (EXPT 123456 123456)
                                (VALUES))

User time    =        1.426
System time  =        0.003
Elapsed time =        1.419
Allocation   = 3398840 bytes
138 Page faults

Answer 3

如果您尝试定义：

(defun f()
  (expt 123456 123456))

在SBCL和CCL中然后做(disassemble #'f)你会发现值(expt 123456 123456)是在编译时预先计算的，并由函数返回。但是如果你定义 :

(defun f()
  (/ (expt 123456 123456) (expt 123456 123456))

反汇编这个函数，你会发现编译器足够聪明，可以编译这个函数returns立即得到值1。

所以，你应该在你的计时中考虑编译器执行的优化，当然打印非常大的数字会占用很多时间。

Answer 4

在 Common Lisp 中你有 time 宏：

(time (progn (expt 123456 123456) 1))
; Real time: 0.578002 sec.
; Run time: 0.577577 sec.
; Space: 733816 Bytes
; GC: 1, GC time: 0.007143 sec.
; ==> 1

(time (progn (princ (expt 123456 123456)) 1))
; a whole lot of numbers ...6
; Real time: 59.980278 sec.
; Run time: 59.017193 sec.
; Space: 8490376 Bytes
; GC: 4, GC time: 0.033218 sec.
; ==> 1

它们之间的区别在于以人类可读的十进制方式生成数字并在慢速控制台上输出。

第二个表达式的用时大约是第一个表达式的两倍：

(time (/ (expt 123456 123456) (expt 123456 123456)))
; Real time: 1.120879 sec.
; Run time: 1.11894 sec.
; Space: 1728656 Bytes
1

确实如此.. 只打印第一个表达式的结果如何：

(let ((value (time (expt 123456 123456))))
  (time (princ value))
  1)
; Real time: 0.584907 sec. (pretty much the same time calculating the result)
; Run time: 0.584398 sec.
; Space: 733816 Bytes
; GC: 1, GC time: 0.020312 sec.
; lots of digits ...56
; Real time: 59.803486 sec. about the same time it took printing it last time
; Run time: 58.414997 sec.
; Space: 2514768 Bytes
; GC: 1, GC time: 0.002712 sec.
; ==> 1

我认为我不需要在 Scheme 中重复这一点。控制台很慢，CL 和 Scheme 中的算术很快，即使是大数字也是如此。

编辑

我确实制作了一个脚本并将其重定向到一个文件，并且花费了大约相同的时间。因此，大部分时间用于将 bignum 转换为人类可读的字符，而不是实际将其输出到控制台上。如果是控制台将其重定向到文件，将大大加快整个过程。

Lisp 中的算术

Arithmetic in Lisp

lisp

math

scheme

common-lisp