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

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.

(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?

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

• Very thorough answer, welcome to Code Review :) Commented Jan 2, 2016 at 22:08