Exercises
Exercise 1.35
Show that the golden ratio \(\phi\) (the section Tree Recursion) is a fixed point of the transformation \(x \mapsto 1 + \frac{1}{x}\), and use this fact to compute \(\phi\) by means of the fixed-point/2 function.
Exercise 1.36
Modify fixed-point/2 so that it prints the sequence of approximations it generates, using io:format as shown in exercise 1.22. Then find a solution to \(x^x = 1000\) by finding a fixed point of \(x \mapsto \frac{log(1000)}{log(x)}\). (Use Erlang's math:log function, which computes natural logarithms.) Compare the number of steps this takes with and without average damping. (Note that you cannot start fixed-point/2 with a guess of 1, as this would cause division by \(log(1) = 0 \).)
Exercise 1.37
a. An infinite continued fraction is an expression of the form
\[ \begin{align} f= \frac{N_1}{D_1 + \frac{N_2}{D_2 + \frac{N_3}{D_3 + \cdots}}} \end{align} \]
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 \(frac{1}{\phi}\), where \(\phi\) is the golden ratio (described in the section Tree Recursion]). 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
\[ \begin{align} \frac{N_1}{D_1 + \frac{N_2}{\ddots + \frac{N_K}{D_K}}} \end{align} \]
Suppose that n and d are functions of one argument (the term index \(i\)) that return the \(N_i\) and \(D_i\) of the terms of the continued fraction. Define a function cont-frac/3 such that evaluating (cont-frac n d k) computes the value of the \(k\)-term finite continued fraction. Check your function by approximating \(\frac{1}{\phi}\) using
(cont-frac (lambda (i) 1.0)
(lambda (i) 1.0)
k)
for successive values of k. How large must you make k in order to get an approximation that is accurate to 4 decimal places?
b. If your cont-frac/3 function generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.
Exercise 1.38
In 1737, the Swiss mathematician Leonhard Euler published a memoir De Fractionibus Continuis, which included a continued fraction expansion for \(e - 2\), where \(e\) is the base of the natural logarithms. In this fraction, the \(N_i\) are all 1, and the \(D_i\) are successively \(1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, \cdot \). Write a program that uses your cont-frac/3 function from exercise 1.37 to approximate \(e\), based on Euler's expansion.
Exercise 1.39
A continued fraction representation of the tangent function was published in 1770 by the German mathematician J.H. Lambert:
\[ \begin{align} \tan r = \frac{r}{1 - \frac{r^2}{3 - \frac{r^2}{5 - \ddots}}} \end{align} \]
where \(x\) is in radians. Define a function (tan-cf x k) that computes an approximation to the tangent function based on Lambert's formula. k specifies the number of terms to compute, as in exercise 1.37.