Equipe algorithmique du LabInfo IGM UMR CNRS

126 pages

Français

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Equipe algorithmique du LabInfo IGM UMR CNRS

pefav

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

126 pages

Français

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

A propos
Informations
Extrait

Description

Equipe algorithmique du LabInfo IGM, UMR CNRS 8049 5 fevrier 2009

equipe algorithmique du labinfo igm

controle dans les reseaux ip

reseaux

maıtres de conferences

ouvrage

reseaux sans fils emergents

Sujets

mathématique

Informations

Publié par	pefav
Publié le	01 février 2009
Nombre de lectures	44
Langue	Français

Extrait

B. Parisse Institut Fourier UMR 5582 du CNRS Université de Grenoble I

Algorithmes de calcul formel

Le résultant

Exercices sur types, calcul exact et approché, algorithmes de bases

Quelques algorithmes d'arithmétique de base. 2.1 Pour en savoir plus.. . . . . . . . . . . . . . . . . . . . . . . . .

14 15

4 4 4 5 6 7 8 9 10 10 11

Calculer sur ordinateur 1.1 Problèmes spéciﬁques au calcul formel. . . . . . . . . . . . . . . 1.1.1 Calcul exact et approché, types, évaluation.. . . . . . . . 1.1.2 Forme normale et reconnaissance du 0.. . . . . . . . . . 1.1.3 Valeur générique des variables et hypothèses. . . . . . . 1.2 Structures de données. . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Calculatrices formelles HP. . . . . . . . . . . . . . . . . 1.2.2 Calculatrices formelles TI. . . . . . . . . . . . . . . . . 1.2.3 Maple, MuPAD, Mathematica, .... . . . . . . . . . . . . 1.2.4 Giac/xcas. . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Algorithmes et complexité.. . . . . . . . . . . . . . . . . . . . .

Le PGCD 4.1 Le sous-résultant.. . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Le pgcd en une variable. . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Le pgcd heuristique.. . . . . . . . . . . . . . . . . . . . 4.2.2 Le pgcd modulaire. . . . . . . . . . . . . . . . . . . . . 4.3 Le pgcd à plusieurs variables.. . . . . . . . . . . . . . . . . . . . 4.3.1 Le pgcd heuristique.. . . . . . . . . . . . . . . . . . . . 4.3.2 Le pgcd modulaire multivariables.. . . . . . . . . . . . . 4.3.3 EZGCD.. . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Quel algorithme choisir ?. . . . . . . . . . . . . . . . . . . . . . 4.5 Pour en savoir plus.. . . . . . . . . . . . . . . . . . . . . . . . .

18 18 21 21 24 28 28 28 31 35 35

Table des matières

Résumé Ce document décrit une partie des algorithmes de calcul formel utilisés pour le logiciel de calcul formel Giac/Xcas, cf. http://www-fourier.ujf-grenoble.fr/~parisse/giac_fr.html

Localisation des racines : les suites de Sturm.

Exercices (PGCD, résultant, ...) 7.1 Instructions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1.1 Entiers. . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1.2 Polynômes. . . . . . . . . . . . . . . . . . . . . . . . . 7.1.3 Calculs modulon. . . . . . . . . . . . . . . . . . . . . . 7.2 Exercices PGCD. . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Exercices (résultant). . . . . . . . . . . . . . . . . . . . . . . . 7.4 Exercice (Bézout modulaire). . . . . . . . . . . . . . . . . . . . 7.5 Exercice (Géométrie et résultants).. . . . . . . . . . . . . . . . . 7.6 Décalage entier entre racines.. . . . . . . . . . . . . . . . . . . .

Factorisation 8.1 Les facteurs multiples. . . . . . . . . . . . . 8.2 Factorisation en une variable. . . . . . . . . 8.2.1 Factorisation dansZ/pZ[X]. . . . . 8.2.2 Distinct degree factorization. . . . . 8.2.3 La méthode de Cantor-Zassenhaus. . 8.2.4 La méthode de Berlekamp. . . . . . 8.2.5 Remontée (Hensel). . . . . . . . . . 8.2.6 Combinaison de facteurs. . . . . . . 8.3 Factorisation à plusieurs variables. . . . . . 8.4 Preuve de l'identité de Bézout généralisée. . 8.5 Algorithme de Bézout généralisé. . . . . . . 8.6 Pour en savoir plus. . . . . . . . . . . . . . 8.7 Exercices (factorisation des polynômes). . .

. . . . . . . . . . . . .

Intégration 9.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . 9.2 Fonctions élémentaires. . . . . . . . . . . . . . . . . . 9.2.1 Extensions transcendantes, tour de variables. . . 9.2.2 Théorème de structure de Risch. . . . . . . . . 9.2.3 Théorème de Liouville. . . . . . . . . . . . . . 9.3 L'algorithme de Risch. . . . . . . . . . . . . . . . . . . 9.3.1 Intégration d'une fraction propre. . . . . . . . . 9.3.2 Réduction sans facteurs multiples. . . . . . . . 9.3.3 La partie logarithmique. . . . . . . . . . . . . . 9.3.4 La partie polynomiale (généralisée). . . . . . . 9.3.5 Extension logarithmique. . . . . . . . . . . . . 9.3.6 Extension exponentielle. . . . . . . . . . . . . 9.4 Quelques références. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . .

10 Intégration numérique 10.1 Les rectangles et les trapèzes. . . . . . . . . . . . . . . . . . . . 10.2 Ordre d'une méthode. . . . . . . . . . . . . . . . . . . . . . . . 10.3 Simpson. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.4 Newton-Cotes. . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.5 En résumé. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40 40 40 40 41 41 42 43 43 44

46 46 48 48 48 50 52 53 56 57 60 60 61 62

64 64 64 64 65 69 72 73 73 73 75 75 76 81

81 81 83 85 86 86

11 Algèbre linéaire 11.1 Résolution de systèmes, calcul de déterminant.. . . 11.1.1 La méthode du pivot de Gauß.. . . . . . . . 11.1.2 Le déterminant.. . . . . . . . . . . . . . . . 11.1.3 Systèmes linéaires. . . . . . . . . . . . . . 11.1.4 Bézout et lesp-adiques.. . . . . . . . . . . 11.1.5 Base du noyau. . . . . . . . . . . . . . . . 11.2 Réduction des endomorphismes. . . . . . . . . . . 11.2.1 Le polynôme minimal. . . . . . . . . . . . 11.2.2 Le polynôme caractéristique. . . . . . . . . 11.2.3 La méthode de Hessenberg. . . . . . . . . . 11.2.4 La méthode de Leverrier-Faddeev-Souriau. . 11.2.5 Les vecteurs propres simples.. . . . . . . . 11.2.6 La forme normale de Jordan. . . . . . . . . 11.2.7 Exemple 1. . . . . . . . . . . . . . . . . . 11.2.8 Exemple 2. . . . . . . . . . . . . . . . . . 11.2.9 Le polynôme minimal par Faddeev. . . . . 11.2.10 Formes normales rationnelles. . . . . . . . 11.2.11 Fonctions analytiques. . . . . . . . . . . . . 11.3 Quelques autres algorithmes utiles. . . . . . . . . . 11.3.1 Complexité asymptotique. . . . . . . . . . 11.3.2 Numériques. . . . . . . . . . . . . . . . . . 11.3.3 Décomposition de Schur. . . . . . . . . . . 11.3.4 Autres. . . . . . . . . . . . . . . . . . . . . 11.4 Quelques références. . . . . . . . . . . . . . . . . . 11.5 Exercices (algèbre linéaire). . . . . . . . . . . . . . 11.5.1 Instructions. . . . . . . . . . . . . . . . . . 11.5.2 Exercices. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . .

12 Interpolation 12.1 Interpolation de Lagrange. . . . . . . . . . . . . . . . . . . . . . 12.1.1 Existence et contrôle de l'erreur.. . . . . . . . . . . . . . 12.1.2 Différences divisées. . . . . . . . . . . . . . . . . . . . 12.2 Les splines. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13 La moyenne arithmético-géométrique. 13.1 Déﬁnition et convergence. . . . . . . . . . . . . . . . . . . . . . 13.2 Lien avec les intégrales elliptiques. . . . . . . . . . . . . . . . . 13.3 Application : calcul efﬁcace du logarithme.. . . . . . . . . . . . 13.4 La méthode de Newton.. . . . . . . . . . . . . . . . . . . . . . .

87 87 87 88 89 90 92 93 93 94 94 95 97 97 98 99 100 100 104 104 104 104 105 108 109 109 109 109

110 110 111 112 113

114 114 117 118 123

Calculer sur ordinateur

1.1 Problèmes spéciﬁques au calcul formel 1.1.1 Calcul exact et approché, types, évaluation.

Dans les langages de programmation traditionnel (C, Pascal,...), il existe déjà des types permettant une représentation exacte des données (type entier) ou une représentation approchée (type ﬂottant). Mais ces types de donnée de base occu-pent une taille ﬁxe en mémoire, le type entier est donc limité à un intervalle d'en-32 tiers (par exemple[0,2−1]pour un entier non signé sur une machine utilisant un processeur 32 bits) alors que le type ﬂottant peut représenter des nombres réels, mais est limité à une précision en nombre de digits de la mantisse et de l'exposant (par exemple 12 chiffres signiﬁcatifs et un exposant compris entre -499 et 499). En calcul formel, on souhaite pouvoir calculer rigoureusement d'une pa rt, et avec des paramètres dont la valeur n'est pas connue d'autre part ; il faut donc s'af-franchir de ces limites : – pour les entiers relatifs, on utilise des entiers deprécision arbitrairedont la taille en mémoire est dynamique (déterminée pendant l'exécution et non à la compilation), – pour les nombres complexes, on utilise un couple de nombres réels, – pour les rationnels, on utilise un couple d'entiers relatifs, √ – pour les irrationnels algébriques (par exemple2), on utilise un polynôme irréductible dont ils sont racines, – pour les paramètres (x, y, z, t...), on utilise un type structuré contenant un champ de type chaine de caractères pour représenter le nom du paramètre et un champ pour attribuer une valeur à (ou une hypothèse sur) ce paramètre, – pour les nombres transcendants (par exempleπ), on est obligé d'introduire un paramètre auquel on attribue une valeur numérique, qui ne sera utilisée qu'au moment où on veut une approximation numérique d'une expression contenant ce nombre transcendant, on parle de constante, – lorsqu'on a besoin d'une approximation numérique d'un nombre, on peut utiliser des conversions de ces types en un type ﬂottant. On peut aussi pour lutter contre les erreurs d'arrondi utiliser des nombres ﬂottants étendus do nt la précision est dynamique ou même des intervalles de ﬂottants étendus, – il faut aussi un nouveau type, appelé expression ou symbolique, permettant d'appliquer une fonction qu'on ne peut évaluer directement sur les objets précédents, par exemplesin(x). Il doit s'agir d'une opération de clôture, au sens où appliquer une fonction à un objet symbolique ne nécessite pas la création d'un nouveau type (en général on renvoie un objet symbolique). Enﬁn, il faut pouvoir évaluer un objet (en particulier symbolique) : par exemple évaluersin(x)lorsqu'on assigne une valeur àx. Dans cet exemple, on voit qu'il faut d'abord remplacerxpar sa valeur avant de lui appliquer la fonction sinus. C'est le mécanisme général de l'évaluation, mais il y a quelques exceptions où o n souhaite empêcher l'évaluation d'un ou plusieurs arguments d'une fonction a vant l'évaluation de la fonction. Par exemple si on veut calculer la valeur numérique d'une intégrale par des méthodes de quadrature, on ne souhaitera pas r echercher une primitive de la fonction à intégrer. Dans le jargon, on parle alors de “quoter” un argument (l'origine du terme vient probablement de la notation du langage '

Lisp). Certaines fonctions doivent toujours quoter leurs arguments (par exemple la fonction qui permet de purger le contenu d'un paramètre), on parle parf ois d'auto-quotation.

1.1.2

Forme normale et reconnaissance du 0.

Une fois déﬁni ces types de base représentant les nombres d'un système de calcul formel, il faut pouvoir comparer ces nombres, en particulier décider si deux représentations distinctes correspondent au même nombre ou, ce qui revient au même, par soustraction décider quand un nombre est nul. Par exemple4/2et 2 représentent le même nombre. Lorsqu'on dispose d'un algorithme permettant d e représenter un nombre d'une manière unique, on parle de forme normale. C 'est par exemple le cas pour les nombres rationnels, la forme normale usuelle est la fraction irréductible de dénominateur positif. C'est aussi le cas pour les fra ctions rationnelles de polynômes à coefﬁcients entiers représentées par une fraction ir-réductible, avec au dénominateur un coefﬁcient de plus haut degré positif. Mal-heureusement, il n'est pas toujours possible de trouver une forme normale pour diverses raisons théoriques ou pratiques : – on ne connaît pas toujours le statut de certaines constantes (par exemple la constante d'Euler), – il n'existe pas d'algorithmes permettant de déterminer s'il existe des rela-tions algébriques entre constantes, – il n'existe pas forcément une seule forme plus simple, par exemple : √ √ ( 2 + 1)x+ 1x+ 2−1 √=√ x+ 2 + 1 ( 2−1)x+ 1

Ce cas se présente fréquemment avec les extensions algébriques. – en pratique il peut être trop coûteux d'utiliser une forme normale, par exem-1000 x−1 ple le polynôme possède 1000 monômes x−1 En résumé, au mieux on a une forme normale, au pire on risque de ne pas recon-naître un zéro, entre les deux on peut ne pas avoir de forme normale mais être capable de reconnaître à coup sûr une expression nulle (par contre, si le système de calcul formel détermine qu'une expression est nulle, alors elle l'est). Il n'existe pas d'algorithme solution pour le problème de la reconnaissance du zéro pour une classe d'expressions "assez générale". Heureu sement, dans la plupart des cas pratiques on sait résoudre ce problème, en se ramenant le plus souvent au cas des polynômes et fractions rationnelles. Par exemple, pour simpli-ﬁer une expression trigonométrique, on remplace les fonctions trigonométriques sin(x),cos(x),tan(x)par leur expression en fonction det= tan(x/2), on est ainsi ramené à une fraction rationnelle entque l'on écrit sous forme normale. Les polynômes ont un rôle central dans tout système de calcul formel puisque sauf dans les cas les plus simples (fractions d'entiers par exemple), la simpliﬁca -tion d'expressions fait appel à un moment ou à un autre à des calculs de PGCD d e polynômes. Le PGCD de polynômes est un algorithme très sollicité auquel nous consacrerons une section. En effet, l'application brutale de l'algorithme d'Eu clide pose des problèmes d'efﬁcacité ce qui a obligé à inventer des méthodes plus ef ﬁ-caces. Anticipons rapidement sur un exemple qui montre l'un des problèmes ma-jeurs des algorithmes de calcul formel, l'explosion en taille (ici des coefﬁcien ts des

restes successifs). Voici donc les restes successifs lorsqu'on app lique l'algorithme 7 6 d'Euclide pour calculer le PGCD deP(x) = (x+ 1)−(x−1)avec sa dérivée (les deux polynômes sont premiers entre eux) :

6 5 7(x+ 1)−6(x−1) 162−390 1060−780 474−78 5 4 3 2 x+x+x+x+x+ 49 49 49 49 49 49 157780−507640 290864−101528 28028 4 3 2 x+x+x+x+ 729 2187 729 729 729 1 1400328−732888 1133352−732888 3 2 (x+x+x+ ) 49 2645 2645 3703 18515 1 2161816376832−555436846944 301917024864 2 (x+x+ ) 2187 4669921 4669921 4669921 1 469345063045455−47641670106615 (x+ ) 907235 129411872 129411872 5497465490623352995840 209648836272383412129 Le lecteur voulant tester d'autres exemples pourra utiliser le programme (cf. Xcas l'appendice) suivant :

pgcd(a):={ local b,r,res; b:=diff(a,x); res:=NULL; for (;b!=0;){ res:=res,b; r:=rem(a,b); a:=b; b:=r; } return(res); }

1.1.3

Valeur générique des variables et hypothèses

Lorsqu'on utilise un symbole sans lui affecter de valeurs en mathématiques on s'attend à une discussion en fonction du paramètre représenté par ce symbole . Ce qui nécessiterait de créer un arborescence de calculs (on retrouve ici les problèmes d'explosion évoqués dans la section précédente). La plupart des systè mes de calcul formel contournent la difﬁculté en supposant que le paramètre possède une valeur 2 générique (par exemple la solution de(t−1)x=t−1serax= 1/(t+ 1)) ou choisissent une branche pour les fonctions possédant un point de branchement 2 (par exemple pour résoudrex=ten fonction det). Certains systèmes deman-dent de manière interactive à l'utilisateur si la variable est par exemple positiv e ou différente de 1 mais cela s'oppose à un traitement automatique. On peut aussi an-ticiper ce type de décision en faisant des hypothèses sur une paramètre, la plupart des systèmes de calcul formel actuel proposent cette possibilité.

1.2

Structures de données

On a vu plus haut qu'on souhaitait manipuler des entiers de taille non ﬁxe, des réels de précision ﬁxe ou non, des fractions, des nombres complexes, des ex-tensions algébriques, des paramètres, des expressions symboliques. La plupart des systèmes proposent un type générique qui recouvre ces divers types de scalaire. On peut par exemple utiliser un type structuré comportant un champ type et la don-née ou un pointeur sur la donnée (avec dans ce cas un pointeur sur un compteur de 1 références de la donnée pour pouvoir la détruire dès qu'elle n'est plu s référencée ). En programmation orientée objet, on utiliserait plutôt un type abstrait dont dérivent ces différents scalaires et le polymorphisme. Il faut aussi un type pour les vecteurs, les matrices et les listes. Il faut pren-dre garde à la méthode utilisée par le système lorsqu'on modiﬁe un élément d'un vecteur, matrice ou liste : soit on effectue une copie de tout l'objet en modiﬁan t l'élément, soit on modiﬁe l'élément de l'objet original. La première méthode (par valeur) est plus aisée à comprendre pour un débutant mais la seconde méthode (par référence) est bien plus efﬁcace. On peut se poser la question de savoir s'il faut inclure ces types dans le ty pe générique ; en général la réponse est afﬁrmative, une des raisons étant que les in-terpréteurs qui permettront de lire des données dans un ﬁchier texte sont en général basé sur le couple de logiciels qui ne peut com-lex(flex)/yacc(bison) piler qu'à destination d'un seul type. Ceci permet également d'uniﬁer en un seul type symbolique les fonctions ayant un ou plusieurs arguments en voyant plusieurs arguments comme un vecteur d'arguments. Les fonctions sont le plus souvent elle-même incluses dans le type générique permettant ainsi à l'utilisateur de saisir de s commandes ou programmes fonctionnels (on peut utiliser une fonction comme ar-gument d'une commande). Pour des raisons d'efﬁcacité, les systèmes de calcul formel utilisent sou vent des représentations particulières pour les polynômes dont on a dit qu'ils jou aient un rôle central. Pour les polynômes à une variable, on peut utiliser la liste des coefﬁcients du polynôme, on parle alors de représentation dense. On peut aussi dé-cider de ne stocker que les coefﬁcients non nuls, on parle alors de représentation creuse (on stocke alors un couple formé par le coefﬁcient et le degré du monôme correspondant). Pour les polynômes à plusieurs variables, on peut les considérer comme des polynômes à une variable à coefﬁcients polynomiaux, on parle alors de représentation récursive. On peut aussi décider de ne pas briser la symétrie entre les variables (pas de variable principale), on parle alors de représentation distribuée, le plus souvent les représentation distribuées sont creuses car les représentations denses nécessitent très vite beaucoup de coefﬁcients. Les méthodes de représenta-tion creuses sont parfois aussi utilisées pour les matrices ayant beaucoup de coef-ﬁcients nuls. Voyons maintenant plus précisément sur quelques exemples de logiciels de cal-cul formel répandus quelles structures de données sont utilisées. Plusieurs éléments entrent en compte dans les choix faits :

1 Certains systèmes de calcul formel (calculatrices par exemple) utilisent d'ailleurs des méthodes spéciﬁques pour gérer le problème de la fragmentation de la mémoire, appelés “garbage collector”. Ce type de méthode est intégré dans des langages comme Lisp ou Java, en C/C++ on trouve des libraries pour cela, par exemple GC de Boehm, incluse dans la distribution de GCC.

– le(s) proﬁl(s) d'utilisation (enseignement, ingéniérie, calcul intensif, rec herche) – les ressources disponibles (mémoire, puissance du processeur...) – la facilité d'implémentation (choix du langage, outils disponibles en partic-ulier débuggueurs, ...) – l'histoire du système (un système conçu avec les outils disponibles aujour-d'hui est forcément différent d'un système conçu il y a 20 ans) Nous allons d'abord parler des calculatrices formelles HP et TI (le lecteur p ourra facilement les tester grâce aux émulateurs gratuits pour PC). Ce sont des systèmes plutôt destinés à l'enseignement, soumis à de fortes contraintes en termes de taille mémoire, et destinés à traiter des petits problèmes. Puis nous présenterons des sys-tèmes pour ordinateur où les ressources (par exemple mémoire) sont moins limitées ce qui permet d'utiliser des langages de programmation de plus haut niveau .

1.2.1

Calculatrices formelles HP

Les langages utilisés pour programmer ces calculateurs sont l'assembleur e t le RPL (Reverse Polish Lisp) adapté à l'écriture de code en mémoire morte très compact. Le type générique est implémenté avec un champ type appelé prologue (qui est en fait un pointeur sur la fonction chargée d'évaluer ce type d'objet) sui vi de la donnée elle-même (et non d'un pointeur sur la donnée, on économise ainsi la place mémoire du compteur de référence). Le type entier en précision arbitraire est codé par le nombre de digits (sur 5 2 quartets ) suivi du signe sur un quartet et de la représentation BCD (en base 10) de la valeur absolue de l'entier. Le choix de la représentation BCD a été fait p our optimiser les temps de conversion en chaîne de caractères pour l'afﬁchage. La mé-moire vive disponible est de 256K, c'est elle qui limite la taille des entiers et non le champ longueur de l'entier. Il n'y a pas de type spéciﬁque pour les rationn els (on utilise un objet symbolique normal). Les fonctions internes des HP49/50/40 utilisent le type programme pour représen-ter les entiers de Gauß (complexes dont la partie réelle et imaginaire est entière). Les nombres algébriques ne sont pas implémentés, sauf les racines carrées (représen-tée de manière interne par le type programme). Il y a un type spéciﬁque prévu pour les ﬂottants en précision arbitraire, mais l'implémentation des opérations sur ces types n'a pas été intégrée en ROM à ce jour. Les types listes, programmes et objet symbolique sont composés du prologue (champ type) suivi par la succession d'objets situés en mémoire vive ou de po in-teurs sur des objets situés en mémoire en lecture seule (ROM) et se terminent par un pointeur sur une adresse ﬁxe (appelée ). Ces types sont eux-mêmes des SEMI objets et peuvent donc être utilisés de manière récursive. La longueur des types listes, programmes, symboliques n'est stockée nulle part, c'est le délimiteur ﬁna l qui permet de la connaître, ce qui est parfois source d'inefﬁcacité. O n utilise de manière interne les listes pour représenter les polynômes denses (avec représenta-tion récursive pour les polynômes à plusieurs variables). 3 Les calculatrices HP4xG utilisent une pile , c'est-à-dire une liste de taille non

2 un quartet=un demi octet 3 Plus précisément deux piles, la pile de donnée et la pile gérant le ﬂux d'ex écution. Cette dernière n'est pas visible par l'utilisateur

ﬁxée d'objets. On place les objets sur la pile, l'exécution d'une fonction pren d ces arguments sur la pile et renvoie un ou plusieurs résultats sur la pile (ce qui est une souplesse du RPN comparé aux langages où on ne peut renvoyer qu'une valeur de retour). Il faut donc donner les arguments avant d'appeler la fonction correspondante. Par exemple pour calculera+b. C'est la syntaxeon tapera a b + dite polonaise inversée (RPN). Un avantage de cette syntaxe est que le codage d'un objet symbolique par cette syntaxe est évidente, il sufﬁt de stocker la lis te précédente . Les objets symboliques sont donc représenté par une suite {a b +} d'objets écrit en syntaxe polonaise inversée. L'évaluation d'un objet sy mbolique se fait dans l'ordre polonaise inversé : les arguments sont évalués puis les fonctions leur sont appliqués. Pour des raisons d'efﬁcacité, on représente souv ent les objets composites (listes, symboliques) par leurs composants placés sur la pile (appelé meta-objets). Une rigidité de la syntaxe polonaise est que les fonctions ont toujours un nom-4 bre ﬁxe d'arguments , par exemple l'addition a toujours 2 arguments, ainsia+ b+cest obtenu par(a+b) +cou para+ (b+c)c'est-à-dire respectivement ou ce qui brise parfois artiﬁciellement la symétrie de a b + c + a b c + + certaines opérations. En polonaise inversée, le système doit de plus jongler avec l'autoquote puisque les arguments sont évalués avant l'opérateur qui é ventuelle-ment demanderait à ne pas évaluer ses arguments. À noter l'existence d'un e com-mande permettant à l'utilisateur de quoter une sous-expression. QUOTE Les hypothèses sur des variables réelles sont regroupées dans une liste stockée dans la variable globale , on peut supposer qu'une variable est dans REALASSUME un intervalle. Il n'y a pas à ce jour de possibilité de supposer qu'une var iable est entière (ni à fortiori qu'une variable à une valeur modulo un entier ﬁxé), bie n qu'il ait été décidé de réserver la variable globale à cet effet. Il n'y INTEGERASSUME a pas de possibilité de faire des hypothèses ayant une portée locale.

1.2.2

Calculatrices formelles TI

Le langage utilisé pour programmer ces calculatrices est le langage C (on peut aussi écrire du code en assembleur pour ces calculatrices). On retrouve ici les dif-férents types de données regroupé en un type générique qui est un tableau d'octets (aussi appelé quantum). Le champ type est appelé tag dans la documentation TI. Contrairement à ce qui précède, ce champ type est placé en mémoire à la ﬁn de l'objet, ce qui est possible car la longueur d'un objet est toujours indiqu ée au début de l'objet. Ceci est fait aﬁn de faciliter l'évaluation (cf. infra). Les entiers en précision arbitraire sont codés par un tag parmi deux (pour dif-férencier le signe), un octet pour la longueur, puis la valeur absolue de l'entier (en base 256). Ils sont donc limités par le champ longueur à 255 octets, le plus 5255 grand entier représentable est(256−1). Il existe un tag spéciﬁque pour les rationnels, pour les constantes réelles et entières qui apparaissent par exemple en résolvant une équation. Il existe des tags utilisés de manière interne, par exemple pour les nombres complexes. Il n'y a pas de tag prévu pour les ﬂottants en pr écision

4 Sauf si on utilise comme dernier argument le nombre d'arguments de la f onction ou si on utilise (cf. infra) un tag de début de liste d'arguments 5 Toutefois une adaptation du logiciel utilisant comme quantum de base par exemple 32 bits 65535 porterait cette limite à65536−1

arbitraire. ni pour les nombres algébriques (racines carrées par exemple). Les listes sont codées par la succession de leurs éléments. En principe elles ne peuvent pas contenir des listes (sauf pour représenter une matrice). Quelques fonctions utilisent les listes pour représenter des polynômes denses à une variable, mais probablement pas pour représenter de manière récursive des polynômes à plusieurs variables (puisque le type liste n'est en principe pas récursif) . Comme les HP, les TI utilisent une pile (non visible par l'utilisateur) appelée expression stack aﬁn de traduire un expression mathématique sous forme d' un texte en un objet symbolique codé exactement comme ci-dessus en syntaxe polonaise. Toutefois, la présence du champ longueur permet d'évaluer un objet sy mbolique sans perdre en efﬁcacité en partant de l'opérateur ﬁnal et en redes cendant ensuite sur ces arguments, c'est la stratégie adoptée. C'est pour cela que le tag d'identiﬁca-tion se trouve à la ﬁn de l'objet. L'utilisation de cette méthode facilite grandement l'autoquotation (on peut toutefois regretter que le système n'ait pas prévu d 'instruc-tion permettant à l'utilisateur d'empêcher l'évaluation d'une sous-expression) . On ne peut pas faire d'hypothèse globale sur un paramètre par contre o n peut faire des hypothèses de type appartenance à un intervalle ayant une portée locale.

1.2.3

Maple, MuPAD, Mathematica, ...

Ces systèmes ont un noyau fermé, au sens où l'utilisateur n'a pas accès d u tout, ou en tout cas pas facilement, aux structures de données de base. Je ne dispose donc pas d'information sur les structures de données utilisées par le noyau (pour MuPAD, on pourrait sans doute en savoir plus en achetant de la documentation sur la programmation des modules dynamiques). L'interaction système-utilisateur se fait quasiment toujours en utilisant le lan-gage de programmation propre au système, langage interprété par le noyau du sys-tème (ce qui ralentit l'exécution). Ces langages utilisateurs sont essentielleme nt non typés : on travaille avec des variables du type générique sans pouvoir accéder aux types sous-jacents. On ne bénéﬁcie en général pas des vériﬁcations faites lors de la compilation avec un langage typé, de plus ces systèmes ne sont pas toujours fourni avec de bon outils de mise au point. Enﬁn ces langages ne sont pas standard-isés d'un système à l'autre et il est en général impossible d'utiliser ces sys tèmes comme des librairies depuis un langage de programmation traditionnel. Leur intérêt principal réside donc dans une utilisation interactive en proﬁtant de la librairie de fonctions accessibles.

1.2.4

Giac/xcas

Il s'agit du système de calcul formel que j'implémente actuellement sous forme d'une bibliothèque C++ (ce qui permettra aux programmes tiers d'utiliser beau -coup plus facilement du calcul formel qu'avec les systèmes précédents) . L'objectif est d'avoir un système facile à programmer directement en C++, proche du langage utilisateur, lui-même compatible avec Maple ou MuPAD, tout cela sans trop perdre en performances comparativement aux librairies spécialisées écrites en C/C++. Ce qui explique un choix de type générique ( ) non orienté objet, avec un champ gen type et soit une donnée immédiate (pour les nombres ﬂottants par exemple), soit un pointeur vers un objet du type correspondant au champ type pour les données