Exercise2-4 <---> Exercise2-6
Exercise 2.5.
Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair a and b as the integer that is the product 2a3b. Give the corresponding definitions of the procedures cons, car, and cdr.
Ru: Покажите, что можно представлять пары неотрицательных целых чисел, используя только числа и арифметические операции, если представлять пару a и b как произведение 2a3b . Дайте соответствующие определения процедур cons, car и cdr.
Scheme solution:
We need to use exponentiation and factorization here. For exponentiation we can take fast-expt procedure from section 1.2.4. For factorization (defining power of given number in prime factorizations of m) we'll use factorize procedure defined below:
(define (cons x y)
(* (fast-expt 2 x)
(fast-expt 3 y)))
(define (factorize m base)
(define (factorize-iter curr acc)
(if (= 0 (remainder curr base))
(factorize-iter (/ curr base) (+ acc 1))
acc))
(factorize-iter m 0))
(define (car z) (factorize z 2))
(define (cdr z) (factorize z 3))
Another, O(log n) version of factorize:
(define (factorize m first-base)
(define (iter m base count accum)
(if (and (= (remainder m base) 0) (not (= m 0)))
(iter (/ m base) (square base) (* 2 count) (+ accum count))
(if (= (remainder m first-base) 0)
(iter (/ m first-base) first-base 1 (+ accum 1))
accum)))
(iter m first-base 1 0))
Haskell solution:
cons x y = 2^x * 3^y
factorize m base = factorize_iter m 0
where
factorize_iter curr acc
| curr `mod` base == 0 = factorize_iter (curr `div` base) (acc+1)
| otherwise = acc
car z = factorize z 2
cdr z = factorize z 3
Exercise2-4 <---> Exercise2-6
Comments
| what is x or y is a negative number there will be an error | ||||
| Posted by NAT-PUBLIC at 2009-04-06 06:06:59 X | ||||
The exercise constrains the problem to nonnegative numbers. So the solution is correct. | ||||
| Posted by SriramDevadas at 2009-05-28 07:49:51 | ||||