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
(more…)
Exercise 1.37(a)- define k-term finite continued fraction.
Linear recursive version:
(define (cont-frac n d k)
(define (cont-frac-iter i)
(if (= i k)
(/ (n i) (d i))
(/ (n i) (+ (d i) (cont-frac-iter (+ i 1.0)))))
)
(cont-frac-iter 1)
)
Then how can we check if the number of k is enough for the calculation in the accuracy of 0.0001? We may be able to check it manually, but creating a checking function seems to be better for me.
(define (check-accuracy)
(define (iter k)
(if (< (abs (- (calc-ratio k) (/ 1 1.6180339887)) ) 0.0001)
k
(iter (+ k 1))
)
)
(iter 1)
)
And we get 10 iterations to get the accuracy in 0.0001.
In this case, the function passes calc-ratio method without using arguments. You can build an abstraction for checking arbitrary accuracy of arbitrary function if you prefer.
(define (check-accuracy accuracy f target)
(define (iter k)
(if (< (abs (- (f k) target) ) accuracy)
k
(iter (+ k 1))
)
)
(iter 1)
)
(more…)
Exercise 1.35 Show that the golden ratio is a fixed point of the transformation x|-> 1 + 1/x, and use this fact to compute the golden ration by means of the fixed-point procedure.
The following code works correctly.
(define (golden-ratio) (fixed-point (lambda (y) (avg y (+ 1 (/ 1 y)))) 1.0))
(golden-ratio) ; 1.6180311591702674
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.
To show each output with the newline and display primitives, we only need to change the fixed-point method as follows:
(define (fixed-point f first-guess)
(define (close-enough? v1 v2) (< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
; add two methods below to the existing code.
(display guess)
(newline)
:
:
Let’s try if the newly implemented feature works:
(golden-ratio)
And we’ll get the following output:
1.0
1.5
1.5833333333333333
1.6074561403508771
1.6147785476652068
1.61702925556443
1.617723628348796
1.6179380934832117
1.6180043565683029
1.6180248320058461
1.6180311591702674
(more…)
SICP Exercise 1.29 – Create more accurate method of numerical integration using Simpson’s Rule.
The following process works.
(define (sympson f a b n)
(define (term-num x)
(if (even? x) 2 4)
)
(define (y k) ( f (+ a (* k h))))
(define h (/ (- b a) n))
(define (next x) (+ x 1))
(define (term x)
(* (term-num x) ( y x ))
)
(* (/ h 3.0) (+ (y 0) (sum term 1 next (- n 1)) (y n)))
)
[shell]
Then let's compare this method to the one which isn't using Simpson's Rule. First we write the code as follows:
[shell]
(integral cube 0 1 0.001)
(sympson cube 0 1 10)
(sympson cube 0 1 100)
And we’ll get the following output.
0.24999987500000073
0.25
0.25
It looks like the new one outperforms the previous one.
SICP Exercise 1.30 – Rewrite sum method as a linear iterative process.
You can easily solve this by using what we’ve learned so far.
(define (sum term a next b)
(define (sum-iter a result)
(if (> a b) result
(sum-iter (next a) (+ result (term a))))
)
(sum-iter a 0)
)
(more…)
Exercise 1.17. Using the results of exercises 1.16 and 1.17, devise a procedure that generates an iterative process for multiplying two integers in terms of adding, doubling, and halving and uses a logarithmic number of steps.
In the exercise, the multiplication is implemented as follows:
(define (mul-1 a b)
(if (= b 0) 0 (+ a (mul-1 a (- b 1))))
)
This requires the order of b. The question here is that we want to implement the same function that requires the order proportional to some logarithm.
(define (double x) (+ x x))
(define (halve x) (/ x 2))
(define (mul-2 a b)
(cond ((= b 0) 0)
((even? b) (mul-2 (double a) (halve b)))
(else (+ a (mul-2 a (- b 1)))))
)
This only requires the order of log_2(b).
As a result, we get the following output:
(mul-1 100 5000000) ; memory shortage
(mul-2 100 5000000) ; 500000000
(mul-2 10000 50000000000000) ; 500000000000000000
