Ex 1.35

Demonstrating that the transformation is equal to φ is easily done. The book definition already described φ as satisfying the equation φ ² = φ + 1. Dividing this equation by φ yields an expression with φ itself on the left side, which is equivalent to the transformation.

To plug this into the fixed-point solver it suffices to use λ(x) = (+ 1 (/ 1 x)) and ensure that our initial value will not fail. Using 0 leads to immediate division by zero. But -1 will also lead to it after one iteration, and in fact there is a whole sequence of negative fractions that will cause the solver to fail (try to derive it). In the case of Dr Racket and some other varieties of Scheme, it’s actually fine to use 0.0 or -1.0, as the decimal point specifies a floating-point value. The math will support floating-point infinity as a usable value in division (turning 1 / infinity into 0), and the solution will be found. Another way to force floating-point is to use 1.0 in the lambda expression.

Before moving on, I just wanted to note that there are many ways to express φ as an equation, and to get one that is usable for a fixed-point solver can actually be a bit tricky. Importantly, the value typically known as ψ, which is equal to 1 – φ (≈ −0.618) is also a fixed point of the expression above. However, it’s fairly difficult to get the solver for this expression to converge to this value. There are other expressions of the golden ratio that can tend to either φ or ψ, depending on the initial value. A few are included in the solutions file, although after the next exercise, because that makes it easier to see how the result is developed.

Ex 1.36

In order to display the result and continue, another procedure is required for when the if condition is false. Instead of calling directly back to try, the procedure show-and-go is called, which displays the result and then calls try. These two form a mutually recursive process that (hopefully) terminates when a result is found.

Of course this solver can fail to terminate, as demonstrated by the example in the book where the values bounce back and forth and averaging is required. The fixed point being determined for this exercise doesn’t have that problem, but averaging does help it converge faster. There is still a restriction on initial values. In this case, the initial guess must be greater than 1. If it is less, values after the first guess will be negative, and this will produce an error when the logarithm is taken. Most any value larger than 1 will work well to demonstrate the reduction in required steps when averaging is used.

Ex 1.37

Calculating continued fractions is simply another recursive process, and isn’t all that different from anything we’ve seen before. The only thing to watch for is to make sure that the proper N_i and D_i values are used for the right index. It is easier to form the fraction by either reducing k in the iterative form, or increasing it in the recursive form. The recursive form requires an internally defined function to reverse. It’s also important to begin and end with the proper index, or else the functions that determine the values for the numerator and denominator may produce errors in the result.

In this particular case of calculating φ, those concerns are hidden since all the values are 1. However the choice of φ is not merely because it is a simple case and an approximation was found in an earlier problem. Since all the values in the continued fraction are at the minimum (1), φ actually represents a ‘worst case’ in terms of convergence for what’s known as simple continued fractions. For a given index i, the partially computed fraction for φ will be farther off than for another simple continued fraction. Put another way, the number of steps observed to get this fraction within a given tolerance will provide an upper limit for the continued fraction procedure, although only for a subset of fractions allowed by this general procedure.

Ex 1.38

With the continued fraction procedure working, we now must determine how to use it properly. In this case, the function for the denominator needs to generate a value for the index, following Euler’s sequence. There’s also the matter of adding the value 2 in order to actually approximate e and not e – 2.

My approach for D_i is to use the remainder of the index divided by 3, as the sequence repeats every three values. When it is in position to give the next value that isn’t 1, division by 3 is used to figure a new index. That index is multiplied by 2. In my solution I took advantage of the math functions remainder and quotient which return integer values from division.

Ex 1.39

Another exercise in using the previously defined function. This time we need to pass a procedure that has a special case. When the index is 1, only x is used, while the rest of the time x² is required. That’s easily accomplished with an if statement. The other sequence of terms is just the odd numbers, which are easy to generate.

Solutions 1.3.3