Available nodes

 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
Les objectifs consistent à mettre en place un ensemble d'outils en 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$ :
  • $(1,2,3,6,7,10,20,40,80,87)$
  • $(1,2,4,5,10,20,21,42,43,86,87)$ (stratégie binaire)
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$.
  • 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 en Scheme 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  :
    (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
    ))
    
    Noter que la multiplication mult est un paramètre de l'algorithme.
  • Production d'algorithmes en C

    Générer le même code pour un algorithme en C, 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 *= en C) 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