-
Notifications
You must be signed in to change notification settings - Fork 1
/
Exercise 1.32 accumulator.rkt
executable file
·144 lines (125 loc) · 3.74 KB
/
Exercise 1.32 accumulator.rkt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
; Exercise 1.32. a. Show that sum and product (exercise 1.31) are both special cases of a
; still more general notion called accumulate that combines a collection of terms, using
; some general accumulation function:
; (accumulate combiner null-value term a next b)
; Accumulate takes as arguments the same term and range specifications as sum and product,
; together with a combiner procedure (of two arguments) that specifies how the current term
; is to be combined with the accumulation of the preceding terms and a null-value that
; specifies what base value to use when the terms run out. Write accumulate and show how sum
; and product can both be defined as simple calls to accumulate.
; b. If your accumulate procedure generates a recursive process, write one that generates
; an iterative process. If it generates an iterative process, write one that generates a
; recursive process.
; SOLUTION
(define (accumulate-recur combiner null-value term a next b)
(if
(> a b) null-value
(combiner (term a) (accumulate-recur combiner null-value term (next a) next b))
)
)
(define (accumulate-iter combiner null-value term a next b)
(define (iter x result)
(if (> x b)
result
(iter (next x) (combiner (term x) result))
)
)
(iter a null-value)
)
(define (sum-recur term a next b)
(accumulate-recur + 0 term a next b)
)
(define (sum-iter term a next b)
(accumulate-iter + 0 term a next b)
)
(define (product-recur term a next b)
(accumulate-recur * 1 term a next b)
)
(define (product-iter term a next b)
(accumulate-iter * 1 term a next b)
)
(define (inc x)
(+ x 1)
)
(define (identity x)
x
)
(define (factorial-recur n)
(product-recur identity 1 inc n)
)
(define (factorial-iter n)
(product-iter identity 1 inc n)
)
; Higher values of n will give better approximations of pi
(define (pi-approx-recur n)
(* (product-recur pi-approx-term 1 inc n) 4)
)
(define (pi-approx-iter n)
(* (product-iter pi-approx-term 1 inc n) 4)
)
(define (pi-approx-term x)
(/ (* (* 2.0 x) (* 2 (+ x 1))) (square (+ (* 2 x) 1)))
)
(define (square x)
(* x x)
)
; Tests
> (sum-recur identity 1 inc 20)
210
> (sum-recur identity 1 inc 35)
630
> (sum-iter identity 1 inc 35)
630
> (product-recur identity 1 inc 35)
10333147966386144929666651337523200000000
> (product-iter identity 1 inc 35)
10333147966386144929666651337523200000000
> (factorial-recur 24)
620448401733239439360000
> (factorial-iter 24)
620448401733239439360000
> (factorial-iter 100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
> (factorial-recur 100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
> (pi-approx-recur 1)
(pi-approx-recur 5)
(pi-approx-recur 10)
(pi-approx-recur 100)
(pi-approx-recur 1000)
(pi-approx-recur 10000)
(pi-approx-recur 100000)
(pi-approx-recur 1000000)
3.5555555555555554
3.275101041334807
3.213784940293188
3.1493784731686008
3.142377365093882
3.1416711865344946
3.141600507501579
3.141593438981073
> (pi-approx-iter 1)
(pi-approx-iter 5)
(pi-approx-iter 10)
(pi-approx-iter 100)
(pi-approx-iter 1000)
(pi-approx-iter 10000)
(pi-approx-iter 100000)
(pi-approx-iter 1000000)
(pi-approx-iter 10000000)
(pi-approx-iter 100000000)
(pi-approx-iter 1000000000)
(pi-approx-iter 10000000000)
(pi-approx-iter 100000000000)
3.5555555555555554
3.2751010413348074
3.213784940293189
3.149378473168601
3.1423773650938855
3.1416711865345
3.1416005075026887
3.1415934389872975
3.1415927321451758
3.1415926690744156
3.1415926440043203
3.141592640508495