SICP Exercice 2.5 - sélecteur se comporte inconstante

Question

Je lis SICP et faire de l'exercice 2.5:

Exercise 2.5. Montrer que nous pouvons représenter des paires de nombres entiers non négatifs en utilisant uniquement des nombres et des opérations arithmétiques si nous représentons la paire a et b en tant qu'entier représentant le produit 2^a*3^b. Donner les définitions correspondantes des procédures cons, car, et cdr.

Voici ma solution:

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

Mon code fonctionne bien avec des cas de test relativement faible:

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

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

Cependant, il produit des résultats incorrects lorsque le nombre grossit:

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

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

Je veux savoir quel est le problème avec ma mise en œuvre. Y a-t-il un problème avec l'algorithme? L'idée est que le plus grand constructeur commun de z = 2^x * 3^y et n (une puissance de 2 qui est supérieure à z) est exactement 2^x.

Si mon algorithme est correct, cette incohérence est-elle causée par une erreur d'arrondi et/ou un débordement?

Answer 1

Une solution consiste à éviter les nombres à virgule flottante.

Tenir compte max-power-dividing qui trouve l'exposant maximal k tel que p^k divise n:

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

Ensuite, nous pouvons écrire:

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

Pour autant que je peux dire, votre solution utilise la bonne idée , mais le calcul en virgule flottante se brise pour les grands nombres.