Skip to main content.
-->
May 15th, 2005

Solution to SICP Exercise 1.20

Structure and Interpretation of Computer Programs

Solution to Exercise 1.20:

;;; Normal Order

; remainder count: 0
(gcd 206 40)

; rc: 0
(if (= 40 0)
    206
    (gcd 40 (remainder 206 40))) 

; rc: 0
(gcd 40 (remainder 206 40)) 

; rc: 0
(if (= (remainder 206 40) 0)
    40
    (gcd (remainder 206 40)
         (remainder 40 (remainder 206 40))))

; rc: 1
(if (= 6 0)
    40
    (gcd (remainder 206 40)
         (remainder 40 (remainder 206 40))))

; rc: 1
(gcd (remainder 206 40)
     (remainder 40 (remainder 206 40)))

; rc: 1
(if (= (remainder 40 (remainder 206 40)) 0)
    (remainder 206 40)
    (gcd (remainder 40 (remainder 206 40))
         (remainder (remainder 206 40)
                    (remainder 40
                               (remainder 206 40)))))

; rc: 2
(if (= (remainder 40 6) 0)
    (remainder 206 40)
    (gcd (remainder 40 (remainder 206 40))
         (remainder (remainder 206 40)
                    (remainder 40
                               (remainder 206 40)))))

; rc: 3
(if (= 4 0)
    (remainder 206 40)
    (gcd (remainder 40 (remainder 206 40))
         (remainder (remainder 206 40)
                    (remainder 40
                               (remainder 206 40)))))

; rc: 3
(gcd (remainder 40 (remainder 206 40))
     (remainder (remainder 206 40)
                (remainder 40
                           (remainder 206 40))))

; rc: 3
(if (= (remainder (remainder 206 40)
                  (remainder 40
                             (remainder 206 40)))
       0)
    (remainder 40 (remainder 206 40))
    (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))))))

; rc: 4
(if (= (remainder 6
                  (remainder 40
                             (remainder 206 40)))
       0)
    (remainder 40 (remainder 206 40))
    (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))))))

; rc: 5
(if (= (remainder 6
                  (remainder 40
                             6))
       0)
    (remainder 40 (remainder 206 40))
    (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))))))

; rc: 6
(if (= (remainder 6 4) 0)
    (remainder 40 (remainder 206 40))
    (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))))))

; rc: 7
(if (= 2 0)
    (remainder 40 (remainder 206 40))
    (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))))))

; rc: 7
(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)))))

; rc: 7
(if (= (remainder (remainder 40
                             (remainder 206 40))
                  (remainder (remainder 206 40)
                             (remainder 40
                                        (remainder 206 40))))
       0)
    (remainder (remainder 206 40)
               (remainder 40
                          (remainder 206 40)))
    (gcd (remainder (remainder 40
                               (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40
                                          (remainder 206 40))))
         (remainder (remainder (remainder 206 40)
                               (remainder 40
                                          (remainder 206 40)))
                    (remainder (remainder 40
                                          (remainder 206 40))
                               (remainder (remainder 206 40)
                                          (remainder 40
                                                     (remainder 206 40)))))))

; rc: 14 (there were 7 calls to remainder in the = form above)
(if (= 0 0)
    (remainder (remainder 206 40)
               (remainder 40
                          (remainder 206 40)))
    (gcd (remainder (remainder 40
                               (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40
                                          (remainder 206 40))))
         (remainder (remainder (remainder 206 40)
                               (remainder 40
                                          (remainder 206 40)))
                    (remainder (remainder 40
                                          (remainder 206 40))
                               (remainder (remainder 206 40)
                                          (remainder 40
                                                     (remainder 206 40)))))))

; rc: 14
(remainder (remainder 206 40)
           (remainder 40
                      (remainder 206 40)))

; rc: 15
(remainder 6
           (remainder 40
                      (remainder 206 40)))

; rc: 16
(remainder 6 (remainder 40 6))

; rc: 17
(remainder 6 4)

; rc: 18
2

For normal order, remainder is performed 18 times.

;;; Applicative Order

; rc: 0
(gcd 206 40)

; rc: 0
(if (= 40 0)
    206
    (gcd 40 (remainder 206 40))) 

; rc: 0
(gcd 40 (remainder 206 40))

; rc: 1
(gcd 40 6)

; rc: 1
(if (= 6 0)
    40
    (gcd 6 (remainder 40 6))) 

; rc: 1
(gcd 6 (remainder 40 6))

; rc: 2
(gcd 6 4)

; rc: 2
(if (= 4 0)
    6
    (gcd 4 (remainder 6 4))) 

; rc: 2
(gcd 4 (remainder 6 4))

; rc: 3
(gcd 4 2)

; rc: 3
(if (= 2 0)
    4
    (gcd 2 (remainder 4 2))) 

; rc: 3
(gcd 2 (remainder 4 2))

; rc: 4
(gcd 2 0)

; rc: 4
(if (= 0 0)
    2
    (gcd 0 (remainder 2 0))) 

; rc: 4
2

For applicative order, remainder is only performed four times.

Posted by Ken Dyck in Programming

This entry was posted on Sunday, May 15th, 2005 at 9:21 am and is filed under Programming. You can follow any responses to this entry through the comments RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to “Solution to SICP Exercise 1.20”

  1. bhrgunatha says:

    This was tedious:
    I got 32 for normal order and 5 for applicative order:

    applicative order (gcd 206 40)
    zero? 40
    (gcd (40 (remainder 206 40)))
    rc 01:: (gcd 40 6)
    zero? 6
    (gcd 6 (remainder 40 6))
    rc 02:: (gcd 6 4)
    (gcd 6 4)
    zero? 4
    (gcd 4 (remainder 6 4))
    rc 03:: (gcd 4 2)
    zero? 2
    (gcd 2 (remainder 4 2))
    rc 04:: (gcd 2 2)
    zero? 2
    (gcd (2 (remainder 2 2)))
    rc 05:: (gcd (2 0))
    zero? 0
    -> 2

    I’m so fed up with this one I can’t be bothered checking why my answer for normal order is different.

    January 15th, 2008 at 9:52 am
  2. Zachary says:

    I got the same, although I expressed it much more compactly. Because of the tricky nature of if evaluation in lisp/scheme, the predicate is fully evaluated whether we are in applicative or normal-order, so assume in each (gcd a b) that b is evaluated completely. Thus:

    
(gcd 206 40)
(gcd 40 (mod 206 40)) ;; b has one mod, so rc = 1
(gcd (mod 206 40) (mod 40 (mod 206 40))) ;; rc = 1 + 2
(gcd (mod 40 (mod 206 40)) (mod (mod 206 40) (mod 40 (mod 206 40)))) ;; rc = 1 + 2 + 4 = 7
(gcd (mod (mod 206 40) (mod 40 (mod 206 40))) (mod (mod 40 (mod 206 40)) (mod (mod 206 40) (mod 40 (mod 206 40))))) ;; rc = 7 + 7 = 14
;; the result of the if here is zero, so we evaluate a
(mod (mod 206 40) (mod 40 (mod 206 40))) ;; 4 mods, rc = 7 + 7 + 4 = 18

    January 25th, 2008 at 1:33 pm

Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>