Godefroy de Compreignac

Blog de Skreo :: Webdev && High-Tech 

• Blog
• Twitter
• Facebook
• Contact

• Maths & Algorithmes

  Interpréteur de BrainFuck

  par Skreo, le 8 Juillet 2007 à 02:09

  Dans ma lutte perpétuelle contre le travail utile, je viens de gaspiller 2 heures à coder un interpréteur de BrainFuck en PHP.
  Pour ceux qui ne connaissent pas le BrainFuck : http://fr.wikipedia.org/wiki/Brainfuck
  Vous allez me dire, "Hey mais ça existe déjà t'es trop nul !", oué c'est vrai, mais celui-ci est beaucoup plus rapide que les autres car il compile le BrainFuck en PHP et exécute le PHP obtenu avec eval. Et pour les ptits emmerdeurs qui me diront que la fonction eval n'est pas sécuritaire, je leur répondrai que oui mais non parce que là on gère que des chaînes de caractères, celui qui arrive à me hacker ça je lui offre un pikachu en peluche.
  Je préviens, c'est totalement inutile, mais ça peut être intéressant (ça peut...).
  
  Voici la seule fonction de l'interpréteur :
  

  <?php
   
   function brainfuck($code, $input=''){
       $code = preg_replace('#[^\[\]\+\-\.,<>]#', '', $code); // On supprime tous les caractères non reconnus par le BF
       $code = str_replace(']', '}', $code);
       $code = str_replace('[', 'while($t[$p]!="\x00"){', $code);
       $code = preg_replace('#([\+]+)#e', '\'$t[$p] = chr(ord($t[$p])+\'.strlen("\\1").\');\'', $code);
       $code = preg_replace('#([\-]+)#e', '\'$t[$p] = chr(ord($t[$p])-\'.strlen("\\1").\');\'', $code);
       $code = preg_replace('#([>]+)#e', '\'$p += \'.strlen("\\1").\';\'', $code);
       $code = preg_replace('#([<]+)#e', '\'$p -= \'.strlen("\\1").\';\'', $code);
       $code = str_replace('.', '$o .= $t[$p];', $code);
       $code = str_replace(',', '$t[$p] = $i[$pi++];', $code);
       $code = '$p = 0;'.                                             // Pointeur
               '$t = str_pad(\'\', 30000, chr(0));'.                // Tableau d'octets
               '$i = \''.str_replace('\'', '\\\'', $input).'\';'.    // Input
               '$pi = 0;'.                                            // Pointeur de l'input
               '$o = \'\';'.                                        // Output
               $code.
               'return $o;';
      
       $o = @eval($code);
       return $o ? $o : '';
   }
   ?>

  [code=php]
  <?php
  
  function brainfuck($code, $input=''){
      $code = preg_replace('#[^\[\]\+\-\.,<>]#', '', $code); // On supprime tous les caractères non reconnus par le BF
      $code = str_replace(']', '}', $code);
      $code = str_replace('[', 'while($t[$p]!="\x00"){', $code);
      $code = preg_replace('#([\+]+)#e', '\'$t[$p] = chr(ord($t[$p])+\'.strlen("\\1").\');\'', $code);
      $code = preg_replace('#([\-]+)#e', '\'$t[$p] = chr(ord($t[$p])-\'.strlen("\\1").\');\'', $code);
      $code = preg_replace('#([>]+)#e', '\'$p += \'.strlen("\\1").\';\'', $code);
      $code = preg_replace('#([<]+)#e', '\'$p -= \'.strlen("\\1").\';\'', $code);
      $code = str_replace('.', '$o .= $t[$p];', $code);
      $code = str_replace(',', '$t[$p] = $i[$pi++];', $code);
      $code = '$p = 0;'.                                             // Pointeur
              '$t = str_pad(\'\', 30000, chr(0));'.                // Tableau d'octets
              '$i = \''.str_replace('\'', '\\\'', $input).'\';'.    // Input
              '$pi = 0;'.                                            // Pointeur de l'input
              '$o = \'\';'.                                        // Output
              $code.
              'return $o;';
     
      $o = @eval($code);
      return $o ? $o : '';
  }
  ?>
  [/code]

  
  
  Et voici un exemple d'utilisation :
  

  <?php
   echo brainfuck('-[>+>++>++<<<-----]+++[>++++++<-]>.>+++++.+.>-----.<<---.>.+++.--------.');
   ?>

  [code=php]
  <?php
  echo brainfuck('-[>+>++>++<<<-----]+++[>++++++<-]>.>+++++.+.>-----.<<---.>.+++.--------.');
  ?>
  [/code]

  
  
  Dîtes-moi le résultat que ça vous donne :p (Pas toi divarvel !)
  Vous pouvez aussi tester la fonction avec des codes en BF que vous trouverez sur internet, à priori tout marche ;-)
  Si vous avez trop la flemme de recopier ce code dans votre éditeur (bande de fainéants !), voici un fichier php avec le code de la fonction et des exemples :
  http://data0.eklablog.com/skreo/perso/perso/brainfuck.php.txt
  

  
  
  4 commentaires

  ---

  Calcul de la racine carrée

  par Skreo, le 11 Mars 2006 à 00:44

  Je me posais depuis un certain temps la question toute bête mais interessante : comment calculer efficacement la racine carrée d'un nombre ?
  Je parts de x² = a
  Il y a quelques mois j'avais fait un petit programme un peu brutal et très lent sur ma TI-89 qui essayait plein de possibilités pour trouver x en vérifiant à chaque fois en comparant x² et a, jusqu'à obtenir un écart maximal prédéfini. Mais c'était pas du tout satisfaisant...
  J'ai alors cherché un peu sur internet, et j'ai trouvé plusieurs méthodes, mais la plupart étaient faites pour être utilisées à l'écrit, et elles étaient donc inexploitable dans un programme. Et j'ai trouvé la méthode d'Héron d'Alexandrie (1^er siècle après J-C) qui consiste en fait à créer une fonction dont le minimum sur R⁺ est en x = √a et y = √a. On cherche donc à atteindre le minimum de cette fonction pour avoir la valeur la plus approchée possible de √a
  A partir de l'équation x² = a, on obtient :
  2x² = x² + a
  2x = x + a/x
  x = (x + a/x)/2
  
  Ce qui donne une fonction f(x) = (x + a/x)/2
  A gauche, on voit la fonction f(x) = (x + 9/x)/2 pour trouver la racine carré de 9
  On voit bien que le minimum de f(x) sur R⁺ est en 3, qui est bien ce que l'on cherche ^^
  Mais comment trouver ce minimum ? En calculant la dérivée f '(x) de f(x) et en cherchant la solution de f '(x) = 0 (la dérivée étant égale au coefficient directeur de la tangente en un point, elle est égale à 0 lorsque la tangente est horizontale, et donc lorsque f(x) atteint son minimum)
  Mais non ! car si on fait ça, le résultat est.... √a ! On ne va tout de même pas tourner en rond ^^
  Non en fait cette fonction permet à partir de n'importe quel nombre de départ d'obtenir un nombre plus proche de √a que ce nombre de départ. Donc en répétant le calcul 3 ou 4 fois on obtient déjà une très bonne approximation.

  Prenons par exemple a = 671, et la racine carré de la puissance de 10 de ce nombre comme nombre de départ (facile à mettre en oeuvre dans un programme).
  On a dans ce cas comme nombre de départ : x = √100 = 10
  f(10) = (10 + 671 / 10) / 2 = 39,05
  f(39,05) = (39,05 + 671 / 39,05) / 2 = 28,1025641025
  f(28,1025641025) = (28,1025641025 + 671 / 28,1025641025) / 2 = 25,9896944600
  f(25,9896944600) = (25,9896944600 + 671 / 25,9896944600) / 2 = 25,9038100697
  f(25,9038100697) = (25,9038100697 + 671 / 25,9038100697) / 2 = 25,9036676943
  f(25,9036676943) = (25,9036676943 + 671 / 25,9036676943) / 2 = 25,9036676940
  
  La valeur réelle de la racine carré de 671 donnée par un ordinateur est 25,9036676940
  Au bout de 3 calculs, on obtient déjà un résultat convenable : 25,98
  Et au bout de 6 calculs, on trouve la racine carré de 671 avec une précision de 10 chiffres après la virgule !
  Evidemment, plus le nombre de départ est proche de la racine carré, et le nombre dont on veut trouver la racine carré est petit, moins il y a de calculs à faire ^^

  
  
  32 commentaires

  
  
  
  Suivre le flux RSS des articles de cette rubrique
  Suivre le flux RSS des commentaires de cette rubrique
  

  Haut de page