SICP - exercise 2.5 - representing pairs of nonnegative integers using only numbers and arithmetic operations

Question

From SICP

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^x*3^y. Give the corresponding definitions of the procedures cons, car, and cdr.

Please review my code.

(define (cons x y)
    (* (expt 2 x) (expt 3 y)))

I created repeat-divide to find x and y.

(define (repeat-divide x y)
    (if (> (remainder x y) 0)
        0
    (+ 1 (repeat-divide (/ x y) y))))

Selectors

(define (car p) (repeat-divide p 2))

(define (cdr p) (repeat-divide p 3))

I am not mathematically inclined, so I feel this solution might be extremely inefficient. How can I make this code better and more efficient?

Answer 1

Well this is going to be inefficient no matter what, it's just that way. So we aren't going to improve the built-in expt, so that leaves repeat-divide for improvement. Let call it de-factor.

So first I thought something like

(define (de-factor p n)
 (let* ((max-expt (ceiling (/ (log p) (log n))))
             ;;log of p in base n
        (gcd-of (gcd p (expt n max-expt)))
        (res (/ (log gcd-of) (log n))))
   res))

which works so long as log internal is accurate enough to return the closest integer.It runs into significant rounding errors for some x and y less than a hundred. If you built a very large log table you could solve in log time so long as you could accurately cast from your log table to the input x and y. (gcd runs in log time) Of course in such case the memory overhead of such a table or map would be huge, so not really that great of an optimization.

(define (de-factor p n)
 (let* ((rough-max-expt (let loop ((x 1))
                           (if (>= (expt n x) p) 
                               x
                               (loop (* 2 x)))))              
             ;;can't use log trick, returns inexact math
        (gcd-of (gcd p (expt n rough-max-expt))))
    (x-to-what-y n gcd-of)))

(define (x-to-what-y x n) ;return y such that (= n (expt x y)) is #t
 (if (= n 1)
     0
    (let loop ((y 1) (step 1) (acc x) (narrow? #f))
      (cond ((= acc n) y)
            ((< step 1) (error x step acc narrow?))
            (else (let ((next (* acc (expt x step))))
                     (if (<= next n)
                         (loop (+ y step) 
                               (if narrow? (/ step 2) (* step 2))
                               next
                               narrow?)
                         (loop y
                               (/ step 2)
                               acc
                               #t))))))))

Minimal changes to the rest

(define (cons x y)
    (* (expt 2 x) (expt 3 y)))


(define (car p) (de-factor p 2))

(define (cdr p) (de-factor p 3))

As far as performance it's still less than linear because of the exact bignum math. (cdr (cons 12345 54321)) returns 12345 in a few seconds, but (cdr (cons 123456 654321)) in about a minute and a half.

When I tried your (cdr (car 12345 54321)) it ran out of memory, with a basic tail-recursion optimization, it took about 10 seconds. (cdr (cons 123456 654321)) is about a half hour. So my code is an optimization, but really just the nature of that big of numbers is they are very inefficient to do a lot of math on, and even more so the bigger they get. You would never do something this weird in production code.

Tail optimization for benchmarking

(define (repeat-divide x y)
  (let loop ((acc 0) (x x))
    (if (> (remainder x y) 0)
        acc
        (loop (+ 1 acc) (/ x y)))))