1 day ago
my attempt to do the exercises in sicp.
Sunday, June 29, 2008
sicp exercise 1.26
; 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))
; (remainder (* base (expmod base (- exp 1) 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 O(log n) process into a O(n) process.'' Explain.
; Answer: if the procedure square is used, then the expression (expmod base (/ exp 2) m) needs
; to be calculated once instead of twice when * is used.