Esercizio 1.16 SICP, dov'è il mio bug, perché mi sembra giusto

Question

Ho appena iniziato a lavorare su questo libro per divertimento; Vorrei che fossero compiti a casa, ma non potrei mai permettermi di frequentare il MIT, e ci sono comunque tonnellate di persone più intelligenti di me. : P

si suppone che fast-exp trovi b ^ n, ovvero 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

Hai dimenticato di chiamare fast-exp. Invece, hai valutato tre atomi separati. Per valutare effettivamente l'espansione rapida da 4 a 2, dovresti scrivere

(fast-exp 4 2)

Answer 2

Anche la soluzione che hai scritto qui non è corretta. per esempio. Scopri (fast-exp 2 6). Previsto: 64, effettivo: 32.

Answer 3

La tua soluzione sta calcolando risposte errate. (Vedi http://ideone.com/quT6A ) In effetti, come in linea di principio puoi scrivere un ricorsivo di coda esponenziazione veloce passando solo due numeri come argomenti? Non credo sia nemmeno possibile, perché nel mezzo del calcolo non sai quale moltiplicatore usare se incontri esponente dispari. Ma posso dare un esempio di soluzione funzionante che è esattamente quello che si aspettano gli autori della SICP (processo iterativo che usa "quantità invariante" (a * b ^ n), dove a è inizialmente 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))