Artisan Coder

James Long is solving some SICP exercises and posting the solutions in his blog. Every software developer, me included, should do that! He posted yesterday the solution for exercise 2.5, which reads:

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.

He confesses that couldn’t figure the math, and points to a solution in the schemewiki. In the end, it is assumed that the code works because one base used is even (2) and the other is odd (3), so the resulting integer can only be divided by 2 a number of times equal to a. In fact, the solution to this problem has nothing to do with parity, but with the fundamental theorem of arithmetic:

the fundamental theorem of arithmetic (or the unique-prime-factorization theorem) states that any integer greater than 1 can be written as a unique product (up to ordering of the factors) of prime numbers. For example,

6936 = 2^3 * 3^1 * 17^2
1200 = 2^4 * 3^1 * 5^2

are two numbers satisfying the hypothesis of the theorem that can be written as the product of prime numbers.

What this means is that if we use prime numbers as bases for the construction of pairs as numbers, we have a guarantee that we will be able to retrieve the original numbers back, because the numbers we have encoded in the “pair” are the only representation possible. So what really matters is that 2 and 3 are prime numbers. In fact, using 5 and 7 as bases would work perfectly as well:

(define *const-m* 5)
(define *const-n* 7)
 
;; "integer logarithm", a friendly misnomer
(define (ilog a b)
  (let loop ((i 0)
             (a a))
    (if (zero? (remainder a b))
    (loop (+ i 1) (quotient a b))
    i)))
 
(define (kons a b)
  (* (expt *const-m* a) (expt *const-n* b)))
 
(define (kar a)
  (ilog a *const-m*))
 
(define (kdr a)
  (ilog a *const-n*))

Let’s see a quick session. By the way, Scheme’s support for integers of arbitrary size really helps here:

> (define a (kons 23 56))
> a
2522320911913220782729737303110106900811912937176227569580078125
> (kar a)
23
> (kdr a)
56
> (define b (kons 127 99))
> (kar b)
127
> (kdr b)
99

As a side note, instead of something like my ilog, the solution in schemewiki uses this function:

(define (count-0-remainder-divisions n divisor) 
  (define (iter try-exp) 
   (if (= 0 (remainder n (exp divisor try-exp))) 
       (iter (+ try-exp 1))  ;; Try another division. 
       (- try-exp 1))) 
 
  ;; We don't need to try 0 divisions, as that will obviously pass. 
  (iter 1))

It uses exponentiation in every step of the loop, which strikes me as very inefficient.