<< 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))
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))
;; 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))))))
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))))
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)
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))
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)))))
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))
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))
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 further only need even? If the number is 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
Another implementation by iteratively finding the largest power divisor
; auxiliary procedures (define (inc x) (+ 1 x)) (define (iter-div n d i) (if (= 0 (remainder n d)) (iter-div (/ n d) d (inc i)) i)) ; constructors & selectors (define (cons-e a b) (* (expt 2 a) (expt 3 b))) (define (car-e z) (iter-div z 2 0)) (define (cdr-e z) (iter-div z 3 0)) ; test case (define z-e (cons-e 2 5)) (car-e z-e) (cdr-e z-e)
A clearer and simpler complete solution. though may be duplicated with some of above solutions.
(define (cons a b) (* (expt 2 a ) (expt 3 b))) (define (car z) (if (= (remainder z 2) 0) (1+ (car (/ z 2))) 0)) (define (cdr z) (if (= (remainder z 3) 0) (1+ (cdr (/ z 3))) 0))
I have a solution that's simple to understand. The idea is to repeatedly divide by 3 for the car or 2 for the cdr until the remainder is 0, which means the product doesn't have any of those factors anymore. Then take either the base 2 or base 3 logarithm to get the exponent of whatever is left over, which is the number we want. car and cdr have time complexity O(b) and O(a) respectively, and it's not obvious to me that you can do any better than that. As an added bonus, this solution is naturally tail-recursive so it also runs in constant space.
(define (logb base x) (/ (log x) (log base))) (define (cons x y) (* (expt 2 x) (expt 3 y))) (define (car z) (if (= (remainder z 3) 0) (car (/ z 3)) (logb 2 z))) (define (cdr z) (if (= (remainder z 2) 0) (cdr (/ z 2)) (logb 3 z)))
I had originally tried using an invariant for count-0-remainder-divisions, but couldn't get it to work. Alas.