SICP exercise 2.05
From Drewiki
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 2a3b. 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.
The exercise asks us to represent the pair as the product 2a3b, so cons is straightforward:
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 2a3b. 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:
Test:
Output:
0
Output:
2
Output:
3
Output:
6
car and cdr are nearly the same and can be simplified using the techniques we learned in chapter 1 of the text:
Test again:
Output:
0
Output:
2
Output:
3
Output:
6
