[archives] [homepage]

Problem 1.26
Friday, August 23, 2019; ago; Download .md

SICP Exercise 1.26

(remainder (* (expmod base (/ exp 2) m)
			  (expmod base (/ exp 2) 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.