Represent pairs of nonnegative integers using 2^a * 3^b

Question

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?

Answer 1

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))