理系学生日記

おまえはいつまで学生気分なのか

SICP

squareを使わずに*を使うと、以下の部分でexpmodが2度評価される。

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

expmod自体は $O(\log n)$ なため、この部分のオーダーは $O(2^{\log n})$ となり結局 $O(n)$