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

Question

我正在阅读 SICP 并做练习 2.5:

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 2^a*3^b. Give the corresponding definitions of the procedures cons, car, and 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 的最大公约数(大于 z 的 2 的幂) >) 正好是 2 ^ x。

如果我的算法是正确的，这种不一致是否是由舍入错误和/或溢出引起的？

Answer 1

一种解决方案是避免 float 。

考虑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))

据我所知，您的解决方案使用了正确的想法，但是浮点计算在处理大量数据时会中断。