Commentaires sur une source : Mon interpréteur Fractran

pgl10 Messages postés 381 Date d'inscription samedi 18 décembre 2004 Statut Non membre Dernière intervention 25 avril 2024 11
6 mars 2014 à 11:11

Beaucoup de programmes Fractran dépassent facilement la limite des entiers sur huit octets, même de type uint64_t, ce qui oblige assez souvent à stopper les itérations prématurément. Pour y remédier on peut utiliser une bibliothèque de gestion d'entiers de grandes tailles. GMP est l'une des plus connue de type. Mais cela nécessite une modification assez importante du source. Heureusement, la variante de GMP due à Paul Herman permet de faire cette modification avec des changements très simples et très peu nombreux. Voici donc, pour comparaison, le source de mon interpréteur Fractran avec GMP en variante de Paul Herman. Les entiers utilisés sont de taille aussi grande que nécessaire.

/************************************************
*  Interpréteur Fractran version 2.5 par pgl10  *
*                                               *
*  Pour l'utiliser il faut faire :              *
*                                               *
*  fractran x0 fractions.txt [output.txt]       *
*                                               *
************************************************/
   
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <stdint.h>
#include "Integer.h"
   
void my_pause() {
    std::cout << std::endl;
    system("pause");    
}
   
void erreur(std::string message) {
    std::cout << std::endl << message << std::endl;
    my_pause();
}
   
int stringToInt(const std::string& s) {
    int x;
    std::istringstream buff(s.c_str());
    buff >> x;
    return x;
}
   
void fractions(std::string ligne, int* nf, int** num, int** den) {
    // On compte le nombre de fractions 
    *nf = 0;
    int ll = ligne.length();
    for(int i=0; i<ll; i++) {
        if(ligne.c_str()[i] == '/') *nf=*nf+1;
    }
    // On met en place la liste des nf fractions
    *num = new int[*nf];
    *den = new int[*nf];
    std::size_t begin, end = -1;
    for(int i=0; i<*nf; i++) {
        begin = ligne.find_first_of("0123456789", end + 1);
        end = ligne.find_first_not_of("0123456789", begin + 1);
        (*num)[i] = stringToInt(ligne.substr(begin, end - begin));
        begin = ligne.find_first_of("0123456789", end + 1);
        end = ligne.find_first_not_of("0123456789", begin + 1);
        (*den)[i] = stringToInt(ligne.substr(begin, end - begin));
    }
}
   
std::string facteurs(Integer x) {
    // Pour imprimer x0 ou xn en facteurs premiers
    // On calcule seulement les facteurs de 2 à 23 de x
    int expos[9], prems[9]={2,3,5,7,11,13,17,19,23};
    Integer xx;
    xx=x;
    for(int i=0; i<9; i++) {
        expos[i]=0;
        while(xx%prems[i]==0) {
            expos[i]++;
            xx/=prems[i];
        }
    }
    // On calcule la chaine de sortie
    std::string s ("");
    int t=0;
    for(int i=0; i<9; i++) t+=expos[i];
    if(t == 0) return s;
    std::stringstream ss;
    for(int i=0; i<9; i++) {
        if(expos[i] != 0) {
            ss << "(" << prems[i] << "^" << expos[i] << ")"; 
        }       
    }
    if(xx != 1) ss << "*" << xx;
    ss >> s;
    return " = " + s;
}
   
int fractran(char* fi_fracts, Integer x, std::ostream& out) {
    // Le programme Fractran est dans la première ligne du fichier fi_fracts
    std::string ligne;
    std::ifstream in_file(fi_fracts, std::ios::in); 
    if(in_file) std::getline(in_file, ligne);
    else {
        std::cout << "Erreur pour le fichier contenant les fractions" << std::endl;
        return 1;
    }
    // On affiche l'entête
    out << std::endl << "Programme Fractran avec les fractions de " << std::string(fi_fracts) 
        << " : " << std::endl << std::endl << ligne << std::endl << std::endl;
    // On affiche la valeur initiale
    out << "et la valeur initiale x0 : " << x << facteurs(x) << std::endl << std::endl;
    // On calcule les nf fractions num[i]/den[i] pour i = 0 à nf-1
    int nf;
    int *num, *den;
    fractions(ligne, &nf, &num, &den);
    // On itère en cherchant à chaque fois la première fraction qui convient.
    bool fini=false;
    int n = 0; 
    do {
        out << "n = " << n << "    x = " << x << std::endl;
        int i;
        for(i=0; i<nf; i++) {
            // Si la i-ième fraction fournit un x suivant entier.
            if((x*num[i])%den[i]==0) {
                x=x*num[i]/den[i]; 
                break;
            }
        }
        // Si aucune fraction fournit un x suivant entier : on a la valeur finale.
        if(i==nf) {
            out << std::endl << "Stop : la suite est finie !" << std::endl;
            out << std::endl << "Et la valeur finale xn : " << x << facteurs(x) << std::endl;
            fini=true;
        }
        n=n+1;
        // Si n est trop grand : on arrête arbitrairement à la 10000-ième itération.
        if(n==10000) {
            out << std::endl << "Stop : n est arbitrairement trop grand !" << std::endl;
            fini=true;
        }
    }while(!fini);
    delete [] num;
    delete [] den;
    return 0;
}
   
int main(int argc, char *argv[]) { 
    // Il faut 3 ou 4 arguments seulement dans l'appel 
    if(argc<3 || argc>4) {
        erreur("Il faut faire : fractran x0 fractions.txt [output.txt]");
        return 1;
    }
    //  On lit la valeur initiale x0
    Integer x0=0;
    x0=argv[1];
    if(x0 < 1) {
        erreur("Il faut que x0 soit un entier positif");
        return 1;
    }
    // On ouvre le fichier éventuel de sortie des résultats 
    // et on effectue le programme Fractran
    // contenu dans argv[2] avec la valeur initiale x0
    // Les résultats sont affichés dans le fichier demandé ou sur la console.
    if(argc==4) {
        std::ofstream out_file(argv[3]);
        fractran(argv[2], x0, out_file);
    }
    else fractran(argv[2], x0, std::cout);
    my_pause();
    return 0;
}

Cet exemple d'utilisation d'entiers de grandes tailles peut aussi servir à d'autres occasions.

cptpingu Messages postés 3837 Date d'inscription dimanche 12 décembre 2004 Statut Modérateur Dernière intervention 28 mars 2023 123
26 févr. 2014 à 15:34

Suite à la v2, je vais ré-écrire quelques conseils qui sont passés à la trappe suite au bug de la boîte de commentaire:

- La fonction "erreur" est mal conçue. J'entends pas là, qu'il ne faut pas quitter abruptement un programme si les conditions sont dites "normal". Je m'explique. Généralement si l'on veut créer une barrière de sécurité, et s'assurer qu'une condition soit absolument respectée, on peut se permettre de quitter le programme et de signaler le souci. Exemple concret: Je créer une classe MyVector. Dans celui-ci, j'implémente la méthode "T operator[](int i)" qui me donne l'élément à la position i. Or, si un utilisateur me donne une position hors borne, je peux quitter le programme en expliquant qu'un bug potentiel a été détecté. C'est d'ailleurs le rôle de la fonction spéciale "assert" qui est dans <cassert>. La fonction assert existe en debug, et disparaît complètement en release. C'est donc une barrière de sécurité "gratuite" qu'il faut abuser.
En revanche, dans le cas d'une "erreur" non pas du programmeur, mais de l'utilisateur (donc pas un bug), on signale l'erreur, mais on ne quitte pas le programme pour autant. Exemple concret: L'utilisateur a indiqué un nom de fichier qui n'existe pas. Ce n'est pas un bug, on le signale, et on peut au choix, lui reproposer de nous donner un nom de fichier ou lui proposer une autre action. Ici, la fonction assert (tout comme exit) n'a pas sa place.
La fonction erreur, ne doit donc pas faire de exit. D'une manière générale, un exit dans son code est indice qui doit mettre la puce à l'oreille. C'est généralement signe de mauvaise conception. Pour le faire proprement, erreur devrait se contenter de formater l'erreur, mais pas de prendre la responsabilité de tuer le programme.

- La portée des variables est une sécurité supplémentaire. Il faut toujours déclarer une variable au moment de son utilité, mais pas avant. C'est, je suppose, un reliquat du C de les pré-déclarer (dans les version C89 et inférieur, on ne peut que déclarer au début d'un bloc). Or, en C++ et à partir de C99, on préfère maximiser la sécurité en limitant au maximum la visibilité de celle-ci. Exemple concret:

Dans ce code, je prédéclare i et j. Ces deux variables existent en dehors de la boucle. J'ai volontairement ajouté une erreur d'inattention commune:

int i, j;
for (i = 0; i < 10; ++i)
  std::cout << i << std::endl;
for (j = 0; j < 20; ++i)
  std::cout << j << std::endl;

Le code précédent, contient quelque chose qui arrive souvent. On se trompe de variable ou on écrase ou réutilise une variable qui n'a plus lieu d'être. Il est important de bien les segmenter. L'autre avantage évident, est la réutilisation du même nom, qui n'est pas gênant puisque le contexte est différent. On pourrait donc écrire:

for (int i = 0; i < 10; ++i)
  std::cout << i << std::endl;
for (int j = 0; j < 20; ++j) // impossible de se tromper car i n'existe plus
  std::cout << j << std::endl;
// À partir d'ici j n'existe plus.

Voir même:

for (int i = 0; i < 10; ++i) // Ce i n'existe que dans la boucle.
  std::cout << i << std::endl;
for (int i = 0; i < 20; ++i) // Ce i n'est pas le même que le précédent.
  std::cout << j << std::endl;

- Il y a un cast inutile. En C++, lorsque l'on doit "caster", c'est souvent un signe de mauvaise conception (voir de problème). Ici, on peut aisément s'en passer en changeant le type de i, en le passant de "int" à "unsigned int". C'est d'ailleurs techniquement moins dangereux puisqu'on comparera bien deux types de nature identique. Caster le retour de ligne.length() ne corrige pas le problème, mais le masque ! (caster un "unsigned int" en "int" peut lui faire perdre des informations, ce qui revient alors au même que de comparer un "unsigned int" et un "int"). Dans le cas présent, le nombre étant petit, aucune différence ne se fera sentir.

- Il faut éviter de mettre une fonction dans la deuxième partie d'un "for", car cette fonction est potentiellement appelée à chaque tour de boucle. On préfèrera stocker le résultat de ligne.length() et s'en servir dans la boucle. Petite subtilité: la plupart du temps, on ne s'en souci pas, car le compilateur est très souvent capable d'optimiser cela tout seul. Rare sont les cas ou il ne le fait pas (mais il en existe). C'est une bonne habitude de sortir cela de la boucle, car comme cela, on ne se pose plus la question. C'est forcément juste, quelque soit le compilateur.

- D'un point de vue architecture de code, il est préférable de découper la lecture du fichier de fraction, du calcul de fractran.

pgl10 Messages postés 381 Date d'inscription samedi 18 décembre 2004 Statut Non membre Dernière intervention 25 avril 2024 11
24 févr. 2014 à 20:44

Bonjour CptPingu,
Un grand merci pour ces commentaires et quel dommage que les premiers commentaires soient perdus. Les commentaires résumés et le code proposé me plaisent beaucoup. Je pensais que mon programme utilisait déjà du bon C++ avec les recommandations déjà faites dans le passé et je vois qu'il y a encore bien des améliorations très intéressantes à utiliser. A noter seulement que l'affichage Windows a toujours son problème de l'ASCII OEM au lieu de l'ASCII ANSI. Donc l'instruction :
out << std::endl << "Stop : il y a trop d'itérations" << std::endl;
ne fonctionne bien que si out vaut out_file et fonctionne mal si out vaut std::out, il y a bien sûr des solutions pour en tenir compte mais c'est moins joli. A noter aussi que dans un premier temps j'avais écrit des "fractan" là où il faut écrire "fractran". Je recommande à ceux qui veulent utiliser ton code de rectifier cette faute. J'ai corrigé mon envoi à ce sujet. De toutes façons, Fractran est un amusement mathématique qui n'a qu'un intérêt théorique et qui n'a aucune efficacité pratique, c'est même le contraire ! Et si on veut jouer un peu plus il faut utiliser de grands entiers au lieu des entiers sur 8 octets. La variante de GMP développée par Paul Herman est un assez bon outil pratique pour faire cela. Mais une simple version basique est suffisante pour faire quelques essais de ce langage de programmation très étonnant.
Tous mes remerciements.

cptpingu Messages postés 3837 Date d'inscription dimanche 12 décembre 2004 Statut Modérateur Dernière intervention 28 mars 2023 123
24 févr. 2014 à 19:04

Pour info:
http://codes-sources.commentcamarche.net/forum/affich-10021313-bug-ecriture-de-commentaire-sur-une-source

cptpingu Messages postés 3837 Date d'inscription dimanche 12 décembre 2004 Statut Modérateur Dernière intervention 28 mars 2023 123
Modifié par cptpingu le 24/02/2014 à 18:49

Je t'avais écrit un long commentaire, mais la boîte de commentaire m'a tronqué celui-ci et j'ai tout perdu !!!
Je n'ai pas le courage de tout réécrire... (60 lignes de commentaires en plus du code ci-joint).

En bref:
- Préfère un std::vector à un tableau en C. (On économise le calcul de nf).
- Un std::fstream se ferme tout seul, pas besoin de .close()
- Le flux de sortie standard et le flux de fichier hérite tous deux d'un flux abstrait std::ostream. Pas de besoin de if, il suffit juste d'initialiser correctement celui-ci.
- Le substr est très inefficace (tu le refais à chaque tour). Il est préférable d'utiliser find_first_of + son deuxème argument qui dit à partir d'où chercher. On ne fait alors le substr que sur la donné à récupérer.
- Plutôt que de faire deux tableaux, j'en ai fait un seul, contenant le couple num/den. Moins de risque de décalage.
- __int64 n'est pas portable. Préfère int64_t de <stdint.h> (Peut être même uint64_t ?)
- Au lieu de "pause()", j'ai appelé la fonction my_pause(), car pause() existe déjà (sous Unix).

Je te propose la réécriture suivante (je te laisse étudier le code, toutes mes excuses, mais je n'ai vraiment pas le courage de réécrire toutes mes remarques):


#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <sstream>
#include <stdint.h>

namespace
{
  struct NumDen
  {
    NumDen(int64_t num, int64_t den)
      : num_(num), den_(den)
    {
    }
    void print(std::ostream& out) const
    {
      out << num_ << "/" << den_;
    }
    int64_t num_;
    int64_t den_;
  };
  typedef std::vector<NumDen> list_type;
  typedef list_type::const_iterator const_iter;
  typedef list_type::iterator iter;

  int64_t stringToInt(const std::string& s)
  {
    int64_t x = 0;
    std::istringstream buff(s.c_str());
    buff >> x;
    return x;
  }

  void my_pause()
  {
    std::cout << std::endl;
    //system("pause");
  }

  void erreur(std::string message)
  {
    std::cout << std::endl << message << std::endl;
    my_pause();
  }

  void print(std::ostream& out, const list_type& list)
  {
    bool first = true;
    const_iter end = list.end();
    for (const_iter it = list.begin(); it != end; ++it)
    {
      if (first)
        first = false;
      else
        out << " ";
      it->print(out);
    }
  }

  bool parse(const std::string& filename, list_type& list, std::ostream& error_msg)
  {
    std::ifstream file(filename.c_str());
    if (!file)
    {
      error_msg << "file not found: " << filename << std::endl;
      return false;
    }

    std::string line;
    std::getline(file, line);

    std::size_t begin = 0;
    while (begin != std::string::npos)
    {
      begin = line.find_first_of("0123456789", begin);
      if (begin == std::string::npos)
        break;
      std::size_t end = line.find_first_not_of("0123456789", begin + 1);
      int64_t num = stringToInt(line.substr(begin, end - begin));

      if (line[end] != '/')
      {
        error_msg << "Parse error at character " << begin
                  << ": expected \"/\" but found \"" << line[end] << "\"" << std::endl;
        return false;
      }
      begin = line.find_first_of("0123456789", end + 1);
      end = line.find_first_not_of("0123456789", begin + 1);
      int64_t den = stringToInt(line.substr(begin, end - begin));
      if (end != std::string::npos && line[end] != ' ')
      {
        error_msg << "Parse error at character " << begin
                  << ": expected \" \" but found \"" << line[end] << "\"" << std::endl;
        return false;
      }

      list.push_back(NumDen(num, den));
      begin = end;
    }

    return true;
  }

  void computeFractan(const list_type& list, int64_t x0, std::ostream& out)
  {
    if (!out)
      return;

    int64_t max = 1;
    int64_t n = 1;
    for (int i = 1; i < 63; ++i)
    {
      n *= 2;
      max += n;
    }

    out << std::endl << "Programme Fractran avec les fractions suivantes : " << std::endl;
    print(out, list);
    out << std::endl << std::endl
        << "et la valeur initiale : " << x0 << std::endl << std::endl;

    bool stop = false;
    const_iter end = list.end();
    n = 0;
    do
    {
      out << "n = " << n << "    x = " << x0 << std::endl;
      const_iter it = list.begin();
      for (; it != end; ++it)
      {
        if (x0 > (max / it->num_))
        {
          out << std::endl << "Stop : x est trop grand !" << std::endl;
          stop = true;
          break;
        }
        // Si la i-ième fraction fournit un x suivant entier
        if ((x0 * it->num_) % it->den_ == 0)
        {
          x0 = x0 * it->num_ / it->den_;
          break;
        }
      }
      // Si aucune fraction fournit un x suivant entier
      if (it == end)
      {
        out << std::endl << "Stop : la suite est finie !" << std::endl;
        stop = true;
      }
      ++n;
      // Si n est trop grand, on arrête
      if (n >= 10000)
      {
        out << std::endl << "Stop : il y a trop d'itérations" << std::endl;
        stop = true;
      }
    } while (!stop);
  }
} // namespace

int main(int argc, char *argv[])
{
  list_type list;

  if (argc < 3 || argc > 4)
  {
    erreur("Il faut faire : " + std::string(argv[0]) + " x0 fractions.txt [output.txt]");
    return 1;
  }

  int64_t x0 = stringToInt(argv[1]);
  if (!parse(argv[2], list, std::cout))
    return 1;

  if (argc == 4)
  {
    std::ofstream out_file(argv[3]);
    computeFractan(list, x0, out_file);
  }
  else
    computeFractan(list, x0, std::cout);

  my_pause();
  return 0;
}

Mon interpréteur Fractran

Votre réponse

Discussions similaires