langage de programmation FRACTRAN
Publié : dim. mai 15, 2011 1:42 pm
Le langage de programmation FRACTRAN (http://fr.wikipedia.org/wiki/FRACTRAN) est intéressant pour un logiciel comme Xcas parce qu'il est basé sur des fractions, qui utilisées dans tout logiciel non basé sur du calcul formel, donnent lieu à des accumulations d'erreurs d'arrondi. Un programme en FRACTRAN est une liste de fractions, et pour faire plus court j'ai décidé de le placer dans l'interpréteur (comme ça il y a une seule donnée en entrée, un entier naturel non nul). Le programme de multiplication est ici:
Pour multiplier a par b, on entre a et b sous forme du produit de 2^a par 3^b (codage de Gödel d'un couple d'entiers) et la réponse est 5^(ab) qui permet de récupérer le produit par décomposition en facteurs premiers (décodage de Gödel). Bon ces notions d'arithmétique concernent plus la Terminale que la Seconde, avec les nouveaux programmes...
Pour voir comment le programme fonctionne, par exemple pour calculer 3*2 (en entrant donc 72), le débogueur est très utile (on entre debug(fractran(72)) dans la console d'Xcas). Encore plus sur les exemples "Fibonacci" et "Collatz" en bas de l'article de wikipedia, où le plus intéressant est la suite des nombres produits pendant l'exécution du programme, plutôt que la seule valeur finale.
D'ailleurs la modification du code ci-dessus qui, au lieu de la valeur finale de n, envoie la liste de ces valeurs, est laissée en exercice.
Code : Tout sélectionner
fractran(n):={
local l,m,stop;
l:=[455/33,11/13,1/11,3/7,11/2,1/3];
stop:=false;
repeter
m:=-1;
repeter
m++;
jusqu_a (type(n*l[m])=DOM_INT ou m=size(l)-1)
si type(n*l[m])=DOM_INT
alors
n*=l[m];
sinon
stop:=true;
fsi
jusqu_a stop;
retourne n;
}
Pour voir comment le programme fonctionne, par exemple pour calculer 3*2 (en entrant donc 72), le débogueur est très utile (on entre debug(fractran(72)) dans la console d'Xcas). Encore plus sur les exemples "Fibonacci" et "Collatz" en bas de l'article de wikipedia, où le plus intéressant est la suite des nombres produits pendant l'exécution du programme, plutôt que la seule valeur finale.
D'ailleurs la modification du code ci-dessus qui, au lieu de la valeur finale de n, envoie la liste de ces valeurs, est laissée en exercice.