SICP 1.3.3: “Formulating Abstractions with Higher-Order Procedures: Procedures as Returned Values”

(Structure and Interpretation of Computer Programs) 1.3.3

My 1.3.3 exercise solutions are also on Github here: https://github.com/bolducp/SICP/tree/master/exercises/chapter_01/1.3_exercises

This section focuses on demonstrating the usefulness of higher-order procedures by means of two specific, detailed examples: 1.) finding roots of an equation f(x) = 0; 2.) finding fixed points of a function.

“Finding roots of equations by the half-interval method

The half-interval method is a simple but powerful technique for finding roots of an equation f(x)=0f(x)=0 where f is a continuous function.” (pg 67)

The 2-page-long explanation of this method is a concise and well-articulated read, so I won’t try to summarize it here. It demonstrates both the definition of the high-order function and how it can be used within another function that also handles error cases. (see pg 67–68)

Finding fixed points of functions

A number xx is called a fixed point of a function f if x satisfies the equation f(x)=x.” (pg 68)

This section harkens back to the strategy used for finding square-roots in section 1.1.7 which also implemented a procedure for recursively applying a function until the return value is within a determined margin to the previous return value (in this case, within 0.00001). This example also demonstrates a method (called “average dumping”) of making subsequent guesses change by smaller intervals if the original implementation results in an infinite loop, “oscillating about the answer” (pg 70).

1.3.3 Exercises

My solutions are provided in gray text blocks below each exercise question.

Exercise 1.35

Show that the golden ratio (section 1.2.2) is a fixed point of the transformation x↦1+1/x, and use this fact to compute ϕ by means of the fixed-point procedure.

x = 1 + 1/xx^2 = x + 1

Turn this into a quadratic equation: x^2 - x - 1 = 0And use quadratic equation factorization to get the roots:x = 1/2(1 - √5)x = 1/2(1 + √5)

which shows what the golden ratio we learned in 1.2.2 (ϕ = (1 + √5) / 2 = 1.618033988)is a fixed point of the transformation x = 1 + 1/x.

We use the fixed-point function that SICP provides for us:

(define tolerance 0.00001)(define (fixed-point f first-guess)  (define (close-enough? v1 v2)    (< (abs (- v1 v2)) tolerance))  (define (try guess)    (let ((next (f guess)))      (if (close-enough? guess next)          next          (try next))))  (try first-guess))

and plug in the function that we're trying to find a fixed point for x = 1 + 1/x, which we can turn into the anonymous Scheme function (lambda (x) (+ 1 (/ 1 x))), and we can choose any starting value

Thus: (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0) = 1.6180327868852458

Exercise 1.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 ↦ 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 fixed-point with a guess of 1, as this would cause division by log(1)=0.)

(define tolerance 0.00001)

(define (fixed-point f first-guess)(define (close-enough? v1 v2)(< (abs (- v1 v2)) tolerance))(define (try guess)(let ((next (f guess)))(newline)(display next)(if (close-enough? guess next)next(try next))))(try first-guess))

(define (average x y)(/ (+ x y) 2))

(fixed-point (lambda (x) (/ (log 1000)(log x))) 1.5)

here's the solution using average dumping:(fixed-point (lambda (x) (average x (/ (log 1000)(log x)))) 1.5)

As shown in the screen shots below, using average dumping decreased the number of iterations by about two thirds.

without average dumping (left) vs. with average dumping (right)

Exercise 1.37

An infinite continued fraction is an expression of the form:

infinite continued fraction

As an example, one can show that the infinite continued fraction expansion with the Ni and the Di all equal to 1 produces 1ϕ, where ϕ 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:

Suppose that n and d are procedures of one argument (the term index i that return the Ni and Di of the terms of the continued fraction. Define a procedure cont-frac such that evaluating (cont-frac n d k) computes the value of the k-term finite continued fraction. Check your procedure by approximating 1ϕ 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 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.

(define (cont-frac n d k)(define (recursive-frac i)(if (< i k)(/ (n i) (+ (d i) (recursive-frac(+ i 1))))(/ (n i) (d i))))(recursive-frac 1))

; k = 12 gives us accuracy within 0.0001 of the expected 0.61803(cont-frac (lambda (i) 1.0)(lambda (i) 1.0)12);.6180257510729613

Part B- iterative version:

(define (cont-frac-iterative n d k)(define (iterative-frac i acc)(if (= i 0) acc(iterative-frac (- i 1)(/ (n i)(+ (d i) acc)))))(iterative-frac k (/ (n k)(d k))))

; k = 12 gives us accuracy within 0.0001 of the expected 0.61803(cont-frac-iterative (lambda (i) 1.0)(lambda (i) 1.0)11);.6180371352785146

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 Ni are all 1, and the Di are successively 1,2,1,1,4,1,1,6,1,1,8,… Write a program that uses your cont-frac procedure from exercise 1.37 to approximate e, based on Euler’s expansion.

(define (cont-frac d k)(define (recursive-frac i)(if (< i k) (/ 1.0 (+ (d i) (recursive-frac(+ i 1))))(/ 1.0 (d i))))(recursive-frac 1))

(define (d i)(if (= (remainder i 3) 2) (/ (+ i 1) 1.5)1))

(define (euler-e k)(+ 2.0 (cont-frac d k)))

(euler-e 10)

The tricky part here was figuring out the correct function implementation for d, such that Euler's Di pattern would be maintained. Also, rather than using my final iterative function solution and supplying d as a function to cont-frac-iterative, I refactored the recursive cont-frac implementation to use the new n and d function values directly.

Exercise 1.39

A continued fraction representation of the tangent function was published in 1770 by the German mathematician J.H. Lambert:

where x is in radians. Define a procedure (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.

(define (cont-frac-iterative n d k)(define (iterative-frac i acc)(if (= i 0) acc(iterative-frac (- i 1)(/ (n i)(+ (d i) acc)))))(iterative-frac k (/ (n k)(d k))))

(define (square x) (* x x))

(define (d i) (- (* 2 i) 1))

(define (tan-cf x k)(define (n i)(if (> i 1) (- (square x))x))(cont-frac-iterative n d k))