SICP exercice 1.16, où est mon bug, parce que cela me semble juste

Question

Je viens de commencer à travailler sur ce livre pour m'amuser; J'aurais aimé que ce soit des devoirs, mais je n'aurais jamais pu me permettre d'aller au MIT, et il y a des tas de gens plus intelligents que moi de toute façon. : P

rapide exp est censé trouver b^n, à savoir 4^2 = 16, 3^3 = 27

(define (fast-exp b n) 
    (define (fast-exp-iter n-prime a) 
    (cond ((= n-prime 1) a) 
      ((= (remainder n-prime 2) 1) (fast-exp-iter (- n-prime 1) (* a b))) 
      (else (fast-exp-iter (/ n-prime 2) (* a b b))))) 
    (fast-exp-iter n 1)) 

fast-exp 4 2; Expected 16, Actual 2 

Answer 1

Vous avez oublié d'appeler rapidement exp. Au lieu de cela, vous avez évalué trois atomes séparés. Pour évaluer réellement la rapid-exp de 4 à 2, vous devez écrire

(fast-exp 4 2) 

Answer 2

La solution que vous avez écrite ici est également incorrecte. par exemple. Découvrez (fast-exp 2 6). Attendu: 64, actuel: 32.

Answer 3

Votre solution calcule les mauvaises réponses. (Voir http://ideone.com/quT6A) En fait, comment en principe pouvez-vous écrire une exponentiation rapide récursive en queue en ne passant que deux nombres comme arguments? Je ne pense pas que ce soit possible, car au milieu du calcul, vous ne savez pas quel multiplicateur utiliser si vous rencontrez un exposant impair. Mais je peux donner un exemple de solution de travail qui est exactement ce qui est attendu par les auteurs SICP (processus itératif en utilisant « quantité invariante » (a * b^n), où est initialement 1)

(define (pow x y) 
    (define (powi acc x y) 
    (cond 
     ((= y 0) acc) 
     ((odd? y) (powi (* acc x) x (- y 1))) 
     (else (powi acc (* x x) (/ y 2))))) 
    (powi 1 x y))