Cours / Conferences C++

Liste de chaînes YouTube dédiées à C++

isPrime(n) avec une regex

Ce minuscule script Perl d'une seule instruction ( print str =~ regex ? no : yes ) indique par YES ou NO si le l'entier passé en argument sur la ligne de commande est un nombre premier :

#!/usr/bin/perl
#usage: isPrime.pl <entier>
print (('@' x $ARGV[0]) =~ /^.?$|^(..+?)\1+$/ ? "NO\n" : "YES\n");

Spirale d'Ulam

Le cœur du script est une expression régulière qui matche quand l'argument n'est pas un nombre premier. Cette expression régulière s'applique à une chaîne de caractères identiques et de longueur égale à la valeur de l'argument. 

La chaîne contenant autant de @ qu'indiqué par l'argument est construite avec  ('@' x $ARGV[0]).

Exemple: isPrime.pl 6  travaille sur la chaîne "@@@@@@"

La première partie de la regex ^.?$ détermine s'il y a 0 ou 1 caractère dans la chaîne, autrement dit si le nombre à tester est 0 ou 1. Si c'est le cas le nombre n'est pas premier (affiche NO).

La deuxième partie de la regex ^(..+?)\1+$ détermine s'il est possible de décomposer la chaîne en la répétition d'une sous chaîne d'au moins 2 caractères. Si c'est le cas c'est que la longueur de la chaîne (donc la valeur de l'argument) peut s’écrire L * N, (avec L>0 et N>1) et donc le nombre n'est pas premier (affiche NO).

• L est la longueur de (..+?)
  
• n est le valeur que représente le + dans \1+

Exemples :

• isPrime.pl 9
  La chaîne de 9 caractères "@@@@@@@@@" est décomposée en 3 répétitions de "@@@"
  ==> matche ==> 9 n'est pas un nombre premier.
  
  
• isPrime.pl 12
  La chaîne de 12 caractères "@@@@@@@@@@@@" est décomposée en 6 répétitions de "@@"
  ==> matche ==> 12 n'est pas un nombre premier.
  
  
• isPrime.pl 11
  La chaîne de 11 caractères "@@@@@@@@@@@" n'est pas décomposable en N répétitions d'une chaîne de longueur L
  ==> ne matche ==> 11 est un nombre premier.

La classique boucle de cherche les diviseurs d'un nombre est prise en charge par la recherche itérative d'une solution dans le moteur d'expressions régulières. Bien sur la méthode n'est ni efficace en place mémoire ni en temps de calcul, mais elle est originale.

Vous trouverez une liste des 50000 premiers nombres premiers ici.

Note: L'image utilisée pour illustrer ce post est la spirale d'Ulam qui représente la position des nombres premiers sur une spirale. Les lignes droites semblent indiquer une certaine organisation (un pattern) des nombres premiers...intriguant...

Histoire de TAoCP

Si vous faites partie de la génération de développeurs qui ont appris à programmer dans des livres, vous connaissez sûrement ces bouquins écrits pour surfer sur une mode, pour essayer de se faire un nom. Des livres impersonnels, avec de la forme mais pas de fond. PHP disparaît des radars et avec lui une charrette d’auteurs insipides.

A l’opposé de ces livres de circonstance je vous présente : « The Art of Computer Programming » (TAoCP) de Donald Knuth, Professeur à Standford. Un ouvrage rédigé par un seul auteur sur toute une vie, sur un seul sujet : l’Algorithmique. La conception de l’ouvrage n’a pas été linaire, loin de là, et comme tout projet il a subit d’énormes retards et changements de direction.

Notes : Vous connaissez l’histoire de Git ? Et bien c’est un peu la même chose qui s’est passé pendant la rédaction/édition de The Art of Computer Programming  (TAoCP). En 1973, à l’occasion de la seconde édition du volume 2,  Knuth était insatisfait des systèmes de composition de page de l’époque. Il décide de faire une pause (de 1974 à 1996 !) pour concevoir l’outil qui lui convient pour rédiger son ouvrage (Tout comme Linus Torval écrit Git pour gérer le code du kernel Linux). Le résultat est metafont et TeX qui sont toujours utilisés en 2025 au travers de LaTeX et TeX Live

Pour convaincre ceux qui hésiteraient à se lancer dans l’achat (et la lecture) de cette œuvre je ne ferais pas mieux que ce post "Dix bonnes raisons de lire ou relire The Art of Computer Programming".

Dans sa forme actuelle (déc 2024) TAoCP est constitué de 5 volumes + un fascicule :

Volume 1: Fundamental Algorithms (1968, 3éme Édition 1997)
Volume 2: Seminumerical Algorithms (1969, 3éme Édition 1997)
Volume 3: Sorting and Searching (1973, 2éme Édition 1998)
Volume 4A: Combinatorial Algorithms, Part 1 (2011)
Volume 4B: Combinatorial Algorithms, Part 2 (2023)
+
Fascicule 7, Constraint Satisfaction (2025)  pour un futur volume 4C ?...

Les Volume 4A et 4B ont d’abord été publié (dans le désordre) sous forme de fascicules:

• Fascicule 0, Introduction to Combinatorial Algorithms and Boolean Functions (2008)
  Fascicule 1, Bitwise Tricks & Techniques; Binary Decision Diagrams (2009)
  Fascicule 2, Generating All Tuples and Permutations (2005),
  Fascicule 3, Generating All Combinations and Partitions (2005)
  Fascicule 4, Generating All Trees; History of Combinatorial Generation (2006)
  Ces cinq premiers fascicules ont ensuite été regroupés et publiés sous le nom "Volume 4A - Combinatorial Algorithms Part 1"en 2011

• Fascicule 5, Mathematical Preliminaries Redux; Introduction to Backtracking; Dancing Links (2019)
  Fascicule 6, Satisfiability (2015)
  Ces deux fascicules ont ensuite été regroupés et publiés sous le nom "Volume 4B - Combinatorial Algorithms Part 2" en 2023.

En prévision :

Volume 5: Syntactic algorithm,
Volume 6: The Theory of context-free languages
Volume 7: Compiler techniques

Ce dernier volume sur les compilateurs est en fait la raison initiale de tout ce travail. En effet, en 1962 Knuth travaillait sur des compilateurs Algol et Fortran et avait entamé l’écriture d’un livre sur ce sujet, mais il avait jugé qu’il fallait d’abord introduire des concepts fondamentaux  … Introduction qui a donné les 5 volumes actuels !

Les exemples ne sont pas écrits en C, ni Pascal, ni C++, ni Java, ni Rust. Mais avec MIX pour les 3 premiers volumes puis avec MMIX. C'est le langage d’une machine virtuelle avec une architecture RISC (ben oui, en 1968 on savait déjà ce qu’était une VM) 

 

 

Le cordonnier, l’informaticien et l’Opinel

Logo Opinel

J’ai été élevé par mes grands-parents, à Albi, pendant les années 60. Mon grand-père, mineur, électricien et grand bricoleur devant l’éternel, avait toujours son Opinel dans la poche. Il faisait tout avec. Il coupait le pain, la viande, bricolait, curait sa pipe, vidait le poulet, taillait des bâtons pour faire des moulins à eau. La liste est sans fin.

Le dimanche nous allions au marché sur la place de l’imposante cathédrale St Cécile. A cette époque les centres commerciaux et leurs galeries commerciales, avec le cordonnier qui fait des clefs, n’existaient pas. Certains artisans faisaient encore du porte à porte comme le rémouleur ou le rempailleur mais la plupart avaient une échoppe face à la cathédrale et autour des halles. Un jour que nous portions des chaussures à réparer au cordonnier (à cette époque on ne jetait pas), avant d’entrer dans la boutique, mon grand-père me dit en montant le cordonnier juste derrière la vitre en train de travailler un morceau de cuir :

-    Regarde, avec le dos de la lame de son Opinel il marque le cuir qui lui permet de gagner son pain et avec l’autre côté il coupe le pain ainsi gagné.

Pour moi qui n’avais pas encore dix ans c’était magique : On pouvait vivre avec un seul outil ! Je comprenais mieux pourquoi l’Opinel dans la poche de mon grand-père était si précieux.

Étonnamment, j’ai passé ma vie avec un seul outil entre mes mains: l’ordinateur. Même si l’écart technologique entre l’Opinel et l’ordinateur est immense, ils ont en commun d’être d’un usage universel, et depuis une décennie les ordinateurs rentrent aussi dans une poche. Mais il y a deux différences abyssales entre ces deux outils qui résument bien des choses : 

• Mon grand-père (1901 - 1992) a dû avoir trois ou quatre Opinel dans sa vie.
  Moi, depuis 1977, j’ai changé d’ordinateur tous les trois ou quatre ans. 
• Je peux prendre l’avion avec mon Smartphone dans la poche mais pas avec mon Opinel.