Exercise 2.5- Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair a and b as the integer that is the product 2^a3^b. Give the corresponding definitions of the procedures cons, car, and cdr.
So far, we’ve seen an implementation of these procedures using lambda expression. By the way, it seems that we can implement them with only numbers and some arithmetic operations according to the problem, so let’s create that version of the procedures.
First of all, We need a procedure that tells us the power of 2 and 3 from a value.
(define (find-times-of-n n x)
(define (iter dev-x result)
(let ((r (remainder dev-x n)))
(if (= r 0) (iter (/ dev-x n) (+ result 1))
result)))
(iter x 0))
What we have to do for getting the power of n( in this case, 2 or 3 would be passed ) from value x is only devide n from x until the remainder of the value / n is non-zero.
Next, we’ll create procedure cons. This is easy because we only need to create a procedure that takes two arguments ( a and b ), and returns 2^a3^b. The procedure will be as follows:
(define (pow x n)
(define (iter i result)
(if (= i n) result (iter (+ i 1) (* result x))))
(iter 0 1))
(define (cons x y) (* (pow 2 x) (pow 3 y)))
Finally, we’ll create procedure car and cdr. Let’s use the procedure find-times-of-n:
(define (car cons) (find-times-of-n 2 cons))
(define (cdr cons) (find-times-of-n 3 cons))
If we want to get the output, you can implement the procedure like this:
(define (print-cons cons)
(newline)
(display "(")
(display (car cons))
(display ",")
(display (cdr cons))
(display ")"))
(define hoge (cons 61 22))
(print-cons hoge) ; (61, 22)
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…)
