SICP Exercise 1.18

Exercise 1.18.  Using the results of exercises 1.16 and 1.17, devise a procedure that generates an iterative process for multiplying two integers in terms of adding, doubling, and halving and uses a logarithmic number of steps.40

 SOLUTION

 The code is here.

Comments

Post a Comment

Popular posts from this blog

SICP Exercise 2.18 reverse

Exercise 2.18.   Define a procedure  reverse  that takes a list as argument and returns a list of the same elements in reverse order: (reverse (list 1 4 9 16 25)) (25 16 9 4 1) SOLUTION The code and tests are here .
Read more

SICP Exercise 1.45 multi average damp

Image
Exercise 1.45.   We saw in section  1.3.3  that attempting to compute square roots by naively finding a fixed point of  y     x / y  does not converge, and that this can be fixed by average damping. The same method works for finding cube roots as fixed points of the average-damped  y     x / y 2 . Unfortunately, the process does not work for  fourth roots -- a single average damp is not enough to make a fixed-point search for  y     x / y 3 converge. On the other hand, if we average damp twice (i.e., use the average damp of the average damp of  y     x / y 3 ) the fixed-point search does converge. Do some experiments to determine how many average damps are required to compute  n th roots as a fixed-point search based upon repeated average damping of  y     x / y n -1 . Use this to implement a simple procedure for computing  n th roots using  fixed-point ,  averag...
Read more

SICP Exercise 3.56 merge streams

Exercise 3.56.   A famous problem, first raised by  R. Hamming, is to enumerate, in ascending order with no repetitions, all positive integers with no prime factors other than 2, 3, or 5. One obvious way to do this is to simply test each integer in turn to see whether it has any factors other than 2, 3, and 5. But this is very inefficient, since, as the integers get larger, fewer and fewer of them fit the requirement. As an alternative, let us call the required stream of numbers  S  and notice the following facts about it. S  begins with 1. The elements of  (scale-stream S 2)  are also elements of  S . The same is true for  (scale-stream S 3)  and  (scale-stream 5 S) . These are all the elements of  S . Now all we have to do is combine elements from these sources. For this we define a procedure  merge  that combines two ordered streams into one ordered result stream, eliminating repetitions: (define...
Read more