Problem 17
The exponentiation algorithms in this section are based on performing exponentiation by means of repeated multiplication. In a similar way, one can perform integer multiplication by means of repeated addition. The following multiplication procedure (in which it is assumed that our language can only add, not multiply) is analogous to the expt procedure: (define (* a b) (if \((=b \quad 0)\) 0 \((+a(* a(-b \quad 1)))))\)
Problem 25
Alyssa P. Hacker complains that we went to a lot of extra work in writing expmod. After all, she says, since we already know how to compute exponentials, we could have simply written (define (expmod base exp \(\mathrm{m}\) ) (remainder (fast-expt base exp) \(\mathrm{m}\) )) Is she correct? Would this procedure serve as well for our fast prime tester? Explain.
Problem 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) \mathrm{m})\) \((\) expmod base \((/ \exp 2) \mathrm{m}))\) \((\) else \(\quad\) m)) \((\) remainder \((*\) base \((\) expmod base \((-\exp 1) \mathrm{m}))\) \(\quad\) 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 \(\Theta(\log n)\) process into a \(\Theta(n)\) process." Explain.
Problem 34
Suppose we define the procedure (define (f g) (g 2)) Then we have (f square) (f (lambda (z) (* z (+ z 1)))) 6 What happens if we (perversely) ask the interpreter to evaluate the combination (f \(f\) )? Explain.
Problem 36
Modify fixed-point so that it prints the sequence of approximations it generates, using the newline and display primitives shown in exercise \(1.22\). Then find a solution to \(x^{x}=1000\) by finding a fixed point of \(x \mapsto \log (1000) / \log (x)\). (Use Scheme's primitive \(\log\) procedure, which computes natural logarithms.) Compare the number of steps this takes with and without average damping. (Note that you cannot start \(\mathrm{fixed}\)-point with a guess of 1 , as this would cause division by \(\log (1)=0\).)
Problem 37
a. An infinite continued fraction is an expression of the form $$ f=\frac{N_{1}}{D_{1}+\frac{N_{2}}{D_{2}+\frac{N_{3}}{D_{3}+\cdots}}} $$ As an example, one can show that the infinite continued fraction expansion with the \(N_{i}\) and the \(D_{i}\) all equal to 1 produces \(1 / \phi\), where \(\phi\) is the golden ratio (described in section 1.2.2). One way to approximate an infinite continued fraction is to truncate the expansion after a given number of terms. Such a truncation-a so-called \(k\)-term finite continued fraction - has the form $$ \frac{N_{1}}{D_{1}+\frac{N_{2}}{\ddots+\frac{N_{K}}{D_{K}}}} $$ Suppose that \(\mathrm{n}\) and \(\mathrm{d}\) are procedures of one argument (the term index \(i\) ) that return the \(N_{i}\) and \(D_{i}\) of the terms of the continued fraction. Define a procedure cont-frac such that evaluating (cont- frac \(\mathrm{n} \mathrm{d} \mathrm{k}\) ) computes the value of the \(k\)-term finite continued fraction. Check your procedure by approximating \(1 / \phi\) using \(\begin{aligned} \text { (cont-frac (lambda (i) } & 1.0 \text { ) } \\ &\text { (lambda (i) } 1.0) \\ & \text { k) } \end{aligned}\) for successive values of \(\mathrm{k}\). How large must you make \(\mathrm{k}\) in order to get an approximation that is accurate to 4 decimal places? b. If your cont-frac procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.
Problem 41
Define a procedure double that takes a procedure of one argument as argument and returns a procedure that applies the original procedure twice. For example, if inc is a procedure that adds 1 to its argument, then (double inc) should be a procedure that adds 2 . What value is returned by (((double (double double)) inc) 5)
Problem 42
Let \(f\) and \(g\) be two one-argument functions. The composition \(f\) after \(g\) is defined to be the function \(x \mapsto f(g(x))\). Define a procedure compose that implements composition. For example, if inc is a procedure that adds 1 to its argument, ((compose square inc) 6) 49
Problem 46
Several of the numerical methods described in this chapter are instances of an extremely general computational strategy known as iterative improvement. Iterative improvement says that, to compute something, we start with an initial guess for the answer, test if the guess is good enough, and otherwise improve the guess and continue the process using the improved guess as the new guess. Write a procedure iterative-improve that takes two procedures as arguments: a method for telling whether a guess is good enough and a method for improving a guess. Iterative-improve should return as its value a procedure that takes a guess as argument and keeps improving the guess until it is good enough. Rewrite the sqrt procedure of section \(1.1 .7\) and the fixed-point procedure of section \(1.3 .3\) in terms of iterative-improve.
