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


a00x

there exist some mistakes in chekkal's code, which leads to wrong results in some condition. For example, (cdr (cons 11 17) will get 16 as output. Below are my codes,

 (define (cons a b) (* (expt 2 a) (expt 3 b) ) ) 
 (define (logb b n) 
  (ceiling (/ (log n) (log b) ) 
  ) 
  ) 
 (define (car n) 
  (logb 2  
                   (gcd 
                    n 
                    (expt 2 (logb 2 n) ) 
                   ) 
  ) 
  ) 
 (define (cdr n) 
  (logb 3  
                   (gcd 
                    n 
                    (expt 3 (logb 3 n) ) 
                   ) 
  ) 
  ) 
                                 ;test 
                                 (define x (cons 11 17) ) 
                                 (car x) 
                                 (cdr x)