Laptops for Algernon

Excercise 1.40 – Define a procedure cubic that can be used together with the newtons-method procedure in expressions of the form (newtons-method (cubic a b c) 1) to approximate zeros of the cubic x^3 + ax^2 + bx + c.

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

(define (cubic a b c)
(lambda (x) (+ (cube x) (* a (square x)) (* b x) c)))

(newtons-method (cubic 3 2 5) 1) ; -2.9041608591349113

You can see answer of x^3+2x^2+5x+1 = 0 in the following link.
http://www.wolframalpha.com/input/?i=x%5E3%2B3x%5E2%2B2x%2B5%3D0&dataset=

Excercise 1.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)

(define (double f)
(lambda (x) (f (f x))))

((double square) 5) ; 625

Notice that the answer is 625, not 125 because we apply square for the square of 5(= 25).

Exercise 1.42. Let f and g be two one-argument functions. The composition f after g is defined to be the function x 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

(define (composition f g)
(lambda (x) (f (g x))))

((compose square inc) 6) ; 49

Excercise 1.43 – If f is a numerical function and n is a positive integer, then we can form the nth repeated application of f, which is defined to be the function whose value at x is f(f(…(f(x))…)). For example, if f is the function x x + 1, then the nth repeated application of f is the function x x + n. If f is the operation of squaring a number, then the nth repeated application of f is the function that raises its argument to the 2nth power. Write a procedure that takes as inputs a procedure that computes f and a positive integer n and returns the procedure that computes the nth repeated application of f. Your procedure should be able to be used as follows:
((repeated square 2) 5) ;625

We pass the default value of iteration and procedure itself in repeated-iter.
The result will be executed at last.

(define (repeated f n)
(define (repeated-iter i result)
(if (= i n)
(lambda (x) (result x))
(repeated-iter (+ i 1) (double result))))
(repeated-iter 1 f))

((repeated square 2) 5) ; 625

Excercise 1.44 – Write a procedure smooth that takes as input a procedure that computes f and returns a procedure that computes the smoothed f. It is sometimes valuable to repeatedly smooth a function (that is, smooth the smoothed function, and so on) to obtained the n-fold smoothed function. Show how to generate the n-fold smoothed function of any given function using smooth and repeated from exercise 1.43.

Notice that in exercise 1.43, we passed the number 5 to the square procedure as an argument, but this time we’re passing a procedure to it. At the first time, we feel confused for the diversity of the expression. however you can get the picture of this by imagining that we’re passing an “argument” for the procedure.

(define (smooth f)
(lambda (x) (/ (+ (f (+ x dx)) (f x) (f (- x dx))) 3) ))

(define (n-fold-smooth n f)
((repeated smooth n) f))

((n-fold-smooth 5 cube) 3) ; apply smooth procedure 5 times

Excercise 1.45 – Do some experiments to determine how many average damps are required to compute nth roots as a fixed-point search based upon repeated average damping of y |-> x / y^n-1.

First we create a procedure so that we can do the experiment with some small values.

(define (n-times-average-damp n)
(repeated average-damp n))

(define (n-sqrt x)
(fixed-point-of-transform (lambda (y) (/ x (* y y ... )))
(n-times-average-damp ... ))
1.0))

You see the factorial of y in the function. This means “n-1″ in the expression.
That is, You can get x^n when the (n-1)th power is excecuted.

Finally we get following result of the experiment.

(power) (required number of average-damp execution)
y^1 = 1 time
y^2 = 1 time
y^3 = 2 times
:
:
y^8 = 3 times
:
:
y^16 = 4 times

So the number of required execution of average-damp will be log_2(n).

Use this to implement a simple procedure for computing nth roots using fixed-point, average-damp, and the repeated procedure of exercie 1.43. Assume that any arithmetic operations you need are available as primitives.

Because the number should be an integer, we’re using a primitive procedure floor.

(define (log_2 x) (/ (log x) (log 2)))

(define (n-sqrt x n)
(fixed-point-of-transform
(lambda (y) (/ x ((repeated (lambda (x) (* x y)) (- n 1)) 1)))
(n-times-average-damp (floor (log_2 n)))
1.0))

Excercise 1.46 – 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.

(define (iterative-improve enough? improve)
(lambda (guess)
(define (iter guess)
(let ((next (improve guess)))
(if (enough? next guess)
next
(iter next))))
(iter guess)))

Rewrite the sqrt procedure of section 1.1.7 and the fixed-point procedure of section 1.3.3 in terms of iterative-improve.

The sqrt procedure will be as follows:

(define (sqrt x)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) 0.0000001))
(iterative-improve
close-enough?
(lambda (y) (average y (/ x y)))))

((sqrt 3) 1.0); 1.7320508075688772

And the fixed-point procedure will be as follows:

(define (fixed-point-improved f)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) 0.0000001))
(iterative-improve
close-enough?
(lambda (x) (average x (f x)))))

If you think that you want to use fixed-point-improved procedure in the sqrt procedure, the code will be like this:

(define (sqrt x)
(fixed-point-improved (lambda (y) (/ x y))))

((sqrt 3) 1.0) ; 1.7320508075688772

“1.0″ is the number for first guess. Although you can create this in the procedure, it would be efficient sometimes, like when you need to guess numbers with some logarithm ( in this time, we might pass 2.0 instead of 1.0 because log(1) = 0 ).