sicp-ex-2.5


  
 ;; ex 2.5, pairs of integers. 
  
 ;; Pair a, b can be stored as a single integer 2^a * 3^b, provided a 
 ;; and b are both non-negative integers.  The first part will be even, 
 ;; the last odd.  Getting rid of the even part will leave the odd, and 
 ;; vice versa. 
  
 ;; Helpers. 
  
 (define (exp base n) 
   (define (iter x result) 
     ;; invariant: base^x * result is constant. 
     (if (= 0 x) 
         result 
         (iter (- x 1) (* base result)))) 
   (iter n 1)) 
  
  
 (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)) 
  
  
 ;; cons, car, cdr 
 (define (my-cons a b) (* (exp 2 a) (exp 3 b))) 
 (define (my-car z) (count-0-remainder-divisions z 2)) 
 (define (my-cdr z) (count-0-remainder-divisions z 3)) 
  
  
 ;; Usage: 
 (define test (my-cons 11 17)) 
 (my-car test) 
 (my-cdr test) 
  
  
 ;; Another way to define count-0-remainder-divisions 
  
 (define (divides? a b) 
   (= 0 (remainder b a))) 
  
 (define (count-0-remainder-divisions n divisor) 
   (define (iter x divisions) 
     (if (divides? divisor x) 
         (iter (/ x divisor) (+ divisions 1)) 
         divisions)) 
   (iter n 0)) 
  

<< Previous exercise (2.4) | Index | Next exercise (2.6) >>


jz

I had originally tried using an invariant for count-0-remainder-divisions, but couldn't get it to work. Alas.



chekkal

 ;; Constructor 
 (define (cons a b) (* (expt 2 a) (expt 3 b))) 
 ;; Enables us to calculate the log of n in base b 
 (define (logb b n) (floor (/ (log n) (log b)))) 
 ;; Selectors 
 (define (car x) (logb 2 (/ x (gcd x (expt 3 (logb 3 x)))))) 
 (define (cdr x) (logb 3 (/ x (gcd x (expt 2(logb 2 x)))))) 

jsdalton

This is probably similar to chekkal's answer at the end of the day. One downside is it returns floats, but this could probably be remedied via a round procedure (not yet introduced in course).

 (define (cons a b) 
   (* (expt 2 a) (expt 3 b))) 
  
 ; once we factor out the 3s, then: 
 ; 2^a = z 
 ; log(2^a) = log(z) 
 ; a*log(2) = log(z) 
 ; a = log(z) / log (2) 
  
 (define (car z) 
   (define (divisble-by-3? a) 
     (= (remainder a 3) 0)) 
   (if (divisble-by-3? z) 
     (car (/ z 3)) 
     (/ (log z) (log 2)))) 
  
 ; once we factor out the 2s, then: 
 ; 3^b = z 
 ; log(3^b) = log(z) 
 ; b * log(3) = log(z) 
 ; b = log(z) / log(3) 
  
 (define (cdr z) 
   (define (even? a) 
     (= (remainder a 2) 0)) 
   (if (even? z) 
     (cdr (/ z 2)) 
     (/ (log z) (log 3))))