Represent pairs of nonnegative integers using 2^a * 3^b Given the following exercise:


  Exercise 2.5
  
  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 2^a * 3^b. Give the
  corresponding definitions of the
  procedures cons, car, and cdr.


I wrote the following:

(define (cons a b) (* (expt 2 a) 
                      (expt 3 b)))
(define (car x)
  (if (= 0 (remainder x 3)) 
      (car (/ x 3))
      (/ (log x)
         (log 2))))

(define (cdr x)
  (if (= 0 (remainder x 2))
      (cdr (/ x 2))
      (/ (log x)
         (log 3))))


What do you think?
Your definition of cons is perfect.

Your definitions of car and cdr contain the log operation, which is a floating-point operation.  Not only are its results imprecise, it is not needed to solve this problem.  Furthermore, notice that the two definitions look very similar to each other.  Whenever one sees a repeated pattern, one ought to consider factoring it out.

To address the above two concerns, one may write a helper function, log-x, which is a specialized log function that takes integer parameters x and n and returns integer p such that x ^ p * y = n, where x does not divide y.  Then, car and cdr may call log-x, with x being 2 and 3 respectively.

In the following implementation, I have renamed the definitions so they do not conflict with primitives.

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

(define (log-x x n)
  (if (= (remainder n x) 0)
      (+ 1 (log-x x (/ n x)))
      0))

(define (car-np np)
  (log-x 2 np))

(define (cdr-np np)
  (log-x 3 np))