SICP Solutions

Section - Procedures and the Processes They Generate

Exercise 1.25

The function expmod defined by Alyssa P. Hacker will take much more time as compared to the original procedure. In the original procedure all operations multiplication/division/remainder are done on integers at max to ${base}^2$, where $base$ is input to the procedure.

But in the process defined by Alyssa, these operations are performed on huge number: $base^n$. This slows down the algorithm significantly.