algorithm - SICP练习2.5-选择器的行为不稳定

我正在阅读SICP并做练习2.5：
Exercise 2.5.证明我们可以表示非负的对
如果我们表示
对a和b作为整数，即积2^a*3^b。
给出程序的相应定义，
以及cons。
以下是我的解决方案：

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

我想知道我的实现有什么问题。算法有什么问题吗？其思想是car和cdr（2的幂大于z = 2 ^ x * 3 ^ y）的最大公设就是n。
如果我的算法正确，这种不一致是由舍入错误和/或溢出引起的吗？

最佳答案

一种解决方法是避免浮点数。
考虑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))

据我所知，您的解决方案使用了正确的思想，但是浮点计算会因大量数据而中断。

关于algorithm - SICP练习2.5-选择器的行为不稳定，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41699267/