沒有定義「方塊」爲什麼這個功能比較慢？

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)只能做一次。