SICP Упражнение 2.5 - селектор ведет себя непостоянно

Question

Я читаю SICP и делать упражнения 2.5:

Exercise 2.5. Показать, что мы можем представлять пары неотрицательных целых чисел используя только числа и арифметические операции, если мы представим пару a и b как целое число, являющееся продуктом 2^a*3^b. Дайте соответствующие определения процедур cons, car, и cdr.

Вот мое решение:

;;; Exercise 2.5 
;;; ============ 

(define (cons x y) 
    (* (expt 2 x) 
    (expt 3 y))) 

(define (car z) 
    ; n is a power of 2, which is greater than z 
    (let ((n (expt 2 (ceiling (/ (log z) (log 2)))))) 
    (/ (log (gcd z n)) (log 2)))) 

(define (cdr z) 
    ; n is a power of 3, which is greater than z 
    (let ((n (expt 3 (ceiling (/ (log z) (log 2)))))) 
    (/ (log (gcd z n)) (log 3)))) 

Мой код хорошо работает с относительно небольшими тестовыми:

(define x 12) 
(define y 13) 
(define z (cons x y)) 

(car z) 
;Value: 12. 
(cdr z) 
;Value: 12.999999999999998 

Однако он производит неправильные результаты, когда число растет больше:

(define x 12) 
(define y 14) 
(define z (cons x y)) 

(car z) 
;Value: 12. 
(cdr z) 
;Value: 2.8927892607143724 <-- Expected 14 

Я хочу знать, что не так с моя реализация. Что-то не так с алгоритмом? Идея заключается в том, что наибольший общий генератор z = 2^x * 3^y и n (мощность 2, которая больше z) составляет точно 2^x.

Если мой алгоритм верен, это непоследовательность вызвана ошибкой округления и/или переполнением?

Answer 1

Одним из решений является предотвращение чисел с плавающей запятой.

Рассмотрим max-power-dividing, которая находит максимальный показатель k таким образом, что p^k разделяющую n:

(define (max-power-dividing p n) 
    (if (zero? (remainder n p)) 
     (+ 1 (max-power-dividing p (/ n p))) 
     0)) 

Тогда мы можем написать:

(define (car z) (max-power-dividing 2 z)) 
(define (cdr z) (max-power-dividing 3 z)) 

Насколько я могу сказать, ваше решение использует правильную идею , но вычисление с плавающей запятой ломается для больших чисел.