Programmation en C– pour les maths

Bernard Parisse

Ce document s’adresse à des étudiants qui poursuivent des études de mathématiques et sont déjà un peu familiarisés avec la programmation, en général avec le langage interprété Python. Il s’agit d’une introduction au C–, c’est-à-dire au langage C, en utilisant certaines facilités du langage C++ (notamment les entrées/sorties, vector pour les tableaux de taille dynamique, string pour les chaines de caractère, la redéfinition des opérateurs et les templates).

Table des matières

Index

  • éditeur, 3

  • Android, 3
  • aléatoire, générateur, 12.1
  • auto, 2

  • bibliothèque, 11
  • boucle, 2
  • break, 2
  • bug, 13

  • CPU, 1
  • cerr, 6
  • chaine de caractères, 4
  • char, 2
  • cin, 3, 6
  • commandes Unix, 3
  • compilateur, 1
  • compilateur, options, 11
  • complexe, nombre, 2
  • const, 2
  • constante, 2
  • constructeur, 9
  • continue, 2
  • cout, 3, 6

  • debug, 13
  • dictionnaire, 4
  • donnée, 2
  • double, 2

  • else, 2
  • emacs, 3
  • entier, 2
  • entrée, 6
  • exception, 10

  • float, 2
  • flottants, précautions, 8
  • flux, 6
  • fonction, 2
  • for, 2

  • générateur aléatoire, 12.1
  • gdb, 13

  • header, 11

  • if, 2
  • include, 2
  • int, 2
  • interpréteur, 1
  • iomanip, 6
  • iostream, 3

  • Linux, 3
  • library, 11
  • long double, 2
  • long long, 2

  • MacOS, 3
  • Makefile, 11
  • main, 2
  • map, 4
  • microprocesseur, 1

  • nombre complexe, 2

  • options, 11

  • permutation, 12.2
  • pointeur, 2

  • référence, 5
  • régistre, 1
  • rand, 12.1
  • rediection, 3
  • return, 2
  • runtime error, 10

  • SEGFAULT, 13
  • setprecision, 6
  • shell, 3
  • sortie, 6
  • srand, 12.1
  • string, 4
  • struct, 9

  • Tableaux, 4
  • tableau C++, 4
  • template, 7
  • test, 2
  • type, 2
  • typedef, 5, 7

  • Unix, commandes, 3
  • unsigned, 2

  • vector, 4

  • Windows, 3
  • while, 2

1  Langage, programme et ordinateur

Un ordinateur (au sens large du terme) est composé au minimum d’un microprocesseur (CPU, central processing unit) et de mémoire : on distingue la RAM (random access memory), parfois la ROM (read only memory), ces mémoires sont directement adressables par le CPU, et la mémoire de stockage (disque dur, clef USB, carte SD ...) non adressable directement par le CPU.

Le microprocesseur possède un nombre limité de régistres (dont la valeur est un entier de taille limitée, en général à 32 ou 64 bits), et effectue la plupart du temps des opérations sur ces régistres : opérations arithmétiques, opérations de lecture/écriture vers la mémoire (données). Ces opérations sont exécutées séquentiellement (sauf instruction de branchement) selon la valeur d’une plage d’adresses consécutives en mémoire (c’est le code). Par exemple pour stocker la valeur d’un régistre à une adresse mémoire de donnée, on devra utiliser deux adresses consécutives de code: la première est l’“opcode” qui indique au CPU quelle action effectuer, la deuxième est l’adresse mémoire de la donnée.

Pour exécuter un programme, il faut donc le décomposer en une suite d’actions très simples exécutables par le CPU, créer la suite de valeurs du code, la charger en mémoire et brancher le CPU à cette adresse mémoire. Comme le nombre d’actions du CPU est très important même pour une tache qui parait simple à un humain, l’humain ne crée pas lui-même les instructions du code, il utilise un langage de programmation et c’est un programme qui se charge de traduire les instructions du langage de programmation en une suite d’instructions compréhensible par le CPU. Il exite principalement deux façons de faire cette traduction: soit on le fait au fur et à mesure (instruction par instruction) avec un interpréteur, soit on le fait globalement, avec un compilateur. Python, Javascript utilisent la première méthode, C/C++, Pascal, Lisp, ... utilisent la deuxième méthode.

Chaque méthode a ses avantages et inconvénients. Un des avantages de la compilation est la vitesse d’exécution, le temps de “traduction” n’intervient plus et des optimisations sont possibles. Un des avantages des interpréteurs, c’est l’indépendance (en principe) de la plateforme, il n’est pas nécessaire de traduire pour plusieurs CPU, c’est l’interpréteur qui s’en charge. Certains programmes font parfois un mix des deux, les parties de code non critiques sont écrites en langage interprété, et les parties critiques en langage compilé (par exemple du calcul matriciel avec des matrices de grande taille).

Comme vous avez déjà travaillé avec un langage interprété (Python), cette UE va vous donner l’occasion de travailler avec un langage compilé, le langage C, qui est un langage très répandu, avec quelques ajouts bien utiles que permet le C++. Le langage C est très proche de la machine, il faut souvent plus de lignes de code pour obtenir un résultat analogue à celui d’un programme écrit en Python, mais cela permet aussi de mieux comprendre ce qui se passe, en particulier lorsqu’on s’intéresse aux questions de temps d’exécution/complexité.

2  Données, type, instructions, contrôle du flux d’exécution

Les données accessibles au CPU sont stockées en mémoire à des adresses précises, mais ce n’est pas pratique pour les humains. On utilise à la place la notion de variable pour stocker une donnée, une variable c’est un couple (nom,valeur). Il faut aussi choisir un format de représentation pour les données (qui in fine vont occuper une ou plusieurs adresses mémoires). Certains langages, comme Python ou Javascript, permettent de stocker des données n’ayant pas le même format de représentation dans une même variable. D’autres langages, comme C, ne le permettent pas, il est obligatoire de spécifier le format de représentation d’une donnée stockée dans une variable, on parle de type et il est obligatoire de déclarer une variable avant de pouvoir l’utiliser.

Le langage C possède des types de base qui sont des formats de données directement gérés par le CPU. Les types C les plus utilisés sont:

On déclare une ou plusieurs variables dans une instruction en indiquant le type puis la ou les variables, par exemple
int a,b;
On peut donner une valeur à une variable, c’est une affectation, cela peut se faire dès la déclaration ou plus tard.
a=2; b=3;
int c=a+b;
Une déclaration de variable permet de l’utiliser soit dans tout le programme (variable globale) soit dans une partie du programme (variable locale à un bloc d’instruction, par exemple variable locale à une fonction). Les constantes sont des cas particuliers de variables dont la valeur est fixée une fois pour toutes, elles sont déclarées avec le mot clef const avant le type, par exemple
const double euler_gamma=0.577215664902;
Une instruction peut être une déclaration, une affectation, une opération arithmétique (avec en général affectation du résultat) ou une instruction de controle du flux d’exécution :test, boucle, appel de fonction. Les instructions sont organisées en blocs, qui sont explicitement délimitées par les délimiteurs { et }, sauf si le bloc ne contient qu’une instruction (qui se termine alors par un ;). L’indentation ne joue pas de rôle pour le compilateur, contrairement à l’interpréteur Python. On utilisera l’indentation dans le texte source comme détecteur d’erreur, si le système d’indentation de l’éditeur du source fait apparaitre une instruction mal indentée, cela signale une erreur de syntaxe plus haut.

Le controle de flux d’exécution, se fait par des tests, boucles et fonctions, comme dans la plupart des langages avec la syntaxe suivante :

Le point d’entrée d’un programme est la fonction main dont le prototype simplifié est
int main(){ ... }
Il faut donc toujours définir une fonction main dans un programme C/C++.

Remarque pour utilisateur avancé uniquement :
Le prototype avancé de la fonction main est
int main(int argc,char ** argv)
il permet de passer en argument de main les chaines de caractères C de la ligne de commande qui a appelé le programme dans le shell. L’entier argc indique le nombre d’arguments en ligne de commande, il vaut toujours au moins 1, argv[0] est le nom du programme, argv[1] le premier argument, etc. Si les paramètres sont des nombres, il faut les convertir en entier (atoi, atol, atoll de #include <stdlib.h>) ou en double (atof). Par exemple pour passer une précision en argument optionnel, on écrira dans main
double eps=1e-10; if (argc>=2) eps=fabs(atof(argv[1]));
et on appellera depuis le shell par exemple
./a.out 1e-12

Pour utiliser des fonctions écrites par d’autres dans son propre programme, il est nécessaire de disposer de la déclaration des prototypes de ces fonctions, ce qui se fait par la directive #include suivi par le nom d’un fichier qui contient les déclarations. Il faudra aussi indiquer au compilateur où trouver les versions compilées de ces fonctions par une option de compilation. Pour les fonctions de la librairie standard C, la librairie mathématique et la librairie standard C++, l’option de compilation est en général automatiquement ajoutée par le compilateur, sinon il s’agit avec les compilateurs de la famille GCC ou clang de -lc -lm -lstdc++. Le code d’initialisation du programme (chargement de la valeur des variables globales) est aussi en général automatiquement ajouté (crt*.o, pour C-runtime).

3  Premier programme

Nous sommes maintenant en mesure de créer un premier programme. Pour tester, il nous faut un environnement de développement. Il en existe beaucoup, selon la machine cible et l’OS de la machine de développement. Le plus simple, sobre et universel est d’utiliser un shell dans un terminal, un éditeur de texte et un compilateur. Si vous n’en connaissez pas, voici des suggestions pour le shell et le compilateur :

Il faut ensuite installer un éditeur de texte source qui reconnait le langage C (attention à ne pas confondre avec un traitement de texte!). Si vous n’en connaissez pas déjà un, je conseille d’utiliser emacs qui dispose de versions Linux, Windows et Mac.

Vous pouvez aussi utiliser des environnements plus gourmands, comme codeblocks, qt creator, visual studio, ... qui sont surtout intéressants pour de gros projets. Pour un débutant, il y a un risque à se perdre dans une interface plus complexe.

Ouvrez maintenant votre terminal/shell et lancez la commande pour exécuter l’éditeur, par exemple sous Linux
emacs prog.cc &
Si vous avez l’habitude des raccourcis d’édition Windows, cochez si nécessaire dans Options Use CUA keys. Tapez le texte source suivant 

#include <iostream>
using namespace std;

int main(){
  int a,b;
  cout << "Entrez deux entiers :";
  cin >> a >> b;
  cout << "La somme vaut " << a+b << "\n";
  return 0;
}

Explications: iostream est la bibliothèque qui gère les entrées-sorties à la console, avec deux “variables” représentant la console en entrée (std::cin) et en sortie (std::cout) et les opérations << et >> qui dirigent dans le sens des flèches un “flux” de donnée (variable de ou vers console). Le using namespace std; permet d’abréger la notation de ces deux variables. \n est utilisé pour représenter un retour à la ligne.

Puis sauvegardez et compilez :
g++ prog.cc
Pour l’exécuter, tapez ./a.out (Linux, Mac) ou ./a.exe (Windows). Modifiez le code source dans l’éditeur pour calculer le produit de deux nombres approchés. Astuces : pour retrouver une commande dans l’historique des commandes, utilisez la flèche du curseur vers le haut ou le bas. Pour passer d’une fenêtre à une autre sans la souris, utilisez Control et la touche de tabulation (windows/linux).

Conseil : je recommande de connaitre un minimum de commandes Unix pour les utiliser dans le shell. Ces commandes existent depuis plus de 50 ans et existeront très certainement encore dans 50 ans, c’est un investissement sur, contrairement aux interfaces graphiques qui changent toutes les quelques années.

  1. ls: liste les fichiers et répertoire du répertoire courant. ls -lt permet d’afficher les fichiers par ordre de date du plus récent au plus ancien.
  2. pwd: chemin du répertoire courant
  3. cd chemin: déplace vers un autre répertoire (absolu si chemin commence par /, relatif sinon) cd déplace vers le répertoire “home”.
  4. cp source cible copie un fichier
  5. mv source cible déplace ou renomme un fichier
  6. rm -i cible efface un fichier (attention, l’effacement est irréversible, l’option -i demande une confirmation)
  7. mkdir et rmdir permettent de créer un répertoire ou de l’effacer si il est vide.
  8. man nom_de_commande: aide sur une commande

On peut utiliser la touche de tabulation (à gauche de A sur un clavier français) pour compléter un nom de fichier ou de commande. On peut utiliser des jokers pour indiquer plusieurs noms de fichiers, * remplace n’importe quelle chaine de caractères, ? remplace n’importe quel caractère, ainsi ls -lt *.cc permet d’afficher tous les fichiers dont le nom termine par .cc. Ou grep double *.cc va afficher toutes les lignes de code source C++ contenant le mot double.

On peut rediriger l’affichage d’un programme vers un fichier avec >, par exemple ./a.out > log. On peut exécuter un programme en tache de fonds en ajoutant &, par exemple ./a.out > log &. On peut même lancer un programme en tache de fonds et quitter la session avec nohup, par exemple nohup ./a.out >& log & lance le programme en tâche de fonds et redirige tous les affichages vers le fichier log, vous pouvez quitter votre session et revenir plus tard lire le fichier log lorsque le programme sera terminé.

Quelques raccourcis et astuces emacs (qui existent depuis presque 50 ans et existeront certainement encore dans 50 ans, encore un investissement sur! L’analogue existe avec vi, “l’autre” éditeur Unix). Attention, certains d’entre eux ne fonctionnent pas si vous activez la compatibilité des raccourcis d’édition windows.

4  Tableaux

C possède des types “pointeur” sur un type donné qui désigne une adresse en mémoire ou est stocké une donnée de ce type de donnée. Par exemple char * est un type pointeur sur une adresse mémoire contenant un caractère. Le contenu d’une adresse se note alors *pointeur. L’adresse d’une variable se note &nom_variable. Ainsi
char ch='a'; char * ptr=&ch; cout << *ptr;
est une manière compliquée d’afficher un a à l’écran. L’utilisation de pointeurs est un peu délicate, pour éviter cela on utilisera certaines facilités du C++.

Pour représenter un tableau de données toutes du même type en C, on utilise une variable de type pointeur, dans laquelle sera stockée l’adresse de la “première” donnée du tableau. On utilise une notation adaptée pour créer un tableau C:
type nom_variable[nombre_elements];
et on lui donne souvent une valeur. Par exemple char chaine[16]="bonjour"; déclare une variable chaine pouvant contenir 16 éléments et initialisée avec 8 caractères (les 7 caractères de bonjour, et un 8ème caractère nul qui marque la fin de la chaine). On peut laisser le compilateur déterminer la taille du tableau, par exemple
char chaine[]="bonjour";
crée une variable de taille 8. Pour des tableaux d’autres types que les chaines de caractères, les valeurs d’initialisations du tableau sont à saisir entre des délimiteurs {} et séparés par des virgules, par exemple
int premiers[]={2,3,5,7,11,13,17,19};

On peut ensuite accéder en lecture ou en écriture à un élément du tableau en indiquant un index compris entre 0 et la taille du tableau moins un. Ainsi chaine[0] vaut le caractère 'b'.

Un tableau C défini de cette manière a une taille définie une fois pour toutes, ce qui n’est pas forcément idéal pour faire des maths, par exemple pour représenter un polynôme en une variable il est agréable de pouvoir stocker des tableaux de taille le degré du polynôme plus un. Pour pouvoir adapter la taille d’un tableau C, il faut le déclarer comme un pointeur et définir ce pointeur en allouant de la place en mémoire (sur le tas, “heap” en anglais), ce qui est délicat lorsqu’on débute. Heureusement, la libraire standard C++ a un type “générique” vector qui permet de travailler avec des tableaux de taille dynamique (non fixé à la compilation) sans avoir à gérer la mémoire soi-même. Pour utiliser ce type il faut écrire #include <vector> au début du fichier source.

Un tableau C++ se définit donc comme un vector<type>, par exemple vector<double> P(5); définit une variable P qui est un tableau de double. Ici P possède 5 éléments (initialisés à 0), mais on peut en ajouter ou en enlever à l’aide de deux méthodes. Une méthode est une fonction associée à un type qui prend un argument implicite, la variable associée au type, on l’appelle en donnant le nom de variable suivi par un . puis par le nom de méthode et ses éventuels arguments explicites. Ainsi P.pop_back(); supprime le dernier élément de P. Ou P.push_back(1); ajoute un 1 à la fin de P.

Instructions fréquemment utilisées avec vector :

La librairie standard C++ dispose aussi d’un type spécialisé pour les chaines de caractères, c’est string. Pour l’utiliser il faut écrire au début du fichier source #include <string>. En plus des instructions ci-dessus, on peut concaténer des string avec +, on peut initialiser une string avec un "message".

Enfin, il est possible de créer des “annuaires” ou dictionnaires, sortes de tableaux indiciés par une donnée de type plus général qu’un entier, il doit s’agit d’un type pour lequel on a une relation d’ordre, par exemple l’ordre lexicographique pour les chaines de caractères. On déclare en début de fichier #include <map>, puis pour déclarer par exemple un annuaire (tableau indicié par une chaine de caractères et de valeur un entier)
map<string,int> annuaire;
on peut ensuite créer une entrée avec annuaire["Gaston"]=612345678;. Pour lire une valeur existante, on utilisera par exemple
cout << annuaire["Gaston"] << endl;
Pour savoir si une entrée existe

auto itend=annuaire.end(),it=annuaire.find("Gaston"); 
if (it!=itend){
  cout << it->first << ":" << it->second;
}

Les accès/recherche se font en temps O(ln(n))O(\ln(n)) s’il y a nn entrées.

5  Fonctions

Les arguments peuvent être passés à une fonction de trois manières 

Par exemple pour faire le produit scalaire de deux vecteurs, on écrira
vector<double> dot(const vector<double> & v,const vecteur<double>& w);
Pour calculer les coefficients de Bézout de deux entiers, on peut écrire
int extgcd(int a,int b,int & u,int &v);
la fonction renvoie le PGCD dd de aa et bb et modifie la valeur des variables u et v pour que au+bv=dau+bv=d.

Il existe un type pour les fonctions prenant les mêmes types d’argument et renvoyant un type donné, on utilise en général un typedef pour lui donner un nom. Par exemple si on écrit
typedef double fcn1(double);
alors fcn1 désigne le type d’une fonction qui prend en argument un double et renvoie un double. Ceci permet d’écrire ensuite un algorithme prenant une telle fonction en argument, par exemple un algorithme de dichotomie
double dicho(fcn1 f,double a,double b);

6  Entrées/sorties

La biblithèque C++ définit des flux d’entrées/sorties standard cin pour la console, cout et cerr pour les sorties console et console d’erreur (qui peuvent être distinctes en cas de redirection des sorties vers un fichier avec > lorsqu’on appelle le programme de ligne de commande). Il faut utiliser #include <iostream> pour y accéder. Les opérateurs >> et << sont alors définis pour les types de base vers un flux de sortie ostream ou depuis un flux d’entrée istream. Cela fonctionne aussi pour le type string de la librairie C++ (attention toutefois en entrée le caractère espace sera considéré comme un délimiteur de fin de chaine), mais pas pour le type vector. Il est nécessaire de le redéfinir soi-même en choisissant un format texte de sauvegarde, par exemple longueur du vecteur puis les données. 

#include <iostream>
#include <vector>

using namespace std;

istream & operator >> (istream & is,vector<double> & v){
  int n;
  is >> n;
  v.resize(n);
  for (int i=0;i<n;i++)
    is >> v[i];
  return is;
}

ostream & operator << (ostream & os,const vector<double> & v){
  int n=v.size();
  os << n << " ";
  for (int i=0;i<n;++i)
    os << v[i] << " ";
  return os;
}

Les flux C++ permettent de gérer les entrées/sorties vers un fichier du disque dur de manière analogue à la console. On ajoute en en-tête #include <fstream> puis on déclare un fichier en lecture par ifstream nom_variable("nom_fichier"); et en écriture par ofstream nom_variable("nom_fichier");, par exemple 

vector<double> v={1/3.0,2.3};
ofstream fich("v.txt");
fich << v << endl;

On peut modifier l’affichage des types standard en utilisant la librairie C++ avec en en-tête #include <iomanip>, en insérant dans une commande d’affichage une instruction telle que setprecision, par exemple fich << setprecision(14) << v << endl;

Remarque : la libraire C contient des instructions d’entrée-sortie définies dans #include <stdio> telles que printf, fprintf, scanf, fscanf.

7  Algorithme et types, modèles (template)

Il arrive qu’un algorithme s’applique à plusieurs types. Par exemple certains algorithmes d’arithmétique comme Euclide ou Bézout peuvent s’appliquer à des entiers ou des polynômes.

On peut utiliser typedef pour donner un nom de type et recompiler un programme en changeant juste le type. Mais ce n’est pas très souple. C++ permet de définir une fonction “paramétrique” où on passe en paramètre un type (ou plusieurs), avec le mot clef template. Au lieu de donner un type précis à un argument, on donne le type paramètre. Par exemple 

template<class T> T gcd(T a,T b){
  while (b!=0){
    T r = a%b;
    a=b;
    b=r;
  }
  return a;
}

int a=55, b=25,c=gcd(a,b);
long long A=12345678901233,B=45362890000597,C=gcd(A,B);

Il y aura deux fonctions gcd, une pour des int (de taille inférieure à 2 31)2^{31}) et l’autre pour des longlong (de taille jusque 2 632^{63}).

Ce mécanisme s’applique également à la définition d’opérateurs, ainsi on peut utiliser 

template<class T>
istream & operator >> (istream & is,vector<T> & v){
  int n;
  is >> n;
  v.resize(n);
  for (int i=0;i<n;i++)
    is >> v[i];
  return is;
}

template<class T>
ostream & operator << (ostream & os,const vector<T> & v){
  int n=v.size();
  os << n << " ";
  for (int i=0;i<n;++i)
    os << v[i] << " ";
  return os;
}

et cela fonctionnera pour des vector<int> comme pour des vector<double>. Et cela fonctionnera aussi pour des vector< vector<double> > (qu’on peut utiliser pour représenter des matrices avec des vecteurs de vecteurs de mêmes tailles).

Remarques :
Si on a un type polynôme pour lequel le reste euclidien est défini par l’opérateur % et l’opérateur != est défini, on peut alors utiliser la fonction paramétrique gcd sans avoir besoin de la redéfinir. La fonction sera alors compilée spécifiquement pour le type polynôme avec appel directement de la fonction de calcul de reste euclidien de polynômes, à la différence d’un langage interprété avec type générique où l’appel sera décidé en fonction du type au moment de l’exécution.

8  Précautions à prendre avec les types flottants.

Les flottants permettent de représenter les nombres réels de manière approchée, mais il ne faut pas perdre de vue qu’il s’agit uniquement de rationnels dont le dénominateur est une puissance de 2, et avec une précision limitée, il faut donc prendre quelques précautions. D’abord, on ne fait presque jamais un test d’égalité entre deux flottants, on va plutôt regarder si la différence est en valeur absolue inférieure à une précision donnée, qui peut être absolue (|b−a|<ε|b-a|&lt;\varepsilon fabs(b-a)<eps) ou relative (|b/a−1|<ε|b/a-1|&lt;\varepsilon fabs(b/a-1)<eps, attention si a=0a=0).

Ensuite, il faut se souvenir que si on fait la différence entre deux nombres proches, on perd en nombre de chiffres significatifs, d’autant plus que les deux nombres sont proches. Il est parfois possible de réécrire un calcul pour l’éviter, par exemple pour résoudre une équation du second degré avec les formules r ±=−b±Δ2ar_\pm=\frac{-b\pm \sqrt{\Delta}}{2a} l’une des formules fait intervenir la différence entre deux nombres qui peuvent être proches, il vaut alors mieux calculer l’autre racine et utiliser r +r −=car_+ r_-=\frac{c}{a} C’est aussi pour cette raison que la librairie mathématique possède une fonction expm1 (valeur plus précise de e x−1e^x-1 pour xx petit) et une fonction log1p (valeur précise de ln(x+1)\ln(x+1) pour xx petit).

Enfin, lorsqu’on a une somme de nombres à calculer, le résultat sera plus précis si on commence par sommer les plus petits. Ainsi dans une somme de série numérique convergente, il faut faire une boucle en commençant par les grands indices, comme ici : erreur2.cc On peut d’ailleurs améliorer la précision en calculant un terme de correction au fur et à mesure de la boucle.

9  Types structurés

Les types de base et extension de la librairie C++ ne suffisent pas toujours à représenter les objets mathématiques qu’on souhaite manipuler. Par exemple pour représenter des rationnels dont le numérateur et le dénominateur sont des petits entiers, il nous faut deux int. Plutot que de passer deux arguments pour travailler sur un rationnel, on définit une structure avec plusieurs membres, par exemple
struct rationnel { int num,den; };
Ensuite on déclare une variable de type rationnel et on peut accéder au numérateur et au dénominateur en utilisant le nom de variable suivi de . et du nom du membre
rationnel q={2,3}; cout << q.num << "/" << q.den;

On peut ensuite définir des fonctions prenant en argument des rationnel comme si c’était un type de base C. Cela s’applique aussi aux opérateurs, par exemple pour définir la multiplication de deux rationnels 

rationnel operator * (const rationnel & a,const rationnel & b){
  rationnel res={a.num*b.num,a.den*b.den};
  return res;
}

On peut simplifier un peu l’écriture ci-dessous en utilisant un constructeur, à définir lors de la déclaration de rationnel 

struct rationnel { 
  int num,den; 
  rationnel(int n,int d):num(n),den(d) {}
};

rationnel operator * (const rationnel & a,const rationnel & b){
  return rationnel(a.num*b.num,a.den*b.den);
}

On observe que nos fractions ne sont pas réduites, on peut ajouter une simplification par le pgcd dans le constructeur 

struct rationnel { 
  int num,den; 
  rationnel(int n,int d):num(n),den(d) {
    int d=gcd(num,den); 
    if (d){
      num /= d; den /= d;
    }
  }
};

On restera malgré tout limité par la taille maximale des entiers.

Pour aller plus loin : La programmation orientée objet définit la notion de classe, il s’agit de structures plus élaborées, où on controle l’accès des données et méthodes (ce sont des fonctions qui sont appelées en donnant le nom de variable suivi d’un point et entre parenthèses les autres arguments de la méthode). On peut créer des hiérarchies de types, spécialisant de plus en plus un objet, par exemple un objet géométrique peut être un point, une droite, etc., cela s’appele l’héritage. Certains algorithmes vont s’appliquer pour tous les types de la hiérarchie, en tenant compte des spécificités de chaque type au moment de l’exécution d’une méthode, on parle de méthode virtuelle et de RTTI (runtime type identification). Par exemple on représentera une figure par un vector d’objets géométriques quel que soit le type d’objet géométrique, l’algorithme d’affichage de la figure va afficher chaque objet un par un, l’affichage étant une méthode virtuelle.

10  Gestion des erreurs d’exécution prévisibles.

Lorsqu’on rencontre une erreur, on peut décider de mettre fin au programme immédiatement en appelant exit(n); où nn est un entier, cela revient à stopper le programme comme si on exécutait return n; dans la fonction main(). Cette méthode convient pour des petits programmes de quelques dizaines de ligne, mais pas pour des programmes plus importants, en particulier les programmes interactifs où l’utilisateur risque de perdre des données non sauvegardées.

Les fonctions de la librairie standard C renvoient souvent une variable de type entier qui permet de savoir si l’opération s’est déroulée normalement et dans le cas contraire on peut regarder le contenu d’une variable globale appelée errno pour connaitre l’erreur. On peut s’en inspirer, par exemple pour calculer un inverse d’entier modulo un entier on peut renvoyer l’inverse ou 0 si l’entier n’est pas inversible. C’est alors à l’appelant de gérer la valeur de retour, et de passer l’erreur à son propre appelant, etc.

Ce n’est donc pas toujours simple de gérer les erreurs correctement en prévoyant tous les cas. Le C++ permet de gérer les erreurs de manière plus automatisée, avec le mécanisme des exceptions et leur traitement. On déclare en en-tête #include <stdexcept>
Pour générer une erreur on utilise throw, pour gérer une erreur on utilise un bloc
try { } catch (exception){ }
Par exemple 

int invmod(int a,int n){
  if (gcd(a,n)!=1) 
    throw(std::runtime_error("Non inversible"));
  ...
}

int main(){
  int a,n; 
  cout << "Calcul de inv(a mod n). Entrez a puis n:";
  cin >> a >> n;
  try {
    int ainv=inv(a,n);
    cout << "L'inverse modulaire est " << ainv << endl;
  } catch (std::runtime_error & e){
    cout << "Une erreur est survenue." << e.what() << endl;
  }
  return 0;
}

11  Compilation, Makefile

Quelques options importantes du compilateur:

Lorsqu’un projet prend de l’ampleur, il devient judicieux de ne pas avoir tout son code source dans un seul fichier. On pourrait par exemple pour des polynômes à coefficients rationnels avoir un fichier qui gère l’implémentation des rationnels et un autre celui des polynômes. Dans celui des polynômes, il faudra accéder aux déclarations permettant de manipuler les rationnels. On crée alors un fichier d’extension .h (comme header) qui reprend uniquement les déclarations, par exemple ici on pourrait l’appeler QQ.h ou rationnel.h. On aura alors un fichier rationnel.cc (ou QQ.cc) contenant les implémentations des fonctions. Et un autre couple de fichiers poly.cc/.h pour les polynômes.

L’option -c du compilateur g++ permet alors de compiler chaque fichier source séparément. On peut alors générer l’exécutable en ajoutant les noms de fichiers objets d’extension .o en argument lors de la compilation du fichier contenant la fonction main.

Par exemple ici on aurait pour compiler tout un projet utilisant des polynômes à coefficients rationnels
g++ -c rationnel.cc
g++ -c poly.cc
g++ prog.cc poly.o rationnel.o

Si on modifie une fonctionnalité des polynômes, on édite poly.cc et on le recompile, il n’est pas nécessaire de recompiler rationnel.cc, par contre il est nécessaire de régénérer l’exécutable (dernière commande ci-dessus).

On peut automatiser le processus en utilisant la commande make qui contient dans un fichier nommé Makefile les commandes nécessaires, organisés en cible à créer, dépendances, commande pour créer une cible avec des dépendances. make reconnait certaines commandes spéciales pour éviter de répéter plusieurs fois le même type de commande. Par exemple ici, cela pourrait donner (utiliser la touche de tabulation pour générer les espaces en début de ligne) 

CXX = g++
CXXFLAGS = -g -I.
OBJS = poly.o rationnel.o

prog: prog.cc $(OBJS)
  $(CXX) $(CXXFLAGS) prog.cc $(OBJS) -o prog

%.o: %.cc
  $(CXX) $(CXXFLAGS) -c $< -o $@

clean:
  rm $(OBJS) prog

Il est possible de regrouper plusieurs fichiers objets d’extension .o en une bibliothèque (statique) d’extension .a avec les commandes ar (pour archive) et ranlib, par exemple
ar cru libpolyrat.a poly.o rationnel.o
ranlib libpolyrat.a
On passe ensuite l’argument -lpolyrat au lieu de poly.o rationnel.o au compilateur. C’est particulièrement utile lorsqu’il y a de nombreux fichiers objets. Si la libraire n’est pas dans le répertoire courant, on peut indiquer son chemin avec l’option -Lchemin. Si les fichiers d’en-tête de la librairie ne sont pas dans le répertoire courant, il faut ajouter l’option -Ichemin à la commande de compilation.

Il exite une variante de bibliothèque, dite dynamique, qui permet de partager le code d’une bibliothèque entre plusieurs exécutables. Il faut générer un fichier d’extension .so (linux/mac) ou .dll (windows) en compilant les fichiers objets avec l’option -shared. Il peut être nécessaire d’indiquer où se trouve une librairie dynamique, sous Linux cela se fait avec la commande
export LD_LIBRARY_PATH = chemin1;chemin2;_ ou pour l’utilisateur root en éditant le fichier /etc/ld.so.conf et en exécutant la commande ldconfig.

12  Pour vos projets

12.1  Aléatoire

La fonction rand() renvoie un nombre entier pseudo-aléatoire compris entre 0 et la constante RAND_MAX. Pour avoir un réel uniformément entre 0 et 1, on utilisera rand()/(RAND_MAX+1.0). Le générateur aléatoire est toujours initialisé par défaut à la même valeur, pour faciliter la mise au point. On peut changer la valeur d’initialisation avec srand(int), par exemple srand(time(NULL))

12.2  Permutations

Une permutation est représentable par un vector<int> donnant les images des entiers de 0 à n−1n-1, par exemple la permutation identité de taille 4 est {0,1,2,3}. La librairie standard #include <algorithm> contient les fonctions next_permutation et prev_permutation qui détermine la permutation suivante ou précédente et permet facilement de les énumérer toutes dans une boucle.

12.3  Interpréteur d’expression

tinyexpr permet de saisir une expression dépendant d’une ou plusieurs variables avec les opérateurs arithmétiques et les fonctions mathématiques usuelles, puis de l’évaluer. Pour l’utiliser il suffit de télécharger les deux fichiers tinyexpr.c et tinyexpr.h et de compiler tinyexpr.c par la commande
gcc -c tinyexpr.c
Voici un programme d’illustration de son usage, qui prend en ligne de commande une expression de deux variables xx et yy entre deux ", et l’évalue pour xx et yy sur un quadrillage et l’affiche. Une adaptation simple utilisant la SDL ci-dessous permettrait d’obtenir une représentation graphique d’un champ de tangente pour une équation différentielle ordinaire y′=f(t,y)y'=f(t,y). 

// -*- compile-command: "gcc -c tinyexpr.c && g++ expr.cc tinyexpr.o -o expr" -*-
#include "tinyexpr.h"
#include <stdio.h>

int main(int argc, char *argv[])
{
  if (argc<2) {
    printf("Usage: %s \"expression\"\n",argv[0]);
    return 0;
  }

  const char *expression = argv[1];
  printf("Evaluating:\n\t%s\n", expression);

  /* This shows an example where the variables
   * x and y are bound at eval-time. */
  double x, y;
  te_variable vars[] = {{"x", &x}, {"y", &y}};

  /* This will compile the expression and check for errors. */
  int err;
  te_expr * fptr = te_compile(expression, vars, 2, &err);

  if (fptr) {
    /* The variables can be changed here, and eval can be called as many
     * times as you like. This is fairly efficient because the parsing has
     * already been done. */
    double xmin=-5,xmax=5,xstep=1;
    double ymin=-5,ymax=5,ystep=1;
    for (y=ymin;y<=ymax;y+=ystep){
      for (x=xmin;x<=xmax;x+=xstep){
        const double r = te_eval(fptr);
        printf("x=%f, y=%f, f(x,y)=%f\n", x,y,r);
      }
    }
    te_free(fptr);
  } else {
    /* Show the user where the error is at. */
    printf("\t%*s^\nError near here", err-1, "");
  }

  return 0;
}

12.4  Entiers et flottants multiprécisions

Pour travailler avec des entiers ou des flottants sans limitation de taille autre que la mémoire disponible entiers avec GMP, flottants avec MPFR, arithmétique d’intervalles avec MPFI

Le type mpz_class représente des entiers en précision arbitraire en C++. Pour l’utiliser, on insère l’en-tête
#include <gmpxx.h>
et on compile avec les options -lgmpxx -lgmp

Par exemple 

#include <gmpxx.h>
#include <iostream>
using namespace std;

// commentez la ligne mpz_class pour mettre au point
// commentez la ligne int une fois au point, et compilez avec -lgmpxx -lgmp
// typedef int entier;
typedef mpz_class entier;

int main(){
  entier a,b;
  cout << "Tapez deux entiers ";
  cin >> a >> b;
  cout << "Le produit vaut " << a*b << endl;
}

12.5  Graphiques

La bibliothèque SDL permet d’afficher des graphiques (2d) sur de nombreuses plateformes. Attention, il ne s’agit pas d’une interface graphique (menus déroulants, boites de dialogues, etc.).

Pour l’utiliser sous Linux debian/ubuntu, il suffit d’installer libsdl-dev (SDL version 1) ou libsdl2-dev (SDL version 2)
sudo apt install libsdl-dev libsdl2-dev
Si on crée un programme pour PC, il vaut mieux utiliser la version 2.

Un exemple de source SDL2 utilisable sur PC emsdl2.cc. À compiler avec g++ emsdl2.cc -lSDL2 ou pour navigateur avec emscripten
emcc emsdl2.cc --use-port=sdl2 -s ASYNCIFY -s SINGLE_FILE -o a.html

En C++, on peut aussi utiliser la librairie SFML qui s’installe sous Linux Debian compatible avec sudo apt install libsfml-dev.

12.6  3d

La librairie OpenGL permet de faire du rendu de scène en 3d. En association avec freeGLUT, on peut faire des programmes interactifs 3d. Installation sur Linux debian via le package freeglut3-dev. Des exemples de code source dont on peut s’inspirer, à compiler avec l’option -lGL -lglut -lGLU

12.7  Calcul symbolique

La librairie Giac permet de faire du calcul symbolique et polynomial en C/C++. Voici un example.

12.8  Créer un exécutable utilisable dans un navigateur

emscripten permet de compiler du C/C++ vers Javascript, le langage intégré aux navigateurs Web. On peut ainsi créer des programmes qui s’exécutent sur PC, tablettes, smartphones, etc. Un intérêt d’emscripten c’est que vous pouvez partager votre programme depuis votre site web personnel, sans que les utilisateurs aient besoin d’installer quoi que ce soit, et avec une vitesse d’exécution pas trop dégradée par rapport à un programme compilé pour PC (on perd un facteur 2 environ).

Vous pouvez aussi développer une interface utilisateur en HTML5, en faisant les calculs en C/C++ compilé en Javascript. C’est nettement plus facile que d’apprendre un toolkit GUI (graphical user interface) tel que Qt ou les GUI natifs de Microsoft ou Apple.

Cf. l’exemple SDL1 de la section 12.5.

12.9  Créer un exécutable pour votre calculatrice

Plusieurs calculatrices graphiques de milieu de gamme peuvent se programmer en C/C++, en compilant le programme sur PC avec un “cross-compiler” (compilateur s’exécutant sur PC mais créant du code qui fonctionne sur une autre architecture)

13  Mise au point

Lorsqu’un programme ne fonctionne pas comme prévu, on peut souvent détecter des erreurs en l’exécutant en pas-à-pas (une ligne de code après l’autre) et en examinant l’évolution du contenu des variables. L’application qui permet de faire cela s’appelle un déboggueur (pour des erreurs d’allocation mémoire, on utilisera plutôt un logiciel spécialisé comme valgrind). Plusieurs interfaces existent, on présente ici gdb sous emacs qui s’exécute dans l’environnement d’édition du texte source.

  1. Utilisez l’option -g lorsque vous compilez (pour utiliser le menu Compile d’emacs, modifiez la première ligne du texte source comme par exemple:
    // -*- mode:C++; compile-command:"g++ -g -Wall essai.cc" -*-)
  2. Compilez le programme, on suppose dans la suite que le programme compilé s’appelle a.out ce qui est le cas par défaut
  3. Dans emacs, sélectionnez Debugger (GDB) dans le menu Tools (ou tapez sur la touche Echap, vous devez voir apparaitre ESC- au bout de quelques secondes, puis selon la version d’emacs tapez xgud-gdb ou xgdb et la touche Entree). Vous devez alors voir dans la ligne d’état en bas:
    Run gdb (like this): gdb a.out
    Modifiez si nécessaire puis tapez Entree. Le deboggueur est activé.
  4. Pour visualiser à la fois le source du programme et le débbugueur, il peut être nécessaire de couper la fenêtre en deux (menu File->&gt;Split Window ou raccourci clavier Ctrl-X 2), et dans l’une des parties de sélectionner le source (menu Buffers ou raccourci Ctrl-X o).
  5. L’étape suivante consiste à mettre un point d’arrêt près de l’endroit où vous suspectez qu’il y a une erreur (par exemple au début d’une fonction suspecte). Il y a deux méthodes, soit en donnant le nom de la routine, par exemple pour le programme principal main:
    b main
    soit dans le code source, en cliquant à gauche de la ligne ou en tapant Ctrl-X puis Ctrl-A puis Ctrl-B à la ligne souhaitée. On peut aussi taper b suivi par le numéro de ligne dans le fichier source (ou b nom_ficher:numero_ligne). Vous pouvez mettre plusieurs points d’arrêt.
  6. Puis on lance l’exécution du programme en cliquant sur Go ou en tapant r (pour run)
  7. Le programme s’exécute normalement jusqu’à ce qu’il atteigne le point d’arrêt. On peut alors visualiser le contenu d’une variable en utilisant l’instruction p suivi du nom de variable (p pour print), par exemple:
    p modulo puis touche Entree
    imprime le contenu de la variable modulo (si elle existe).
  8. L’instruction n (next) exécute la ligne courante. Pour exécuter ensuite plusieurs lignes à la suite, on tape plusieurs fois sur la touche Entree. On peut aussi indiquer un paramtre numérique à la commande n.
  9. L’instruction s (step in) permet de rentrer à l’intérieur d’une fonction si la ligne courante doit exécuter cette fonction (alors que n exécute cette fonction en un seul pas, sauf si cette fonction contient un point d’arrêt)
  10. L’instruction u (until) exécute le programme sans arrêt jusqu’à ce que la ligne de code source suivante soit atteinte (ou une adresse donné en paramètre). C’est particulièrement intéressant pour sauter au-delà d’une boucle.
  11. L’instruction c (continue) permet de continuer l’exécution jusqu’au prochain point d’arrêt. On peut aussi indiquer un paramètre pour ignorer le point d’arrêt un certain nombre de fois.
  12. kill permet de stopper le programme en cours,
  13. d permet de détruire un point d’arrêt (on donne alors son numéro) ou tous les points d’arrêt. On peut aussi temporairement désactiver ou réactiver un point d’arrêt (commandes disable et enable)
  14. f 0, f 1, etc. permet de visualiser la fonction appelante à l’ordre demandé, l’ordre est calculé depuis la fonction interrompue (0 pour la fonction actuelle, 1 pour la 1ère appelante, etc.), ainsi que les variables de cette fonction. Cette commande peut d’ailleurs être utilisée en cas de Segmentation fault sans mettre de point d’arrêt au préalable.
  15. Vous pouvez corriger une erreur dans la fenêtre d’édition, recompiler le programme et revenir dans la fenêtre gdb (c’est le buffer nommé *gud-a.out*) puis reprenez ce mode d’emploi à l’étape 5 (relancer l’exécution du programme en tapant r, etc.).
  16. Pour quitter le déboggueur, tapez q (quit) ou fermez le buffer *gud-a.out* (activez ce buffer et choisissez Close dans le menu Files)

Remarques:

14  Optimisation

Avant de chercher des astuces d’optimisation, il importe de vérifier que l’algorithme utilisé a la bonne complexité. Par exemple un algorithme de tri en recherchant le maximum puis en recommençant dans le reste de la liste est en O(n 2)O(n^2), ce qui n’est pas optimal (O(nln(n))O(n\ln(n)) pour un tri fusion, avec tas...). Dans la suite, on suppose qu’on a la “bonne” complexité (à l’intérieur du grand O), et on essaie d’optimiser la valeur de la constante qui est cachée dans le OO.

On peut commencer par optimiser la vitesse d’un exécutable en compilant avec l’option -O2. Mais il est souvent possible de faire mieux en utilisant diverses astuces. Attention toutefois, il ne faut pas chercher à optimiser de cette manière un programme trop vite, car optimiser veut souvent dire écrire un code moins lisible et cela risque d’introduire des bugs. Avant de chercher à optimiser, il faut avoir un code bien testé, avec un certain nombre de tests de vérification faciles à exécuter (on parle de tests de régressions).

Pour optimiser, il faut regarder de plus près comment le code compilé fonctionne. Quelques exemples d’amélioration :

Un site de référence : le site d’Agner.

15  Quelques commandes utiles pour aller plus loin.

  

Ce document a été traduit de LATEX par HEVEA