Généralités
Ce projet a pour but d'écrire une famille simple de générateurs
automatiques de programmes vers
Scheme
et C
. L'exemple choisi est le calcul rapide de $x^n$
dans un monoïde générique / un ensemble muni d'une loi de
multiplication associative. C'est l'associativité qui est
intéressante ici, puisqu'elle assure que, lorsque l'on fait un
calcul dont la valeur finale est résultat d'un ensemble de
multiplications, ledit résultat ne dépend pas de l'ordre dans lequel
les multiplications sont faites. En pratique, cela signifie qu'il y
a plusieurs manières de calculer par exemple $x^{16}$ :
-
- $x^{16} = x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x$ , 15 multiplications
-
- $x^{16} = x^6*x^6*x^4$;
- $x^6 = x^4*x^2$;
- $x^4 = x^2*x^2$;
- $x^2 = x*x$, 5 multiplications
-
- $x^{16} = x^8*x^8$;
- $x^8 = x^4*x^4$;
- $x^4 = x^2*x^2$;
- $x^2 = x*x$, 4 multiplications
Scheme
permettant de calculer algorithmes efficaces
pour ces exponentiations, et générer le code associé.
Objectifs du projet
L'objet de base pour le projet est la chaîne
d'additions pour un entier $n$ : une liste d'entiers strictement
croissante commençant par $1$, telle que tout entier dans la liste
est la somme de deux entiers présents dans les
indices antérieurs, et telle que le dernier élément soit égal à
$n$. Par exemple, pour $n=87$ :
De manière équivalente, il s'agit de la suite d'exposants associée à
un calcul de $x^n$ par multiplications successives de termes
précédents, en n'utilisant qu'une seule
multiplication à chaque étape. Des trois exemples donnés en
introduction, seul le dernier peut effectivement être codé par une
chaîne d'additions. Noter que l'algorithme d'exponentiation binaire
classique fournit naturellement des chaînes d'addition pour tout
$n$.
- $(1,2,3,6,7,10,20,40,80,87)$
- $(1,2,4,5,10,20,21,42,43,86,87)$ (stratégie binaire)
-
Vérification
Vérifier qu'une liste d'exposants donnée est bien une chaîne d'additions pour un entier $n$, et écrire le code nécessaire permettant d'exécuter l'algorithme d'exponentiation associé permettant de calculer $x^n$. Calculer pour une chaîne d'additions donnée le nombre de registres nécessaires 1 au calcul, ainsi que la complexité de l'algorithme produit en temps et en espace. -
Génération de chaînes
Étant donné un entier $n$, écrire un algorithme capable de construire l'ensemble des chaînes d'addition de $n$. Plusieurs stratégies sont envisageables pour obtenir ces chaînes, et elles seront discutées en fonction de leur complexité. En particulier, pour de grandes valeurs de $n$ pour lesquelles l'énumération exhaustive serait difficile, construire une stratégie meilleure que la stratégie binaire (ou dichotomique). -
Production d'algorithmes en Scheme
Écrire le code permettant, en fonction d'un entier $n$ donné, de générer automatiquement une fonction d'exponentiation enScheme
qui soit complètement optimisée, c'est-à-dire qui ne refait aucun calcul autre que les multiplications nécessaires à l'exponentiation $x^n$ 2 :Noter que la multiplication(define (exp10 mult x) (let* ([x2 (mult x x)] [x3 (mult x2 x)] [x6 (mult x3 x3)] [x7 (mult x6 x)] [x10 (mult x7 x3)]) x10 ))
mult
est un paramètre de l'algorithme. -
Production d'algorithmes en C
Générer le même code pour un algorithme enC
, qui soit de complexité en espace minimale, c'est-à-dire qui utilise dans la pile le nombre minimal de variables nécessaire au fonctionnement de votre algorithme. Prendre en compte la possibilité de choisir de faire des multiplications in-place (le résultat est directement stocké dans la variable correspondant à un paramètre, comme le*=
enC
) ou out-of-place (le résultat est placé dans une nouvelle variable).
Critères d'évaluation
- Les codes produits doivent être testés, que ce soit pour leur validité, ou leur efficacité, voire leur généricité.
- Il devra être attaché de l'importance au fait d'évaluer les gains de complexité obtenus, comparativement à l'algorithme d'exponentiation binaire classique.
- Plusieurs stratégies pour l'exponentiation de grands nombres peuvent facilement être construites et comparées.
1. | ↩
22/03/2016 : Le nombre de registres nécessaire est le
nombre minimal d'emplacements mémoire (comptés comme des variables en
C ) nécessaires à la réalisation du calcul. On
pourra estimer ce nombre en supposant que le résultat de la
multiplication doit nécessairement être stocké dans un
registre différent des deux opérandes. Avec cette hypothèse,
les nombres de registres nécessaires pour les 3 premiers
exemples sont respectivement : 3, 3 et
3 2
(grâce à Mr Rollet). |
2. | ↩
05/04/2016 : la génération de code Scheme est
fortement invitée à être faite en Scheme ,
c'est-à-dire comme une liste de symboles que l'on pourra
passer à la fonction eval . Le fait de produire
du code avec des crochets [] n'est pas
important, ils sont de toutes façons interprétés comme des
parenthèses ()
par Racket .
;; Trick to use eval outside the toplevel (define-namespace-anchor anchor) (define ns (namespace-anchor->namespace anchor)) (define (eval-expr expr) (eval expr ns)) ((eval-expr '(lambda (mult x) (let* ([x2 (mult x x)] [x3 (mult x2 x)]) x3))) * 2) ;; -> 8 |