SICP Exercise 1.26
(remainder (* (expmod base (/ exp 2) m)
(expmod base (/ exp 2) m))
m)
Using multiplication like this rather than calling square causes the expmod function to be called twice. Instead of linear recursion, the procedure now becomes a recursion tree whose execution time increases exponentially as it’s depth increases as a logarithm of N.