Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 2.05

From Drewiki
Jump to: navigation, search

Problem

Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair a and b as the integer that is the product <math>2^a3^b</math>. Give the corresponding definitions of the procedures cons, car, and cdr.

Solution

For this exercise we'll need one of our exponentiation procedures from chapter 1 of the text.

(define (square x) (* x x))
 
(define (fast-expt b n)
  (fast-expt-iter b n 1))
 
(define (fast-expt-iter b n a)
  (cond ((= n 0) a)
        ((even? n) (fast-expt-iter (square b) (/ n 2) a))
        (else (fast-expt-iter b (- n 1) (* a b)))))

The exercise asks us to represent the pair as the product <math>2^a3^b</math>, so cons is straightforward:

(define (cons a b)
  (* (fast-expt 2 a) (fast-expt 3 b)))

For any given pair a and b represented in this fashion, there are a factors of 2 and b factors of 3. We can use the fact that 2 and 3 are relatively prime (i.e., they share no common factors) to implement car and cdr. Assume that p is the pair represented by <math>2^a3^b</math>. When a is greater than zero (i.e., when p is a multiple of 2), then the remainder of p divided by 2 is zero; but when a is zero (i.e., when p contains no multiples of 2), the remainder of p divided by 2 is non-zero. Therefore, by repeatedly dividing by 2 until the remainder is non-zero, we can determine the value of a: in fact, a's value is the number of times we can repeatedly divide by 2, starting with pair p, such that the remainder is zero.

By the same argument, we can repeatedly divide a pair p by 3 until the remainder is non-zero to determine b.

Here are implementations of car and cdr which implement this strategy:

(define (car p)
  (if (= (remainder p 2) 0) (+ 1 (car (/ p 2)))
      0))
 
(define (cdr p)
  (if (= (remainder p 3) 0) (+ 1 (cdr (/ p 3)))
      0))

Test:

(car (cons 0 2))

Output:

0
(cdr (cons 0 2))

Output:

2
(car (cons 3 6))

Output:

3
(cdr (cons 3 6))

Output:

6


car and cdr are nearly the same and can be simplified using the techniques we learned in chapter 1 of the text:

(define (car p) (count-factors p 2))
 
(define (cdr p) (count-factors p 3))
 
(define (count-factors p n)
  (if (= (remainder p n) 0) (+ 1 (count-factors (/ p n) n))
      0))

Test again:

(car (cons 0 2))

Output:

0
(cdr (cons 0 2))

Output:

2
(car (cons 3 6))

Output:

3
(cdr (cons 3 6))

Output:

6
Personal tools