Exercice SICP 1.16, où est mon bug, car il me semble juste

Question

Je viens de commencer à travailler sur ce livre pour le plaisir; J'aimerais que ce soit des devoirs, mais je ne pourrais jamais me permettre d'assister au MIT, et il y a des tonnes de gens plus intelligents que moi de toute façon. : p

fast-exp est censé trouver b ^ n, c'est-à-dire 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 fast-exp. Au lieu de cela, vous avez évalué trois atomes distincts. Pour évaluer réellement l’expansion rapide 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épart (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 vous pouvez en principe écrire une queue récursive Exponentiation rapide en ne passant que deux nombres comme arguments? Je ne pense pas que ce soit même 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 correspond exactement à ce qui est attendu par les auteurs de SICP (processus itératif utilisant "une quantité invariante" (a * b ^ n), où a 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))