2
\$\begingroup\$

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?

\$\endgroup\$
1
\$\begingroup\$

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)))))
\$\endgroup\$
  • \$\begingroup\$ Very thorough answer, welcome to Code Review :) \$\endgroup\$ – Alex L Jan 2 '16 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.