Quel est le problème avec ma mise en œuvre itérative d'expmod?

Question

Le programme suivant est conçu pour calculer base^expo mod m.

(define (expmod base expo m) 
    (define (square n) 
    (* n n)) 
    (define (even? n) 
    (= (remainder n 2) 0)) 
    (define (expmod-iter base expo m result) 
    (cond ((= expo 0) result) 
      ((even? expo) 
      (expmod-iter base 
         (/ expo 2) 
         m 
         (remainder (square result) m))) 
      (else 
      (expmod-iter base 
         (- expo 1) 
         m 
         (remainder (* base result) m))))) 
    (expmod-iter base expo m 1)) 

En fait, je suis en train de convertir a tail-recursive program from SICP à son équivalent itératif. Voici le programme original:

(define (expmod base exp m) 
    (cond ((= exp 0) 1) 
     ((even? exp) 
     (remainder (square (expmod base (/ exp 2) m)) 
        m)) 
     (else 
     (remainder (* base (expmod base (- exp 1) m)) 
        m)))) 

Le résultat de (expmod 42 1000000007 1000000007) est 270001056, mais selon Fermat's Little Theorem, puisque 1000000007 est premier, le résultat devrait être 42.

Qu'est-ce que je fais mal?

Answer 1

Ceci est mon mise en œuvre d'un expmod itérative:

(define (expmod base exp mod) 
    (let loop ((base base) 
      (exp exp) 
      (result 1)) 
    (cond ((zero? exp) result) 
      ((odd? exp) (loop base (sub1 exp) (modulo (* result base) mod))) 
      (else (loop (modulo (sqr base) mod) (quotient exp 2) result))))) 

testé dans Racket avec l'entrée de votre échantillon. Vous devrez remplacer sub1 et sqr par des implémentations appropriées si vous n'utilisez pas Racket. Notez que, bien que vous ayez à mettre la base de la base pour un exposant pair, vous pouvez réellement moduler le résultat de cela, comme vous pouvez le voir dans mon code. Donc ça ne devient pas trop massif.