Iterative version of expmod

Recursive version:

(define (square x) (* x x))
(define (expmod base exp m)
  (cond ((= exp 0) 1)
   	((even? exp)
	 (remainder (square (expmod base (/ exp 2) m))
	  (remainder (* base (expmod base (- exp 1) m))

I was a bit surprised that the above algorithm didn’t come with the problem set of to rewrite it in an iterative form. So here it is.

Iterative Version:

(define (square-mod n m) (remainder (* n n) m))
(define (expmod-iter base n m a)
  (cond ((= n 0) a)
   	((even? n) (expmod-iter (square-mod base m) (/ n 2) m a))
	  (expmod-iter base (- n 1) m (remainder (* a base) m)))))
(define (expmod base n m)
  (expmod-iter base n m 1))