(define (simpson f a b n)
(define h (/ (- b a) n))
(define (y k) (f (+ a (* k h))))
(define (term x)
(cond ((= x 0) (y 0))
((= x n) (y n))
((odd? x) (* 4 (y x)))
((even? x) (* 2 (y x)))))
(* (/ h 3) (sum term 0 inc n)))With n=100 this gives us 0.24999999999999992, and with n=1000 we get 0.2500000000000003. So it's clearly more accurate than the results given by the integral function.
(define (iterative-sum term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a)
(+ (term a) result))))
(iter a 0))Part 1:
(define (product term a next b)
(if (> a b)
1
(* (term a)
(product term (next a) next b))))
(define (factorial n)
(product identity 1 inc n))
(define (pi accuracy)
(define (term n)
(if (even? n)
(/ n (- n 1))
(/ (- n 1) n)))
(* 4 (product term 3 inc (+ accuracy 3))))Part 2:
(define (iterative-product term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (* (term a) result))))
(iter a 1))Part 1:
(define (accumulate
combiner null-value term a next b)
(if (> a b)
null-value
(combiner (term a)
(accumulate combiner
null-value
term
(next a)
next
b))))
(define (acc-sum term a next b)
(accumulate + 0 term a next b))
(define (acc-product term a next b)
(accumulate * 1 term a next b))Part 2, an iterative version.
(define (iter-accumulate
combiner null-value term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a)
(combiner (term a)
result))))
(iter a null-value)(define (filtered-accumulate
filter? combiner null-value term a next b)
(define (filtered-term a)
(if (filter? a) (term a) null-value))
(if (> a b)
null-value
(combiner (filtered-term a)
(filtered-accumulate filter?
combiner
null-value
term
(next a)
next
b))))Part 1:
(define (sum-of-squares-of-prime-numbers a b)
(filtered-accumulate prime? + 0 square a inc b))Part 2:
(define (product-of-relatively-prime-numbers-to n)
(define (gcd a b) (if (= b 0) a (gcd b (remainder a b))))
(define (relprime? i) (= (gcd i n) 1))
(filtered-accumulate relprime? * 1 identity 1 inc n))(f f) will call the function f and pass '2' as its argument. Then function f will try to call 2 as a function (and pass 2 to it), but this will run into an interpreter error since 2 is not a function. The error is get is "Error: 2 is not a function".
Show the golden ration is a fixed point of the transformation.
Need to show that (1 + sqrt(5)) / 2 = 1 + 1 / ((1 + sqrt(5)) / 2)
RHS becomes 1 + (2 / (1 + sqrt(5)))
Which becomes (3 + sqrt(5)) / (1 + sqrt(5))
Multiply LHS by (1 + sqrt(5)) and RHS by 2 to get
(1 + sqrt(5))^2 = (3 + sqrt(5)) * 2
Both expand to 6 + 2 * sqrt(5)So we can compute it with the fixed point method as follows:
(define (golden-ratio)
(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0))This gives a value of 1.6180327868852458.
(define (modified-fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2))
tolerance))
(define (try guess count)
(print count ". " guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next (+ count 1)))))
(try first-guess 0))
(define (log-test guess)
(modified-fixed-point
(lambda (x) (/ (log 1000) (log x)))
guess))
(define (damped-log-test guess)
(modified-fixed-point
(lambda (x) (average x (/ (log 1000) (log x))))
guess))With an initial guess of 5, log-test takes 27 guesses but damped-log-test only takes 7. Both settle around 4.555539314360711. With an initial guess of 1000, log-test takes 35 and damped-log-test takes 16.
(define (cont-frac n d k)
(define (cont-frac-rec i)
(if (= i k)
(/ (n k) (d k))
(/ (n i) (+ (d i) (cont-frac-rec (+ i 1))))))
(cont-frac-rec 1))
(cont-frac
(lambda (x) 1)
(lambda (x) 1)
iterations))The expression will give 0.6180555555555556 when iterations is 11, which is accurate to 4 decimal places.
Part 2, an iterative version:
(define (iterative-cont-frac n d k)
(define (cont-frac-iter i result)
(cond ((= i 1) result)
(else (cont-frac-iter (- i 1)
(/ (n i)
(+ (d i) result))))))
(cont-frac-iter k 0))This one takes one additional iteration to be as accurate.
(define (e-tester iterations)
(+ 2 (cont-frac
(lambda (x) 1.0)
(lambda (x)
(if (= (remainder (- x 2) 3) 0)
(* 2 (+ (/ (- x 2) 3) 1))
1))
iterations)))It was relatively easier to get the above but I got stuck for a while because it wasn't giving me a correct answer, until I found an error in my count-frac methods that hadn't surfaced before.
(define (tan-cf x k)
(cont-frac
(lambda (y) (if (= y 1) x (- (* x x))))
(lambda (y) (- (* 2 y) 1))
k))(define (cubic a b c)
(lambda (x) (+ (cube x) (* a (square x)) (* b x) c)))
(newtons-method (cubic 1 1 1) 1)21 is returned. The mega-double procedure adds 16 since it multiplies by power of two every time its called on itself (I had to run this to be sure).
(define (compose f g)
(lambda (x) (f (g x))))(define (repeated f n)
(if (= n 1)
f
(repeated (compose f f) (- n 1))))(define (smooth f)
(lambda (x)
(/ (+ (f x) (f (+ x dx)) (f (- x dx)))
3)))
(define (n-fold-smooth f n)
(repeated (smooth f) n))This is one to revisit, I almost got there on my own but not quite.
(define (log2 x) (/ (log x) (log 2)))
(define (nth-root n x)
(fixed-point
((repeated
average-damp (floor (log2 n)))
(lambda (y)
(/ x (expt y (- n 1)))))
1.0))Come back to this one, I am impatient and I want to move on.