Mathématice, intégration des Tice dans l'enseignement des mathématiques  
Sommaire > N°29 - Mars 2012 > Bachotage arithmétique avec bash, levons la (...)

Bachotage arithmétique avec bash, levons la bâche !
franchissement de la ligne de commande...
Moteur de recherche
Mis en ligne le 4 mars 2012, par Alain Busser

Le langage bash ne connaît que deux types de données : Les chaînes de caractères et les entiers. Mais beaucoup de problèmes algorithmiques, et notamment d’arithmétique, concernent les entiers. On peut donc utiliser bash pour tester des algorithmes sur des entiers.

Pour programmer en bash (Bourne-Again shell), on n’a rien à installer, puisque ce logiciel est la fondation des systèmes d’exploitation basés sur UNIX, en particulier Linux. Ce langage de programmation n’est donc pas totalement multi-plateforme puisque les windowsiens en sont privés [1], mais les heureux possesseurs d’un UNIX ont déjà tout ce qu’il faut pour programmer en bash, il suffit pour cela qu’ils ouvrent une console et ça y est, ils programment en bash [2] ! Ceci dit, pour des questions de confort (et de coloration syntaxique), le logiciel Geany a été utilisé dans cet article.

D’où vient ce nom à bugger dehors ?

L’ancêtre de bash est le shell Unix de Stephen Bourne, ou Bourne shell (en abrégé sh comme shell, parce que c’est un peu la coque qui entoure le système d’exploitation, du moins sa partie visible).

Lorsque le projet GNU a repris son shell à lui, il l’a baptisé Bourne Again Shell pour faire un jeu de mots sur Borne again shell suggérant l’idée d’une renaissance. D’où le nom de bash.

Mais il existe d’autres logiciels reconnaissant les scripts ci-dessous, comme le Korn shell, Csh, Tcsh, Zsh ou le léger Ash shell, ash signifiant cendre... C’est pour cela qu’il est nécessaire de préciser au début de chacun des scripts ci-dessous le choix du shell qu’on a fait, en expliquant où est bash (ou autre) à la console. Ce qu’on fait en commençant le script par une des lignes suivantes :

#! /bin/bash
#! /bin/sh

On remarquera que dans cet article, Guillaume Connan fait de même avec Python 3, en commençant un de ses scripts par

#! python3

Ce n’est pas un hasard, puisque python3 est considéré comme une instruction de bash, comme le sont tous les logiciels installés, en particulier Perl, Python, grep, cat, awk, cat etc.

Pour programmer en bash avec Geany, on doit commencer par créer un document texte avec l’extension sh, puis le rendre exécutable. Sous Ubuntu on peut faire un clic droit sur le fichier, et sélectionner l’option autoriser l’exécution comme un programme :

Une fois que c’est fait, il suffit d’ouvrir le fichier avec Geany et pour tester chaque modification, on lance l’algorithme en cliquant sur l’icône ressemblant à un rouage [3] :

Voici quelques exemples de scripts en bash, d’intérêt essentiellement mathématique :

Présentation

Affectation, entrée, sortie

Affectation

L’affectation se note classiquement par un signe d’égalité :

a=3

Mais comme le type par défaut est la chaîne de caractères, tout appel à a va renvoyer la lettre a et non la variable a. Pour accéder au contenu d’une variable, on précède son nom du symbole dollar [4]. En plus, si on veut incrémenter un nombre entier a, le simple fait d’écrire

a=$a+1

ne marche pas, parce que dans ce cas a contiendra 3+1 et non 4 : Les opérations ne s’exécutent pas toutes seules ! Pour les forcer à s’exécuter, on les met elles-mêmes derrière le symbole dollar (avec des doubles parenthèses). Pour incrémenter a, chacune des lignes de code suivantes convient :

a=$(($a+1))
let "a=$a+1"
let "a+=1"
let "a++"

Dans la suite de cet article, l’usage de let avec un script entre guillemets sera préféré (question de goût essentiellement).

Les opérations sont notées comme en Python (langage) par les symboles suivants :

opération notation exemple
addition + 2+2=4
soustraction - 3-2=1
multiplication * 3*2=6
division euclidienne / 22/7=3
reste % 22%7=1
puissance ** 2**3=8
facteurs premiers factor 2012=2*2*503

Entrée de données

Pour entrer au clavier la valeur d’une variable x, on fait juste

read x

Sortie de données

Pour afficher le contenu d’une variable, on utilise echo (qui recopie le contenu de la variable dans la console, à moins qu’on effectue une redirection pour écrire dans un fichier) :

echo x

écrit "x" dans la console, alors que

echo $x

effectue la sortie désirée.

Voici, à titre d’exemple, un script qui permet de vérifier que la fonction $x \mapsto x^2-(x+1)(x-1)$ est constante :

Tests

Les tests s’écrivent entre crochets, et envoient un nombre entier (bash n’ayant pas de booléens), 0 si le test échoue, 1 s’il réussit. Les opérateurs booléens s’écrivent façon ligne de commande avec des tirets : -a (comme and) pour la conjonction, et -o (comme or) pour la disjonction. Les opérateurs de comparaison s’écrivent comme des abréviations anglaises, par exemple -lt (comme less than) pour inférieur, ou -eq (comme equal) pour l’égalité...

Un test s’écrit entre if et fi (if à l’envers) ; le mot else est utilisé pour gérer le cas où le test échoue.

Des exemples seront montrés dans les onglets suivants.

Boucles

à indice

L’instruction

seq 1 10

affiche la suite des entiers allant de 1 à 10, alors comme bash peut déléguer son travail (en envoyant des signaux par des pipes), on peut effectuer des opérations répétitives en écrivant la séquence entre apostrophes à l’envers (caratère Alt Gr+7) ; dans ce cas tout ce qui est entre do et done sera effectué. Par exemple, pour afficher les dix premiers carrés, on peut faire ainsi :

à condition de sortie

Une boucle à condition de sortie s’écrit entre do et done comme pour la boucle for, mais cette fois-ci on l’écrit après while, suivi par le test. Un exemple se trouve dans l’onglet suivant.

Sujet du Bac L

Voici un sujet du Bac en algorithmique, en l’occurence le Bac L d’Amérique du Sud de novembre 2010 :

On va voir dans cet onglet comment l’algorithme peut être testé avec bash.

Pour n=3

L’initialisation consiste juste à affecter (et créer au passage) les variables u, S et i à leurs valeurs initiales avec le symbole d’égalité :

u=1
S=1
i=0

Pour le traitement, tant que i$<$n se traduit par while i less than n, ou plus précisément "tant que la valeur de i est plus petite que la valeur de n" ; bref par

while [ $i -lt $n ]

Pour la sortie, on utilise echo comme vu dans l’onglet précédent. Finalement, le script est le suivant :

Pour une liste de valeurs de n

Pour remplir le tableau, il suffit de remplacer le n=3 par une boucle sur plusieurs valeurs de n ; donc de mettre le tout entre do et done :

Une façon plus algorithmique de faire [5], consiste à redéfinir le traitement comme une fonction sur n, qu’on va appeler Solution, et qui se définit avec des parenthèses vides : C’est dans le corps de la fonction que bash saura qu’il y a une variable entière, qui s’appellera $1 (variable numéro 1). On peut en profiter pour déclarer u, S et i comme variables locales :

On constate que l’argument d’une fonction n’est pas entre parenthèses : bash pratique plutôt la notation cos x que l’ancienne cos(x) (ou plutôt ce serait le cas si bash faisait de la trigonométrie ce qui n’est pas le cas puisque bash ne connaît que les entiers).

L’utilisation des fonctions sera continuée dans les onglets suivants, notamment le pgcd qui est une fonction de deux variables $1 et $2.

Fibonacci

Comme la suite de Fibonacci est composée d’entiers, son calcul est tout-à-fait à la portée de bash :

Syracuse

Bien qu’elle ne soit pas au programme de spé maths, la suite de Collatz et la conjecture de Syracuse la concernant sont de nature à la fois algorithmique et arithmétique. Pour une exploration expérimentale de la suite de Collatz, on peut utiliser des fonctions (voir onglet précédent) et construire un script en deux temps : Une fonction UnTour qui réalise la récurrence et la suite proprement dite, construite dans une fonction Suite dont on ne sait actuellement si elle converge.

Récurrence

Dans la fonction UnTour, on utilise une variable locale reste qui, comme son nom l’indique, contient le reste de l’antécédent modulo 2. En effet, selon la valeur de ce reste, on applique l’une des deux fonctions affines suivantes :

  • $n \mapsto \frac{n}{2}$ si le reste est nul ;
  • $n \mapsto 3n+1$ sinon ;

En se rappelant que l’antécédent de la fonction est noté $1, on a le test suivant ("différent de" s’écrit -ne comme not equal) :

UnTour(){
   local reste
   let "reste=$1%2"
   if [ $reste -ne 0 ]
   then return $((3*$1+1))
   else return $(($1/2))
}

Pour tester cette fonction de N dans N, on l’applique successivement aux entiers de 0 à 5 en affichant l’antécédent avec (ce qui donne un tableau de valeurs de la fonction, dans la console en bas à droite) :

Suite de Collatz

Maintenant que la récurrence fonctionne, on peut calculer la suite de Collatz, avec deux variables locales i (l’indice de la suite) et u (le terme courant de la suite) :

  • i est initialisé à 0 parce que le premier terme de la suite est $u_0$ ;
  • u est initialisé avec l’argument de la fonction Suite parce que le premier terme de la suite est cet argument.

Dans une boucle à condition d’arrêt (elle s’arrête dès qu’on entre dans le cycle 1->4->2->1), on réalise alors les opérations suivantes :

  1. on affiche le terme courant de la suite, avec son indice entre parenthèses ;
  2. on incrémente l’indice i ;
  3. On applique la fonction UnTour à u ce qui renvoie un entier stocké dans $ ? (cette notation rappelle un peu le "answer" des calculatrices, sauf que c’est une question qui est représentée ici, pas une réponse...)
  4. on affecte u avec le résultat obtenu.

En appliquant la fonction Suite au nombre 13, on obtient cet affichage dans la console :

Test de primalité

Un petit apéritif : Les décompositions en facteurs premiers des entiers de 2 à 20 :

Comme bash n’a pas de variables booléennes ("que des entiers et des chaînes de caractères, qu’on vous dit !"), la fonction EstPremier décrite ci-dessous renvoie un entier égal à zéro si l’argument est composé, à un sinon. Cet entier s’appellera oui ci-dessous et c’est une variable locale initialisée à 1 (il suffit d’un seul diviseur pour l’annuler, et elle sera égale à 1 à la fin si et seulement si aucun diviseur n’a été trouvé).

Une seule autre variable locale sera nécessaire, le diviseur à tester, et il s’appellera donc diviseur. On l’initialise à 3 pour lui faire parcourir une suite de raison 2 (ce qui évite de tester la divisibilité par 4, 6, 8 etc).

Dans un premier temps, on regarde si n est pair auquel cas il est composé :

if [ $(($n % 2)) -eq 0 ]
then oui=0
fi

Ensuite on parcourt une boucle (tant que le carré du diviseur est inférieur à n) : Si, modulo le diviseur, n est nul, c’est que n a un diviseur et la variable oui est là aussi annulée. De toute façon, on ajoute 2 au diviseur potentiel pour passer successivement à 5, 7, 9 etc :

while [ $(($diviseur**2)) -lt $n ]; do
   if [ $(($n % $diviseur)) -eq 0 ]
       then oui=0
   fi
   let "diviseur+=2"
done

C’est tout ! Il n’y a plus qu’à retourner la valeur finale de oui, 0 si n est composé, et 1 si n est premier :

L’affichage de la console montre que, sur les années de 2010 à 2020, seules 2011 et 2017 sont des nombres premiers (la boucle sur p appelle la fonction EstPremier avec pour argument p puis affiche p et le résultat du test). Qui sait, ça peut servir dans un dîner (et il reste 8 ans pour modifier le script bash qui donnera la réponse sur la décennie suivante !).

Euclide

L’algorithme d’Euclide est assez facile à traduire en bash dans sa version itérative avec les divisions euclidiennes (puisque bash a une fonction "modulo"). Comme la fonction pgcd a deux variables, celles-ci seront $1 et $2 qui vont commencer par être stockées dans deux variables locales a et b ; comme le calcul parallèle n’est pas encore répandu dans les PC, on a besoin d’une troisième variable où on stockera provisoirement les résultats des calculs, et qui s’appellera r puisque ce sera le reste dans une division euclidienne.

La boucle continue tant que b est non nul ("greater than 0" abrégé en -gt 0) ; on y fait les affectations classiques :

  1. stocker dans r le reste de a par b ;
  2. écraser a (dont on n’a plus besoin) avec b
  3. remplacer b par r.

À la sortie de la boucle, on retourne la valeur finale de a qui est le pgcd :

Une fois que bash est enrichi de cette nouvelle commande, on peut calculer le pgcd de 12 et 16 en entrant

pgcd 12 16
echo $?

La dernière ligne ayant pour but d’afficher le résultat obtenu.


Une fois que c’est fait, on peut enrichir l’algorithme d’Euclide pour qu’il calcule aussi les nombres u et v du théorème de Bézout. On utilise les notations du document d’accompagnement d’Xcas.

Comme une fonction de bash retourne un entier et qu’ici on en a besoin de deux, on ne retourne en réalité rien dans la fonction Bezout ci-dessus (parce qu’il n’y a aucune ligne qui commence par "return") mais on y affiche le résultat voulu (u, v et l’égalité de Bézout).

Simulation

Juste pour montrer qu’on ne fait pas que de l’arithmétique avec bash, on va voir ici comment on peut simuler le lancer de deux dés et obtenir le tableau des effectifs (sur 1000 simulations).

Pour lancer un dé, on récupère auprès du système d’exploitation un entier pseudo-aléatoire et on le réduit modulo 6, ce qui fournit un entier pseudo-aléatoire entre 0 et 5 ; il suffit alors d’ajouter 1 pour avoir un résultat de dé :

let "de1=$RANDOM%6+1"
let "de2=$RANDOM%6+1"
let "resultat=$de1+$de2"

La variable resultat contient alors la somme des deux dés.

Il n’y a qu’à faire ça 1000 fois et stocker les résultats dans un tableau des effectifs et on a fini. Sauf que bash n’a pas de tableau [6] (mais puisqu’on se tue à vous le répéter, que des entiers et des chaînes de caractères, qu’on vous a dit !). Alors on va créer des variables qui s’appelleront effectifs2, effectifs3 etc. Et on va les créer dans une boucle sur n allant de 2 à 12, en initialisant (ce qui aura pour effet de la créer) une variable appelée effectifs$n qui aura bien le nom voulu. Créer 12 variables ayant les noms voulus se fait donc en une ligne (la ligne 3 ci-dessous) :

for n in `seq 2 12`; do let "effectifs$n=0"; done

Qui a dit qu’on avait besoin d’un tableau ?

Pour ce qui est d’incrémenter les "cellules" du "tableau", il suffit, avec le résultat du lancer des deux dés, de faire

let "effectifs$resultat++"

Une fois qu’on a fini de lancer les deux dés, la variable effectifs2 contient par exemple 30 (si la somme était égale à 2 sur 30 des 1000 lancers) et il suffit pour afficher les effectifs, d’une variable e affectée avec le fameux effectifs$n et affichée à côté de n dans une phrase du plus bel effet :

Conclusion

Pour la cryptographie par contre, il est plus difficile d’utiliser bash parce que l’obtention des caractères d’un texte et leur conversion en entiers sont plus compliqués qu’avec d’autres langages. Cependant bash peut fabriquer des clés publiques RSA avec l’instruction rsa, coder un fichier avec openssl... Des implémentations du chiffrage de Vigenère, du chiffrage affine ont déjà été faites en bash.

Pour le chiffre de Cesar par contre, le codage (et le décodage) avec bash se font très rapidement avec la commande tr (Unix) de transposition. Par exemple

echo "voici un message que bash peut coder" | tr 'a-z' 'd-za-c'

pour coder le message, et

echo "yrlfl xq phvvdjh txh edvk shxw frghu" | tr 'a-z' 'x-za-w'

pour le décoder.


De façon générale, bash possède dans son jeu d’instructions tous les logiciels installés, et certains lanceurs sont de simples scripts en bash. Par exemple, lancer le logiciel Scratch (langage) revient juste à exécuter ce script (on remarque que ce n’est pas bash qui est utilisé, mais sh) :

Un autre exemple très connu est Firefox.

Du point de vue des élèves, voici quelques avantages qu’il peut y avoir à utiliser bash pour faire de l’arithmétique :

  1. Sur un OS comme la clé agreg par exemple, bash est le langage par excellence parce qu’il ne nécessite pas l’interface graphique.
  2. Sur un UNIX en général, faire du bash, c’est connaître les arcanes de son
    propre ordi, ce qui est satisfaisant pour les élèves (et les collègues le cas échéant) qui sont assez curieux pour vouloir regarder ce qu’il y a dans le "ventre de la bête".
  3. Savoir programmer en bash, c’est entre autres savoir faire un installeur,
    savoir programmer une tâche qui démarre à un moment précis, etc.
  4. Faire de l’arithmétique avec un langage qui ne sait faire que ça, peut paraître assez logique. Dans la même veine, on peut penser à des langages "restreints" utilisés dans l’enseignement de la programmation, comme Brainfuck ou FRACTRAN. Personnellement, j’ai au moins appris en rédigeant cet article, à quel point les nombres réels sont utiles en algorithmique, en pestant régulièrement contre bash quand j’avais besoin desdits réels !
  5. chez moi [7] bash occupe 799,1 kilooctets (et sh occupe 81,9 kilooctets !),
    qui dit mieux ?

Lectures conseillées

Les deux ouvrages ci-dessous ont en commun le fait que leurs auteurs ont privilégié la clarté sur l’exhaustivité, qu’ils en soient remerciés (par exemple en lisant voire achetant leur livre) !

  • le wikibook
  • le framabook qui vaut largement ses 25€ (devrait faire partie de la bibliothèque de tout enseignant de l’ISN)

notes

[1Priver les utilisateurs d’un système d’exploitation privatif, il faut le faire !

[2Attention, il semble que le bash des ordinateurs Apple soit plus pauvre que celui des Linux, et certains des scripts décrits ci-dessus pourraient ne pas tourner sous Mac. Quant aux téléphones portables, l’auteur n’en possédant pas, n’a pu tester sur l’un d’entre eux...

[3C’est exactement la même manipulation avec les langages Python (langage), Ruby etc.

[4Ça doit rappeler des souvenirs au programmeurs en Perl et en php !

[5Au sens où elle permet de mieux réinvestir l’effort consenti jusqu’ici, sur d’autres exemples comme ceux des onglets suivants...

[6En fait, pour les versions les plus récentes de bash, les tableaux existent et se notent comme dans les autres langages avec des crochets.

[7Ubuntu 10.04 "Lucid Lynx" en l’occurence, avec bash 4.1.5 et sh 4.4

Réagir à cet article
Vous souhaitez compléter cet article pour un numéro futur, réagir à son contenu, demander des précisions à l'auteur ou au comité de rédaction...
À lire aussi ici
MathémaTICE est un projet
en collaboration avec
Suivre la vie du site Flux RSS 2.0  |  Espace de rédaction  |  Nous contacter  |  Site réalisé avec: SPIP  |  N° ISSN 2109-9197