SICP行使2.5セレクタは

Question

私はSICPを読んで、運動2.5やってるinconstantly動作します。私たちはペアを 我々は唯一の数字と算術演算を使用して非負 整数のペアを表すことができ

Exercise 2.5.表示を表している場合a製品番号2^a*3^bである整数として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

解決策の1つは、浮動小数点数を避けることです。

(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)) 

を私の知る限り、あなたのソリューションは、右のアイデアを使用しています

はp^kがnを分割することを最大の指数kは、見つかったmax-power-dividingを考えてみましょうしかし、浮動小数点計算は大きな数の場合には中断されます。