#| Для этого упражнения нет проверок.
Любое решение будет считаться успешным ответом. |#
#| This exercise has no tests.
Any solution is a right answer. |#
; Solution

; Louis’s version of expmod doesn’t use
; a square function, but instead uses multiplication (*).
; This might not seem significant, but we have to keep
; in mind that the interpreter uses applicative-order evaluation,
; meaning it will evaluate the arguments and then apply the function.

; In the case of (square (expmod base (/ exp 2) m)),
; the parameter of square will be evaluated only once,
; then square will be applied.

; In the case of
; (* (expmod base (/ exp 2) m)
;    (expmod base (/ exp 2) m)),
; each of the (expmod base (/ exp 2) m) will be fully evaluated
; before the * is applied. Since both are recursive calls,
; it will double the work to do whenever this branch is executed.
; The complexity becomes Θ(log(2^n)) = Θ(n*log2) = Θ(n).