没有定义“方块”为什么这个功能比较慢？

Question

这个问题位于SICP（练习1.26） 它说没有“方块”的定义，它会运行得更慢。 它旨在检查数字是否为素数。 这是更快的版本：

Scheme,Prime check,O(log n)

没有的 “广场” 的定义，使用

(* (expmod base (/ exp 2) m) 
    (expmod base (/ exp 2) m)) 

据说是Ø（ñ）

Answer 1

您需要如果您不使用square，则两次评估(expmod base (/ exp 2) m)。如果您将结果与let绑定在一起并将其传递给square，那么它将具有相同的复杂性。

Answer 2

这不是square过程，它使速度更快，而是缓存中间值。使用let会使它一样快：

(let ((tmp (expmod base (/ exp 2) m))) 
    (* tmp tmp)) 

关键的一点是，(expmod base (/ exp 2) m)只能做一次。