<< 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)
The key problem of chekkal's code is that `(logb b n)` is not exact and will output 16.999999999999996 for `(logb 3 (expt 3 17))`. IMHO `round` is better as jsdalton says.
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)))
Here I give one summary of history comments and one needed proof.
jsdalton's comment is based on recursive calls which is similar to `count-0-remainder-divisions`. But it doesn't track the recursive depth. It instead uses one inexact `(/ (log z) (log 2))` which IMHO is unnecessary.
alexanderchr's comment is same as foni's, knucklehead's and mashomee's where both again are based on recursive calls. They are just recursive implementation of `count-0-remainder-divisions` instead of using the iterative method. So 2bdkid's comment is same as "Another way to define count-0-remainder-divisions" (also for adkipnis's).
Nico de Vreeze's comment can combine `(= 1 z)` and `else` although that is not readable. `num-cdr` will always follow the call path of `num-car` and then do `else` in the rest process. It is better to replace `(even? z)` by `(divide-by-3? z)` although this is a small optimization.
master's comment is same as jsdalton's.
it's not obvious to me that you can do any better than that
IMHO, chekkal's comment is the most efficient. a00x's is based on it and better. If we think those lib functions have O(1) time complexity (although they are not), then obviously they are the most efficient.
The exercise says
''Show that'' we can represent pairs of nonneg- ative integers using only numbers and arithmetic opera- tions if we represent the pair a and b as the integer that is the product 2a 3b .
Then we need to show the 1st quote in https://math.stackexchange.com/a/62937/1059606 (IMHO there is no need to read the full post but just read some parts until you understand the question post). Then we can use the fundamental theorem of arithmetic to prove that (IMHO we had better learn Discrete maths before learning SICP although SICP also needs some numerical analysis background).
I had originally tried using an invariant for count-0-remainder-divisions, but couldn't get it to work. Alas.