「正方形」の定義がないと、なぜこの機能が遅くなるのですか？

Question

この質問はSICP（演習1.26） にあります。「正方形」の定義がなければ、より遅く実行されます。 数字がプライムかどうかのチェックを目指しています。 これは迅速バージョンである：O（N）と言われて

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

を使用し、 "四角" の定義がなければ

Scheme,Prime check,O(log n)

Answer 1

あなたは必要squareを使用しない場合は、(expmod base (/ exp 2) m)を2回評価してください。結果をletにバインドしてsquareに渡すと、同じ複雑さになります。

Answer 2

より速いが、中間値のキャッシングを行う手順はsquareではありません。 letを使用すると、同じくらい速いことになるだろう：

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

キーポイントは(expmod base (/ exp 2) m)は一度だけ行われることです。