From SICPExercise 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?
SICP - exercise 2.5 - representing pairs of nonnegative integers using only numbers and arithmetic operations
performance;beginner;lisp;scheme;sicp
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)))))