sicp-ex-2.5



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


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

jz

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


atomik

The top example has a few more layers than are really necessary, so I flattened it out and added a printing interface to make testing easier.

 ;   `count-0-remainder-divisions` will iteratively 
 ;   divide `p` by `d` until `p` is no longer a multpile 
 ;   of `d`. It will count the number of divisions with 
 ;   `n` and return `n` when `(remainder p d)` is not 
 ;   equal to 0. 
  
 (define (count-0-remainder-divisions n p d) 
         (if (= (remainder p d) 0) 
                 (count-0-remainder-divisions (+ n 1) (/ p d) d) 
                 n)) 
  
 ;   Dr. Racket doesn't like it when I overwrite 
 ;   primitives so my functions will be named 
 ;   `pair` `head` and `tail` instead of `cons` 
 ;   `car` and `cdr`, respectively. 
  
 (define (pair a b) 
         (* (expt 2 a) (expt 3 b))) 
  
 (define (head pair) 
         (count-0-remainder-divisions 0 pair 2)) 
  
 (define (tail pair) 
         (count-0-remainder-divisions 0 pair 3)) 
  
  
 (define (print pair) 
         (newline) 
         (display "( ") 
         (display (head pair)) 
         (display " . ") 
         (display (tail pair)) 
         (display " )") 
         (newline)) 
  
  
 (print (pair 991 1023)) 


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 dahttp://community.schemewiki.org/?sicp-ex-2.5y. 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))http://community.schemewiki.org/?sicp-ex-2.5 
   (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)http://community.schemewiki.org/?sicp-ex-2.5 
  (logb 3  
                   (gcd 
                    n 
                    (expt 3 (logb 3 n) ) 
                   ) 
  ) 
  ) 
                                 ;test 
                                 (define x (cons 11 17) ) 
                                 (car x) 
                                 (cdr x) 


foni

Another implementation

  
 ;;;Helpers 
 ;;Computes b^n ref: SICP -section 1.2.4 
 ;; b^n  = 1 if n = 0 
 ;;      = (b^(n/2))^2 if n even 
 ;;      = b.b^(n-1)  o.w. 
 (define (expt b n) 
   (define (even? n) (= (remainder n 2) 0))http://community.schemewiki.org/?sicp-ex-2.5 
   (define (square x) (* x x)) 
   (cond ((= n 0) 1) 
        ((even? n) (square (expt b (/ n 2)))) 
        (else (* b (expt b (- n 1)))))) 
  
 ;;return p where n = (k^p).q such that k does not divide q 
 (define (pow k n) 
     (if (not (= 0 (remainder n k)))  0  (+ 1 (pow k (quotient n k))))) 
  
 ;;test pow 
 (pow 2 (* (expt 2 3) (expt 7 11))) 
 (pow 7 (* (expt 2 3) (expt 7 11))) 
 (pow 5 (* (expt 2 3) (expt 7 11))) 
  
 ;;;represent pairs of non-negative integers as 2^a.3^b 
 (define (cons a b)  (* (expt 2 a) (expt 3 b))) 
 (define (car p) (pow 2 p)) 
 (define (cdr p) (pow 3 p)) 
  
 ;;test the representation 
 (car (cons 12 34)) 
 (cdr (cons 12 34)) 
 (car (cons  3 0)) 
 (cdr (cons  3 0)) 
 (car (cons  0 3)) 
 (cdr (cons  0 3)) 
 (car (cons  0 0)) 
 (cdr (cons  0 0)) 
  


knucklehead

How about...

  
  
 (define (cons x y) 
   (* (expt 2 x) (expt 3 y))) 
  
 (define (car z)            
   (if (= (gcd z 2) 1)      
     0                      
     (+ 1 (car (/ z 2))))) 
  
 (define (cdr z)           
   (if (= (gcd z 3) 1)     
     0                     
     (+ 1 (cdr (/ z 3))))) 
  


alexanderchr

The last solution can be abstracted further:

  
  
 (define (largest-power-of a z) 
   (if (= (remainder z a) 0) 
     (+ 1 (largest-power-of a (/ z a))) 
     0)) 
  
 (define (car z) 
   (largest-power-of 2 z)) 
  
 (define (cdr z) 
   (largest-power-of 3 z)) 
  


2bdkid

I turned alexanderch's function into a linear-iterative proceduce.

  
  
 (define (largest-power-divisor b n) 
   (define (divides? a b) 
     (= (remainder b a) 0)) 
   (define (iter result z) 
     (if (divides? b z) 
         (iter (inc result) 
               (/ z b)) 
         result)) 
   (iter 0 n)) 
  
 (define (num-cons a b) 
   (* (expt 2 a) 
      (expt 3 b))) 
  
 (define (num-car z) 
   (largest-power-divisor 2 z)) 
  
 (define (num-cdr z) 
   (largest-power-divisor 3 z)) 
  


vreeze42

Using even?, / and cond.

  
 (define (power base exp) 
   (if (= exp 0) 
       1 
       (* base (power base (- exp 1))))) 
  
 (define (num-cons x y) 
   (* (power 2 x) (power 3 y))) 
  
 ;; and futher only need even? If the number if not even and not 1, it must be divisible by 3! 
  
 (define (num-car z) 
   (cond ((= 1 z) 0) 
         ((even? z) (+ 1 (num-car (/ z 2)))) 
         (else 0))) ;; only factors of 3 left. 
  
 (define (num-cdr z) 
   (cond ((= 1 z) 0) 
         ((even? z) (num-cdr (/ z 2))) ;; remove car-part. 
         (else (+ 1 (num-cdr (/ z 3)))))) ;; then divide by 3 until 1 left. 
  
 (define z (num-cons 10 20)) 
 (num-car z) ;; 10 
 (num-cdr z) ;; 20 
  
 (define zeroes (num-cons 0 0)) 
 (num-car zeroes) ;; 0 
 (num-cdr zeroes) ;; 0