langage de programmation FRACTRAN

Discussion sur l'enseignement de l'algorithmique avec Xcas au lycee
alain974
Messages : 104
Inscription : lun. mai 24, 2010 11:15 am

langage de programmation FRACTRAN

Message par alain974 » 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:

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 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.
Dernière modification par alain974 le dim. mai 15, 2011 3:57 pm, modifié 1 fois.

alb
Messages : 1320
Inscription : ven. août 28, 2009 3:34 pm

Re: langage de programmation FRACTRAN

Message par alb » dim. mai 15, 2011 2:38 pm

La deuxième fraction est 11/13, non ?
RQ: avec Xcas les rationnels sont simplifiés et je ne sais pas si on peut l'empêcher ?
getNum(3x/(x-1)) renvoie 3x
getNum(11/33) renvoie 1

alain974
Messages : 104
Inscription : lun. mai 24, 2010 11:15 am

Re: langage de programmation FRACTRAN

Message par alain974 » dim. mai 15, 2011 3:59 pm

alb a écrit :La deuxième fraction est 11/13, non ?
OUI! Merci beaucoup.

Du coup j'ai édité le post ci-dessus pour que ce soit correct. Dans un programme FRACTRAN toutes les fractions doivent être irréductibles.

Répondre