Записки сумасшедшего
в том числе SICP по-русски 2, по стопам великих!
Упражнение 1.31
Читай между строк.
а. Процедура sum — всего лишь простейшая из обширного множества подобных абстракций, которые можно выразить через процедуры высших порядков. Напишите аналогичную процедуру под названием product, которая вычисляет произведение значений функции в точках на указанном интервале. Покажите, как с помощью этой процедуры определить factorial. Кроме того, при помощи product вычислите приближенное значение π по формуле π = (2/3)*(4/3)*(4/5)*(6/5)*(6/7)*(8/7)...
б. Если Ваша процедура product порождает рекурсивный процесс, перепишите ее так, чтобы она порождала итеративный. Если она порождает итеративный процесс, перепишите ее так, чтобы она порождала рекурсивный.
------------------------------------
Сначала рекурсивная версия, после сложения в принципе ничего сложного:
time for recursive factorial of 500: 2 ms
time for iterative factorial of 500: 593 mks
Видно что, итеративная форма примерно в 4 раза быстрее.
Что касается вычисления Пи, то сначала я написал какие-то 3 мутные версии и отрабатывают они за отвратительно большое время. А все из-за сложности O(n^2).
Вот результаты вычисления:
t_pi:
3.14080852966447 --- 1264 ms
t_pi2:
3.14080852966447 --- 1262 ms
t_pi3:
3.14237736509388 --- 1406 ms
t_pi_good:
3.14237736509388 --- 9 ms
Причем последнюю версию можно улучшить еще в 2 раза, но этот метод я подсмотрел и поэтому решил не постить (.
а. Процедура sum — всего лишь простейшая из обширного множества подобных абстракций, которые можно выразить через процедуры высших порядков. Напишите аналогичную процедуру под названием product, которая вычисляет произведение значений функции в точках на указанном интервале. Покажите, как с помощью этой процедуры определить factorial. Кроме того, при помощи product вычислите приближенное значение π по формуле π = (2/3)*(4/3)*(4/5)*(6/5)*(6/7)*(8/7)...
б. Если Ваша процедура product порождает рекурсивный процесс, перепишите ее так, чтобы она порождала итеративный. Если она порождает итеративный процесс, перепишите ее так, чтобы она порождала рекурсивный.
------------------------------------
Сначала рекурсивная версия, после сложения в принципе ничего сложного:
1 (define (product_r term a next b)
2 (if (> a b)
3 1
4 (* (term a)
5 (product_r term (next a) next b))))
6
Теперь итеративная, тоже все просто:
1 (define (product_i term a next b)
2 (define (iter a result)
3 (if (> a b)
4 result
5 (iter (next a) (* result (term a)))))
6 (iter a 1))
7
8
Для теста написал процедуру вычисления факториала:
1 (define (fac_i n)
2 (define (inc i) (+ i 1))
3 (define (elem x) x)
4 (product_i elem 1 inc n))
5
6 (define (fac_r n)
7 (define (inc i) (+ i 1))
8 (define (elem x) x)
9 (product_r elem 1 inc n))
И результаты:time for recursive factorial of 500: 2 ms
time for iterative factorial of 500: 593 mks
Видно что, итеративная форма примерно в 4 раза быстрее.
Что касается вычисления Пи, то сначала я написал какие-то 3 мутные версии и отрабатывают они за отвратительно большое время. А все из-за сложности O(n^2).
1 (define (pi prec)
2 (define (inc i) (+ i 1))
3 (define (num n)
4 (define (f k)
5 (cond ((= 0 k) 2)
6 ((even? k) (f (- k 1)))
7 (else (+ 2 (f (- k 1))))))
8 (product_i f 0 inc n))
9 (define (den n)
10 (define (f k)
11 (cond ((= 0 k) 3)
12 ((even? k) (+ 2(f (- k 1))))
13 (else (f (- k 1)))))
14 (product_i f 0 inc n))
15 (* 4.0 (/ (num prec) (den prec))))
16 (define (pi2 prec)
17 (define (inc i) (+ i 1))
18 (define (num k)
19 (cond ((= 0 k) 2)
20 ((even? k) (num (- k 1)))
21 (else (+ 2 (num (- k 1))))))
22 (define (den k)
23 (cond ((= 0 k) 3)
24 ((even? k) (+ 2 (den (- k 1))))
25 (else (den (- k 1)))))
26 (define (f x)
27 (/ (num x) (den x)))
28 (* 4.0 (product_i f 0 inc prec)))
29 (define (pi3 prec)
30 (define (inc i) (+ i 1))
31 (define (num k)
32 (define (f n acc)
33 (cond ((= n k) acc)
34 ((even? n) (f (+ n 1) acc))
35 (else (f (+ n 1) (+ 2 acc)))))
36 (f 1 2))
37 (define (den k)
38 (define (f n acc)
39 (cond ((= n k) acc)
40 ((even? n) (f (+ n 1) (+ 2 acc)))
41 (else (f (+ n 1) acc))))
42 (f 0 1))
43 (define (f x)
44 (/ (num x) (den x)))
45 (* 4.0 (product_i f 1 inc prec)))
Потом я немного подумал и написал вот это:
1 ;1 2 1 2 1 2
2 ;2 1 2 1 2 1
3 (define (pi_good prec)
4 (define (inc i) (+ i 1))
5 (define (f x)
6 (if (odd? x)
7 (/ (+ x 1) (+ x 2))
8 (/ (+ x 2) (+ x 1))))
9 (* 4.0 (product_i f 1 inc prec)))
Эта версия работает значительно лучше.Вот результаты вычисления:
t_pi:
3.14080852966447 --- 1264 ms
t_pi2:
3.14080852966447 --- 1262 ms
t_pi3:
3.14237736509388 --- 1406 ms
t_pi_good:
3.14237736509388 --- 9 ms
Причем последнюю версию можно улучшить еще в 2 раза, но этот метод я подсмотрел и поэтому решил не постить (.