Exercise1-25 <---> Exercise1-27
Exercise 1.26
Louis Reasoner is having great difficulty doing exercise 1.24. His fast-prime? test seems to run more slowly than his prime? test. Louis calls his friend Eva Lu Ator over to help. When they examine Louis's code, they find that he has rewritten the expmod procedure to use an explicit multiplication, rather than calling square:
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (* (expmod base (/ exp 2) m)
(expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
I don't see what difference that could make, says Louis. I do. says Eva. By writing the procedure like that, you have transformed the 
process into a 
process. Explain.
Ru: У Хьюго Дума большие трудности в упражнении 1.24. Процедура fast-prime? у него работает медленнее, чем prime?. Хьюго просит помощи у своей знакомой Евы Лу Атор. Вместе изучая код Хьюго, они обнаруживают, что тот переписал процедуру expmod с явным использованием умножения вместо того, чтобы вызывать square:
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (* (expmod base (/ exp 2) m)
(expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
Хьюго говорит: «Я не вижу здесь никакой разницы». «Зато я вижу, — отвечает Ева. — Переписав процедуру таким образом, ты превратил процесс порядка в процесс порядка ». Объясните.
Solution:
On each iteration of expmod two identical expressions of (expmod base (/ exp 2) m) are evaluated before multiplication. Thus, we have got a binary tree recursion with the total number of expmod evaluations being 
. And 
.
Another consideration about growth rate, that may be appropriate here, but not correct in general is that 
.
Exercise1-25 <---> Exercise1-27