-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path1_20
33 lines (25 loc) · 970 Bytes
/
1_20
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
Here's an illustration of the (gcd 206 40) process using normal-order evaluation.
(I will be representing remainder with r)
(gcd 206
40)
(gcd 40
(r 206 40))
(gcd (r 206 40)
(r 40 (r 206 40)))
(gcd (r 40 (r 206 40))
(r (r 206 40) (r 40 (r 206 40))))
(gcd (r (r 206 40) (r 40 (r 206 40)))
(r (r 40 (r 206 40)) (r 40 (r 206 40))))
It is at this point that the second argument of the gcd process (referred to as "right" from here, evaluates to 0).
Therefore, now the first argument ("left") of the gcd process is evaluated.
With these both, the total comes to 18 remainders.
Here's psuedo-code to calculate the total number of remainders (if it takes k steps, in normal-order:
left = right = tot_rem = 0
while (k > 0):
temp = left
left = right
right = 1 + temp + right
tot_rem += right
k -= 1
tot_rem += left
In applicative-order evaluation, the total number of remainders is 4. That is, tot_rem = k (number of steps)