sicp-ex-1.20


The process generated using the normal-order evaluation is the following. It performs 18 remainder operations: 14 when evaluating the condition and 4 in the final reduction phase.

  
 (gcd 206 40) 
  
 (if (= 40 0) ...) 
  
 (gcd 40 (remainder 206 40)) 
  
 (if (= (remainder 206 40) 0) ...) 
  
 (if (= 6 0) ...) 
  
 (gcd (remainder 206 40) (remainder 40 (remainder 206 40))) 
  
 (if (= (remainder 40 (remainder 206 40)) 0) ...) 
  
 (if (= 4 0) ...) 
  
 (gcd (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) 
  
 (if (= (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) 0) ...) 
  
 (if (= 2 0) ...) 
  
 (gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))) 
  
 (if (= (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) 0) ...) 
  
 (if (= 0 0) ...) 
 (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) 
  

The number 'R' of remainder operations executed by the normal-order evaluation process is given by the formula

         R = SUM(i from 1 to n, fib(i) + fib(i - 1)) - 1 

where n is the number of gcd invocations required to compute the (gcd a b). The first invocation does not need to compute remainder thus the -1

R is given by the following function:

 (define (count-remainders n) 
     (define (loop n sum) 
         (if (= 0 n) (- sum 1) 
             (loop (- n 1) (+ sum (fib n) (fib (- n 1)))))) 
     (loop n 0)) 

In this particular case that is:

 (count-remainders 5) 
 => 18 

The process generated using the applicative-order evaluation is the following. It performs 4 remainder operations.

  
 (gcd 206 40) 
  
 (gcd 40 (remainder 206 40)) 
  
 (gcd 40 6) 
  
 (gcd 6 (remainder 40 6)) 
  
 (gcd 6 4) 
  
 (gcd 4 (remainder 6 4)) 
  
 (gcd 4 2) 
  
 (gcd 2 (remainder 4 2)) 
  
 (gcd 2 0) 
  
 2 
  

It seems that the formula

         R = SUM(i from 1 to n, fib(i) + fib(i - 1)) - 1 

is incorrect. One can easy check this by letting n=2. The correct count should be 1 while the formula gives 2.

Let b_i be the value of b at the n'th invocation of gcd(a,b). Let b(i) be the count of remainder procedure needed to calculate b_i. Similarly, define a_i and a(i). It is easy to check that

1. a_i=b_(i-1) and thus a(i)=b(i-1).

2. b(i+1) = a(i) + b(i) + 1 = b(i-1) + b(i) + 1 because b_(i+1) = a_i mod b_i

Based on my own derivation, R should be

b(1)+b(2)+...+b(n)+b(n-1) with b(1)=0, b(2)=1 and b(n)=b(n-1)+b(n-2)+1, which is not equivalent with the above R formula


<< Previous exercise (1.19) | sicp-solutions | Next exercise (1.21) >>