Encore une autre façon de faire

Plusieurs versions de la fonction puissance ont été montrées en cours. Il y avait la version linéaire:

;;; : nat * nat -> nat ;;; (n m) rend n^m (define (^ n m) (if (= m 0) 1 (* n (^ n (- m 1)))))

Puis, une version dichotomique:

;;; carre : int -> nat ;;; (carre n) rend le carré de n (define (carre n) (* n n)) ;;; : nat * nat -> nat ;;; (n m) rend n^m (define (^ n m) (if (= m 0) 1 (if (even? m) (carre (^ n (quotient m 2))) (* n (carre (^ n (quotient m 2)))))))

Cette dernière s'appuyait sur l'identité:

n2m = (nm)2, n2m+1 = n (nm)2

En voici encore une variante qui s'appuie sur les règles légèrement différentes (ces règles ne modifient pas le caractère dichotomique: il y a toujours autant de multiplications que dans la version précédente):

n2m = (n2)m, n2m+1 = n n2m

Ce qui donne en Scheme:

;;; Id: power.scm,v 1.1 2001/10/22 07:12:36 queinnec Exp (define (^ n m) (if (= m 0) 1 (if (even? m) (^ (carre n) (quotient m 2)) (* n (^ n (- m 1))) ) ) )

Enfin, si l'on supprime l'appel à carre en le remplaçant par son équivalent (* n n), si on transforme l'appel récursif à m-1 qui est pair en son équivalent, et que l'on factorise le calcul de (n2)m, on peut également écrire:

(define (^ n m) (if (= m 0) 1 (let ((r (^ (* n n) (quotient m 2)))) (if (even? m) r (* n r) ) ) ) )

En résumé, il y a plus d'une façon de faire!