Lisp中的算术

Question

如果我尝试(expt 123456 123456)在Chicken Scheme(使用数字扩展名)和Clisp中评估表达式,则需要相当长的时间(在Clisp中更多).所以,我认为,评估的表达(/ (expt 123456 123456) (expt 123456 123456))至少需要两倍的时间,因为解释必须评估两倍的电源功能,然后必须评估师.但是,令人惊讶的是,两位口译员的答案几乎是瞬间出现的.到底是怎么回事？怎么可能？确切地说,这个表达式是如何评估的？

Answer 1

在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很快,即使使用bignums也是如此.

编辑

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

Answer 2

即使使用大整数,提升功率也是一种相对快速的操作(需要对数时间,不包括大整数运算的成本).但是打印一个数字是一个相对较慢的操作(它需要二次时间).因此,在您的第一个问题打印结果需要很长时间.在你的第二个问题中,结果为1,因此花费在计算上的时间很快.在我的计算机上,第一个问题需要花费不到2秒的时间,然后花费几秒钟打印结果,第二个问题需要的时间少于两倍,然后立即打印1.

Answer 3

如果您尝试定义:

(defun f()
  (expt 123456 123456))

在SBCL和CCL中,(disassemble #'f)您会发现该值(expt 123456 123456)在编译时预先计算并由函数返回.但是如果你定义:

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

并且反汇编这个函数,你会发现编译器足够聪明,可以编译函数,使它立即返回值1.

因此,您应该在您的计时中考虑编译器执行的优化,当然,打印非常大的数字需要花费大量时间.