\documentclass[a4paper,11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}
\usepackage{makeidx}
\usepackage{graphicx}
\usepackage{ifpdf}
\ifpdf
 \usepackage[colorlinks,pdftex]{hyperref}
\else
 \usepackage[ps2pdf,breaklinks=true,colorlinks=true,linkcolor=red,citecolor=green]{hyperref}
\fi
\ifhevea
\else
\textheight 23 cm 
\textwidth 15cm
\topmargin -1.5 cm
\fi

\makeindex

% \renewcommand{\cuttingunit}{subsection} (add HEVEA after % for hacha)
\input{giacfr.tex}
\giacmathjax

\title{Programmation en C-- pour les maths}
\author{Bernard Parisse}
\begin{document}
\begin{giacjshere}
\maketitle

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, \verb|vector| pour les
tableaux de taille dynamique, \verb|string| pour les
chaines de caractère, la redéfinition des opérateurs et 
les templates).

\begin{center}
\includegraphics{progl3_qrcode.png}
\end{center}

\tableofcontents

\printindex

\section{Langage, programme et ordinateur}
Un ordinateur (au sens large du terme) est composé au minimum
d'un microprocesseur (CPU\index{CPU}\index{microprocesseur},
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\index{régistre}
(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\index{interpréteur}, soit on le fait globalement, avec
un compilateur\index{compilateur}.
Python, Javascript utilisent la première méthode,
C/C++, Pascal, Lisp, ... utilisent la deuxième méthode. 
%(Certains langages permettent de faire les deux, en compilant automatiquement 
%certaines parties d'un programme interprété.)

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é.

\section{Données, type, instructions, contrôle du flux d'exécution}
Les données\index{donnée}
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\index{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:
\begin{itemize}
\item  \verb|int|\index{int}, \verb|unsigned|\index{unsigned} qui sont des
  entiers\index{entier}
  signé ou non signé (en général sur 32 bits, mais pas toujours,
donc compris entre $-2^{31}$ et $2^{31}-1$ ou entre 0 et $2^{32}-1$),
des variantes comme \verb|long long|\index{long long} et
\verb|unsigned long long|
(en général sur 64 bits). Pour saisir une constante entière, on la tape
en base 10, ou avec le préfixe \verb|0x| en base 16, ou le préfixe 
\verb|0| en base 8, ou \verb|0b| en base 2. On utilise le suffixe \verb|LL|
pour un long long sur 64 bits et \verb|ULL| pour un entier long long 
non signé sur 64 bits.
\item
\verb|char|\index{char} qui permet de représenter sur 8 bits des caractères
(selon le format ASCII ou UTF8), un caractère peut se définir par
un entier (son code ASCII) ou être saisi entre deux \verb|'|
\item \verb|float|\index{float}, \verb|double|\index{double},
  \verb|long double|\index{long double}
qui permettent de représenter des nombres réels approchés en
virgule flottante (représentation en base 2).
Le type \verb|float| utilise 32 bits, 24 pour la mantisse (23
sont stockés, le 1 initial ne l'est pas), 1 bit de signe, 8 bits
pour l'exposant. Le type \verb|double| utilise 64 bits, 53 pour
la mantisse (52 stockés), 1 bit de signe, 11 bits pour l'exposant
(compris entre -1022 et 1023, les exposants -1023 et 1024 sont utilisés
pour représenter plus ou moins l'infini et un résultat indéfini NaN, 
not a number). Le type \verb|long double| est stocké sur 80 bits,
avec 64 bits de mantisse.
On entre en général un flottant en base 10 avec la notation
mantisse\verb|e|exposant, par exemple \verb|1.6e-19| signifie
$1.6\times 10^{-19}$ (le séparateur de la partie fractionnaire
est le point, pas la virgule).
Le suffixe \verb|f| indique un flottant, le
suffixe \verb|L| un long double.\\
Pour travailler avec des nombres
complexes\index{complexe, nombre}\index{nombre complexe}
en C++, on ajoute
\verb|#include<complex>| en début de fichier, puis on utilise
le type \verb|complex<double>|.
\item les pointeurs\index{pointeur}
  qui désignent des adresses en mémoire et servent
à représenter des tableaux de valeurs de même type stockés à des
adresses consécutives.
\item Astuce~: le compilateur reconnait le mot-clef \verb|auto|\index{auto}
qui lui dit de déterminer lui-même le type de la variable qui
suit. A utiliser avec précaution quand même, car il peut être par exemple
difficile de déterminer les limites de dépassement de capacité
d'un type entier qu'on n'a pas déclaré soi-même.
\end{itemize}

On déclare une ou plusieurs variables dans une instruction
en indiquant le type puis la ou les variables, par exemple\\
\verb|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.\\
\verb|a=2; b=3;|\\
\verb|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\index{constante}
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 \verb|const|\index{const} avant le type, par exemple\\
\verb|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 \verb|{| et \verb|}|,
sauf si le bloc ne contient qu'une instruction (qui se termine
alors par un \verb|;|).
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~:
\begin{itemize}
\item tests\index{test}\index{if}\index{else}~:\\
\verb|if (condition) bloc_vrai|\\
\verb|if (condition) bloc_vrai else bloc_faux|\\
\item boucles\index{boucle}\index{while}\index{for}~:\\
\verb|while (condition) bloc|\\
\verb|for (initialisation;condition;incrementation) bloc|\\
L'instruction \verb|break;|\index{break}
permet d'arrêter immédiatement une boucle,
alors que \verb|continue|\index{continue}
passe immédiatement à l'itération suivante.
Ces deux instructions s'utilisent en général dans un test.
\item appel de fonction\index{fonction}\index{return}\\
\verb|nom_fonction(argument1,argument2,...)|\\
Un appel de fonction se fait après avoir déclaré la fonction~:
\verb|type nom_fonction(type argument1, type argument2,...){|\\
\verb|  instructions | \\
\verb|  return valeur;|\\
\verb|}|\\
Ici \verb|valeur| est la valeur renvoyée lorsqu'on appelera la fonction.\\
Si \verb|return| est exécuté, on quitte immédiatement la fonction,
même si on est au milieu d'une boucle.\\
On peut déclarer une fonction (on déclare son prototype)
avant de la définir~:\\
\verb|type nom_fonction(type argument1, type argument2,...);|\\
\verb|...|\\
\verb|type nom_fonction(type argument1, type argument2,...){|\\
\verb|  ...|\\
\verb|}|\\
\end{itemize}
Le point d'entrée d'un programme est la fonction \verb|main|\index{main}
dont le prototype simplifié est\\
\verb|int main(){ ... }|\\
Il faut donc toujours définir une fonction main dans un programme C/C++.

{\bf Remarque pour utilisateur avancé uniquement}~:\\ 
Le prototype avancé de la fonction main est\\
\verb|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 \verb|argc| indique le nombre d'arguments en ligne de commande,
il vaut toujours au moins 1, \verb|argv[0]| est le nom du programme,
\verb|argv[1]| le premier argument, etc. Si les paramètres
sont des nombres, il faut les convertir en entier 
(\verb|atoi|, \verb|atol|, \verb|atoll| 
de \verb|#include <stdlib.h>|)
ou en double (\verb|atof|).
Par exemple pour passer une précision en argument optionnel,
on écrira dans \verb|main| \\
\verb|double eps=1e-10; if (argc>=2) eps=fabs(atof(argv[1]));|\\
et on appellera depuis le shell par exemple\\
\verb|./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 \verb|#include |\index{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 \verb|-lc -lm -lstdc++|. Le code 
d'initialisation du programme (chargement de la valeur des 
variables globales) est aussi en général automatiquement ajouté 
(\verb|crt*.o|, pour C-runtime).

\section{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\index{shell}
dans un terminal, un éditeur\index{éditeur} de texte et un compilateur. 
Si vous n'en connaissez pas, voici des suggestions pour le shell et le
compilateur~:
\begin{itemize}
\item Windows\index{Windows}: installer 
\ahref{https://www.mingw-w64.org/}{mingw} ou 
\ahref{https://www.cygwin.com/}{cygwin} comme shell, 
puis installez \verb|gcc g++ gdb| ou\\
\ahref{https://learn.microsoft.com/fr-fr/windows/wsl/install}{configurez WSL}
avec une distribution Linux et voir plus bas.
Il existe une version d'emacs pour Windows.
\item MacOS\index{MacOS}: repérer l'application Terminal (dans Accessoires~?)
pour le shell et installez \ahref{https://brew.sh/}{homebrew}
puis les outils de développement Mac, avec des commandes du type\\
\verb|brew install emacs|\\
Il existe plusieurs versions d'emacs pour MacOS, emacs, aquamacs, ...\\
Sur les Mac récents (processeurs M), je conseille 
plutôt d'installer le logiciel
de virtualisation \ahref{https://mac.getutm.app/}{UTM}
et une distribution Linux pour architecture arm64 pour bénéficier
du support du débuggueur gdb, le débuggueur du compilateur LLVM
(\verb|lldb|) n'est pas facilement interfaçable avec emacs.
\item Linux\index{Linux}: n'importe quelle application de terminal fera l'affaire
pour le shell (Konsole, xterm, etc.). 
Vérifiez que \verb|gcc g++ gdb| sont installés avec
le gestionnaire de package de votre distribution
\item Android\index{Android}: on peut travailler en mode console
en installant l'application 
\ahref{https://f-droid.org/fr/}{F-Droid} depuis un
navigateur, puis en installant Termux depuis F-Droid (attention
il ne faut pas installer Termux depuis Google Playstore!). Vous pouvez
ensuite installer le compilateur et emacs avec\\
\verb|pkg install build-essential emacs|\\
Ceci nécessite une maitrise d'emacs en mode console 
donc d'apprendre les raccourcis clavier d'emacs. Mais vous pouvez bien
sur utiliser un autre éditeur de programme.
\\
Alternative payante~: l'application Userland disponible sur le
Playstore permet d'installer une distribution Linux complète 
en mode texte et graphique, de manière conviviale,
mais elle n'est pas gratuite (prix octobre 2023: 2.29€)
\end{itemize}
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 \verb|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\\
\verb|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
\begin{verbatim}
#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;
}
\end{verbatim}
Explications: iostream\index{iostream}
est la bibliothèque qui gère les entrées-sorties
à la console, avec deux ``variables'' représentant la console en entrée
(\verb|std::cin|)\index{cin} et en sortie (\verb|std::cout|)\index{cout}
et les opérations \verb|<<| et \verb|>>|
qui dirigent dans le sens des flèches un ``flux'' de donnée
(variable de ou vers console). Le \verb|using namespace std;|
permet d'abréger la notation de ces deux variables. \verb|\n| est
utilisé pour représenter un retour à la ligne.

Puis sauvegardez et compilez~:\\
\verb|g++ prog.cc|\\
Pour l'exécuter, tapez \verb|./a.out| (Linux, Mac) ou \verb|./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\index{commandes Unix}\index{Unix, commandes}
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.
\begin{enumerate}
\item \verb|ls|: liste les fichiers et répertoire du répertoire courant.
\verb|ls -lt| permet d'afficher les fichiers par ordre de date du plus 
récent au plus ancien.
\item \verb|pwd|: chemin du répertoire courant
\item \verb|cd chemin|: déplace vers un autre répertoire (absolu
si \verb|chemin| commence par \verb|/|, relatif sinon)
\verb|cd| déplace vers le répertoire ``home''.
\item \verb|cp source cible| copie un fichier
\item \verb|mv source cible| déplace ou renomme un fichier
\item \verb|rm -i cible| efface un fichier (attention, l'effacement
est irréversible, l'option \verb|-i| demande une confirmation)
\item \verb|mkdir| et \verb|rmdir| permettent de créer un
répertoire ou de l'effacer si il est vide.
\item \verb|man nom_de_commande|: aide sur une commande
\end{enumerate}
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, 
\verb|*| remplace n'importe quelle chaine de caractères, \verb|?|
remplace n'importe quel caractère, ainsi \verb|ls -lt *.cc|
permet d'afficher tous les fichiers dont le nom termine par \verb|.cc|.
Ou \verb|grep double *.cc| va afficher toutes les lignes de code
source C++ contenant le mot \verb|double|.

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


Quelques raccourcis et astuces emacs\index{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. 
\begin{itemize}
\item la touche de tabulation permet d'indenter la ligne courante, Très
utile pour vérifier qu'on n'a pas fait d'erreur à une ligne précédente
ou pour réindenter un petit bloc de texte source
\item \verb|Ctrl-S| permet de chercher une chaine vers le bas, 
\verb|Ctrl-R| vers le haut.
\item \verb|Ctrl-X Ctrl-S| sauvegarde le fichier courant
\item \verb|Ctrl-X Ctrl-F| ouvre un nouveau fichier. On peut utiliser
la touche tabulation pour compléter un début de nom de fichier ou
la touche \verb|?| pour voir les complétions possibles.
\item \verb|Ctrl-|espace: marque un début de zone de sélection, 
\verb|Echap W|: place dans le presse-papier sans effacer, 
\verb|Ctrl W|~: efface et place dans le presse-papier.
\item \verb|Ctrl-X 2| ou menu File New window below 
permet de couper la fenêtre en deux pour avoir
deux vues sur son code source ou voir deux fichiers simultanément
\item \verb|Ctrl-X 1| ou menu File Remove other windows
permet de rétablir une seule fenêtre
\item à faire une fois~:
créez un fichier \verb|~/.emacs| contenant
\begin{verbatim}
(setq inhibit-splash-screen t)
(show-paren-mode t)  
\end{verbatim}
ceci affiche directement emacs en mode 1 fenêtre et active le
parenthese-match qui permet de visualiser facilement les blocs
de programme, début/fin d'appels de fonctions, conditions, etc.
Vous pouvez rajouter des définitions de raccourcis clavier dans ce fichier
par exemple j'utilise \verb|(global-set-key "\C-g" 'goto-line)|
pour pouvoir changer de ligne avec Control G).
\end{itemize}

\section{Tableaux}\index{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 \verb|char *| est un type pointeur sur une adresse mémoire
contenant un caractère. Le contenu d'une adresse se note alors 
\verb|*pointeur|. L'adresse d'une variable se note 
\verb|&nom_variable|. Ainsi \\
\verb|char ch='a'; char * ptr=&ch; cout << *ptr;|\\
est une manière compliquée d'afficher un \verb|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:\\
\verb|type nom_variable[nombre_elements];|\\
et on lui donne souvent une valeur.
Par exemple \verb|char chaine[16]="bonjour";| déclare
une variable \verb|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\\
\verb|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 \verb|{}| et séparés par des virgules,
par exemple\\
\verb|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 \verb|chaine[0]| vaut
le caractère \verb|'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'' \verb|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 \verb|#include <vector>| au début
du fichier source.

Un tableau C++\index{tableau C++}\index{vector}
se définit donc comme un \verb|vector<type>|, par
exemple \verb|vector<double> P(5);| définit une variable \verb|P|
qui est un tableau de \verb|double|. Ici \verb|P| possède 5
éléments (initialisés à 0), mais on peut en ajouter ou en enlever
à l'aide de deux {\em 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 \verb|.|
puis par le nom de méthode et ses éventuels arguments explicites.
Ainsi \verb|P.pop_back();|  supprime le dernier élément de \verb|P|.
Ou \verb|P.push_back(1);| ajoute un 1 à la fin de \verb|P|.

Instructions fréquemment utilisées avec \verb|vector|~:
\begin{itemize}
\item initialisation \verb|vector<T> v={valeur1, ...};| où
les valeurs sont de type \verb|T|
\item \verb|v[k]|~: accès en lecture/écriture
à l'élement d'indice $k$ compris entre
0 et la taille du vecteur moins 1, en temps $O(1)$
\item \verb|v.push_back(t);|~: ajoute un élément, en temps $O(1)$ s'il
n'est pas nécessaire de réallouer le vecteur
\item \verb|v.pop_back();|~: supprime le dernier élément en temps $O(1)$
\item \verb|v.size()|~: taille du vecteur. La capacité du vecteur 
(nombre d'éléments réservés en mémoire)
s'obtient avec \verb|v.capacity()|. On peut l'augmenter 
avec \verb|v.reserve(n)|.
\item \verb|v.insert(v.begin()+k,valeur);| ajoute en temps $O(n)$ 
un élément en position $k$
\item \verb|v.erase(v.begin()+k);| efface en temps $O(n)$ l'élément
  situé en position $k$.
\item \verb|sort(v.begin(),v.end())| trie le vecteur par ordre
  croissant. Il faut ajouter en début de fichier
  \verb|#include <algorithm>| 
\end{itemize}

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

Enfin, il est possible de créer des ``annuaires'' ou
dictionnaires\index{dictionnaire},
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
\verb|#include <map>|\index{map}, puis pour déclarer
par exemple un annuaire
(tableau indicié par une chaine de caractères et de valeur un entier)\\
\verb|map<string,int> annuaire;|\\
on peut ensuite créer une entrée avec
\verb|annuaire["Gaston"]=612345678;|. Pour lire une valeur
existante, on utilisera par exemple\\
\verb|cout << annuaire["Gaston"] << endl;|\\
Pour savoir si une entrée existe\\
\begin{verbatim}
auto itend=annuaire.end(),it=annuaire.find("Gaston"); 
if (it!=itend){
  cout << it->first << ":" << it->second;
}
\end{verbatim}
Les accès/recherche se font en temps $O(\ln(n))$ s'il y a $n$ entrées.

\section{Fonctions}
Les arguments peuvent être passés à une fonction de trois manières~
\begin{itemize}
\item par valeur~: la valeur de l'argument est recopiée dans une
variable locale à la fonction, la variable locale peut être modifiée,
cela n'affecte pas la valeur d'une variable passée en argument.
La copie peut être couteuse en temps et en mémoire si la donnée occupe
beaucoup de mémoire. Déclaration \verb|type argument|
\item par référence\index{référence}~:
  l'adresse de la variable passée en argument
est passée à la fonction avec un nom de variable local à la fonction.
Toute modification de la valeur dans la fonction se répercute automatiquement
à la variable passée en argument. 
Déclaration par \verb|type & argument|
\item par référence constante~: c'est une variante du cas précédent
pour passer un paramètre non modifiable à la fonction, le
compilateur vérifie que la variable n'est pas modifiée.
Déclaration par \verb|const type & argument|
\end{itemize}
Par exemple pour faire le produit scalaire de deux vecteurs, on écrira\\
\verb|vector<double> dot(const vector<double> & v,const vecteur<double>& w);|\\
Pour calculer les coefficients de Bézout de deux entiers, on peut écrire\\
\verb|int extgcd(int a,int b,int & u,int &v);|\\
la fonction renvoie le PGCD $d$ de $a$ et $b$ et modifie la valeur des variables
\verb|u| et \verb|v| pour que $au+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
\verb|typedef|\index{typedef}
pour lui donner un nom. Par exemple si on écrit\\
\verb|typedef double fcn1(double);|\\
alors \verb|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\\
\verb|double dicho(fcn1 f,double a,double b);|

\section{Entrées/sorties}\index{entrée}\index{sortie}
La biblithèque C++ définit des flux\index{flux}
d'entrées/sorties standard \verb|cin|\index{cin}
pour la console, \verb|cout|\index{cout}
et \verb|cerr|\index{cerr} pour les sorties console
et console d'erreur (qui peuvent être distinctes en cas de redirection
des sorties vers un fichier avec \verb|>| lorsqu'on appelle le programme
de ligne de commande). Il faut utiliser \verb|#include <iostream>|
pour y accéder. Les opérateurs \verb|>>| et \verb|<<| sont alors
définis pour les types de base vers un flux de sortie \verb|ostream|
ou depuis un flux d'entrée \verb|istream|.
Cela fonctionne aussi pour le type \verb|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 \verb|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.
\begin{verbatim}
#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;
}
\end{verbatim}

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
\verb|#include <fstream>| puis on déclare un fichier en lecture
par \verb|ifstream nom_variable("nom_fichier");| et en écriture par
\verb|ofstream nom_variable("nom_fichier");|, par exemple
\begin{verbatim}
vector<double> v={1/3.0,2.3};
ofstream fich("v.txt");
fich << v << endl;
\end{verbatim}

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

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

\section{Algorithme et types, modèles (template)}\index{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 \verb|typedef|\index{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
\begin{verbatim}
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);
\end{verbatim}
Il y aura deux fonctions gcd, une pour des int (de taille inférieure
à $2^{31})$ et l'autre pour des longlong (de taille jusque $2^{63}$).

Ce mécanisme s'applique également à la définition d'opérateurs, ainsi on peut
utiliser
\begin{verbatim}
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;
}
\end{verbatim}
et cela fonctionnera pour des \verb|vector<int>| comme pour
des \verb|vector<double>|.
Et cela fonctionnera aussi pour des \verb|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 \verb|%| et l'opérateur \verb|!=| est défini,
on peut alors utiliser la fonction paramétrique \verb|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.

\section{Précautions à prendre avec les types flottants.}\index{flottants, précautions}
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|<\varepsilon$ \verb|fabs(b-a)<eps|)
ou relative ($|b/a-1|<\varepsilon$ \verb|fabs(b/a-1)<eps|,
attention si $a=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_\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_-=\frac{c}{a}$$
C'est aussi pour cette raison que la librairie mathématique
possède une fonction \verb|expm1| (valeur plus précise
de $e^x-1$ pour $x$ petit)
et une fonction \verb|log1p| (valeur précise de $\ln(x+1)$
pour $x$ 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~:
\ahref{https://www-fourier.univ-grenoble-alpes.fr/\home{parisse}/info/erreur2.cc}{erreur2.cc}
On peut d'ailleurs améliorer la
précision en calculant un terme de correction au fur et à mesure
de la boucle.

\section{Types structurés}\index{struct}
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 \verb|int|. Plutot que de passer deux arguments pour
travailler sur un rationnel, on définit une structure
avec plusieurs membres, par exemple\\
\verb|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 \verb|.| et du nom du membre\\
\verb|rationnel q={2,3}; cout << q.num << "/" << q.den;|

On peut ensuite définir des fonctions prenant en argument des
\verb|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
\begin{verbatim}
rationnel operator * (const rationnel & a,const rationnel & b){
  rationnel res={a.num*b.num,a.den*b.den};
  return res;
}
\end{verbatim}
On peut simplifier un peu l'écriture ci-dessous en utilisant
un constructeur\index{constructeur},
à définir lors de la déclaration de rationnel
\begin{verbatim}
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);
}
\end{verbatim}

On observe que nos fractions ne sont pas réduites, on peut ajouter 
une simplification par le pgcd dans le constructeur
\begin{verbatim}
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;
    }
  }
};
\end{verbatim}
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 \verb|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.

\section{Gestion des erreurs d'exécution prévisibles.} \index{exception} 
\index{runtime error}
Lorsqu'on rencontre une erreur, on peut décider de mettre
fin au programme immédiatement en appelant \verb|exit(n);| où
$n$ est un entier, cela revient à stopper le programme
comme si on exécutait \verb|return n;| dans la fonction \verb|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 \verb|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
\verb|#include <stdexcept>|\\
Pour générer une erreur on utilise \verb|throw|, pour gérer 
une erreur on utilise un bloc\\
\verb|try { } catch (exception){ }|\\
Par exemple
\begin{verbatim}
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;
}
\end{verbatim}

\section{Compilation, Makefile}
Quelques options\index{compilateur, options}\index{options}
importantes du compilateur:
\begin{itemize}
\item \verb|-g| génère les informations de mise au point, pour exécution
en pas à pas avec gdb, voir section \ref{sec:gdb}.
\item \verb|-Wall| affiche tous les avertissements (all warnings)
\item \verb|-o| nom du fichier généré s'il est différent du nom
choisi par défaut
\item \verb|-O2| ou \verb|-O3| optimisation en vitesse d'exécution
\item \verb|-Os| optimisation de la taille de l'exécutable (à utiliser
pour des architectures où c'est important, par exemple calculatrices)
\item \verb|-c|, compile un fichier en un fichier objet,
sans générer d'exécutable, cf. ci-dessous.
\item \verb|-Ichemin|, indique un répertoire pour y chercher des fichiers
de déclarations (\verb|#include|), et \verb|-Lchemin| indique
un répertoire pour y chercher des bibliothèques.
\end{itemize}

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 \verb|.h| (comme header)\index{header}
qui reprend uniquement les déclarations, par exemple ici on pourrait
l'appeler \verb|QQ.h| ou \verb|rationnel.h|. On aura alors
un fichier \verb|rationnel.cc| (ou \verb|QQ.cc|) contenant
les implémentations des fonctions. Et un autre couple de fichiers
\verb|poly.cc/.h| pour les polynômes.

L'option \verb|-c| du compilateur \verb|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 \verb|.o| en argument lors de la compilation du fichier
contenant la fonction \verb|main|.

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

Si on modifie une fonctionnalité des polynômes, on édite \verb|poly.cc|
et on le recompile, il n'est pas nécessaire de recompiler 
\verb|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 \verb|make|
qui contient dans un fichier nommé \verb|Makefile|\index{Makefile}
les commandes
nécessaires, organisés en cible à créer, dépendances, commande pour
créer une cible avec des dépendances. \verb|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)
\begin{verbatim}
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
\end{verbatim}

Il est possible de regrouper plusieurs fichiers objets d'extension
\verb|.o| en une bibliothèque\index{bibliothèque}\index{library}
(statique) d'extension \verb|.a| 
avec les commandes \verb|ar| (pour archive) et \verb|ranlib|, par exemple\\
\verb|ar cru libpolyrat.a poly.o rationnel.o|\\
\verb|ranlib libpolyrat.a|\\
On passe ensuite l'argument \verb|-lpolyrat| au lieu de
\verb|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 \verb|-Lchemin|. Si les fichiers d'en-tête
de la librairie ne sont pas dans le répertoire courant, il faut
ajouter l'option \verb|-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 \verb|.so| (linux/mac)
ou \verb|.dll| (windows) en compilant
les fichiers objets avec l'option \verb|-shared|. Il peut être
nécessaire d'indiquer où se trouve une librairie dynamique, sous Linux
cela se fait avec la commande\\
\verb|export LD_LIBRARY_PATH = chemin1;chemin2;|\_
ou pour l'utilisateur \verb|root|
en éditant le fichier \verb|/etc/ld.so.conf| et en exécutant
la commande \verb|ldconfig|.

\section{Pour vos projets}
\subsection{Aléatoire}\index{rand}\index{srand}\index{générateur aléatoire}\index{aléatoire, générateur}
La fonction \verb|rand()| renvoie un nombre entier pseudo-aléatoire
compris entre 0 et la constante \verb|RAND_MAX|. Pour avoir un
réel uniformément entre 0 et 1, on utilisera \verb|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 \verb|srand(int)|, par exemple
\verb|srand(time(NULL))|

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

\subsection{Interpréteur d'expression}
\ahref{https://github.com/codeplea/tinyexpr}{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 
\ahref{https://www-fourier.univ-grenoble-alpes.fr/\home{parisse}/info/tinyexpr.c}{tinyexpr.c} et \ahref{https://www-fourier.univ-grenoble-alpes.fr/\home{parisse}/info/tinyexpr.h}{tinyexpr.h} 
et de compiler \verb|tinyexpr.c| par la commande\\
\verb|gcc -c tinyexpr.c|\\
Voici un programme d'illustration de son usage, qui prend en ligne de commande
une expression de deux variables $x$ et $y$ entre deux ", et l'évalue 
pour $x$ et $y$ 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)$.
\begin{verbatim}
// -*- 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;
}
\end{verbatim}

\subsection{Entiers et flottants multiprécisions}
Pour travailler avec des entiers ou des flottants
sans limitation de taille autre que
la mémoire disponible 
\ahref{https://gmplib.org/}{entiers avec GMP}, 
\ahref{https://www.mpfr.org/}{flottants avec MPFR},
\ahref{https://gitlab.inria.fr/mpfi/mpfi}{arithmétique d'intervalles avec MPFI}

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

Par exemple
\begin{verbatim}
#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;
}
\end{verbatim}

\subsection{Graphiques} \label{sec:sdl}
La bibliothèque
\ahref{https://www.libsdl.org/}{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)\\
\verb|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 
\ahref{https://www-fourier.univ-grenoble-alpes.fr/\home{parisse}/info/emsdl2.cc}{emsdl2.cc}. \`A compiler avec \verb|g++ emsdl2.cc -lSDL2|

Un exemple de source SDL1 utilisable sur PC mais aussi pour navigateur  
\ahref{https://www-fourier.univ-grenoble-alpes.fr/\home{parisse}/info/emsdl1.cc}{emsdl1.cc} avec des versions anciennes de emscripten. 
\`A compiler avec \verb|g++ emsdl.cc -lSDL| (PC)
ou avec \verb|emcc emsdl1.cc -s SINGLE_FILE -o a.html| 
(emscripten version 1.x).

En C++, on peut aussi utiliser la librairie 
\ahref{https://www.sfml-dev.org/tutorials/2.6/start-linux-fr.php}{SFML} 
qui s'installe sous Linux Debian
compatible avec \verb|sudo apt install libsfml-dev|.

\subsection{3d}
La librairie OpenGL permet de faire du rendu de scène en 3d. En association
avec \ahref{https://freeglut.sourceforge.net/}{freeGLUT}, 
on peut faire des programmes interactifs 3d. Installation sur Linux
debian via le package \verb|freeglut3-dev|.
Des \ahref{https://cs.lmu.edu/~ray/notes/openglexamples/}{exemples} 
de code source dont on peut s'inspirer, à compiler avec l'option
\verb|-lGL -lglut -lGLU|

\subsection{Calcul symbolique}
La librairie
\ahref{https://www-fourier.univ-grenoble-alpes.fr/\home{parisse}/giac_compile_fr.html}{Giac} permet de faire du calcul symbolique et polynomial
en C/C++. Voici un
\ahref{https://www-fourier.univ-grenoble-alpes.fr/\home{parisse}/info/example_giac.cc}{example}.

\subsection{Créer un exécutable utilisable dans un navigateur}
\ahref{https://emscripten.org/}{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 \ref{sec:sdl}.

\subsection{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)
\begin{itemize}
\item
  Casio est le plus ouvert, on peut compiler des applications
additionnelles (addins) sur les Graph 35 et 90  avec
\ahref{https://www.planet-casio.com/Fr/forums/topic14914-1-tutoriels-dutilisation-de-gint.html}{gint}
  ou le \ahref{https://prizm.cemetech.net/Prizm_User_Portal/}{Casio SDK}
et gcc pour processeur 32 bits sh3/sh4
\item
TI est nettement moins ouvert. Il est possible de compiler du C/C++ pour
les \ahref{https://github.com/CE-Programming/toolchain}{TI83/84} 
(gcc pour processeur ez80 8bits étendu à 24) et pour des
  TI Nspire pas trop récentes, jailbreakées avec 
\ahref{https://ndless.me/}{ndless} (compilateur gcc ARM 32 bits)
\item Numworks (N0120, N0115, N0110 verrouillées):
  il existe un \ahref{https://github.com/numworks/epsilon-sample-app-c}{kit de développement officiel}, mais il est très
  incomplet, nécessite de passer par le site du constructeur
  et les applications sont désactivées au moindre reset/crash.\\
Si votre calculatrice est une N0110 non verrouillée ou une N0100, vous
pouvez compiler non seulement un programme, mais un OS complet (firmware).
Le compilateur est gcc pour ARM 32 bits.
\end{itemize}

\section{Mise au point} 
\label{sec:gdb} \index{bug} \index{debug} \index{gdb}
\index{SEGFAULT}
Lorsqu'un programme ne fonctionne pas comme pr\'evu, on peut souvent
d\'etecter des erreurs en l'ex\'ecutant en pas-\`a-pas (une ligne
de code apr\`es l'autre) et en examinant l'\'evolution du contenu
des variables. L'application qui permet de faire cela s'appelle un
d\'eboggueur (pour des erreurs d'allocation m\'emoire,
on utilisera plut\^ot un logiciel sp\'ecialis\'e comme 
\ahref{https://valgrind.org/}{valgrind}). 
Plusieurs interfaces existent, on pr\'esente ici  
\verb|gdb| sous \verb|emacs|
qui s'ex\'ecute dans
l'environnement d'\'edition du texte source.
\begin{enumerate}
\item Utilisez l'option \verb|-g| lorsque vous compilez
(pour utiliser le menu Compile d'emacs, modifiez la premi\`ere ligne du texte source comme par exemple:\\
\verb|// -*- mode:C++; compile-command:"g++ -g -Wall essai.cc" -*-|)
\item Compilez le programme, on suppose dans la suite que le programme
compil\'e s'appelle \verb|a.out| ce qui est le cas par d\'efaut
\item Dans \verb|emacs|, s\'electionnez Debugger (GDB) dans le menu Tools
(ou tapez sur la touche \verb|Echap|, vous devez voir
apparaitre \verb|ESC-| au bout de quelques secondes, puis selon
la version d'emacs tapez \verb|xgud-gdb| ou \verb|xgdb|
et la touche \verb|Entree|). Vous devez alors voir dans la ligne d'\'etat
en bas:\\
\verb|Run gdb (like this): gdb a.out|\\
Modifiez si n\'ecessaire puis tapez \verb|Entree|. Le deboggueur est activ\'e.
\item Pour visualiser \`a la fois le source du programme et le
d\'ebbugueur, il peut \^etre n\'ecessaire de couper la fen\^etre
en deux (menu File-$>$Split Window ou raccourci clavier Ctrl-X 2),
et dans l'une des parties de s\'electionner le source (menu Buffers
ou raccourci Ctrl-X o).
\item L'\'etape suivante consiste \`a mettre un {\em point d'arr\^et}\/ 
pr\`es de l'endroit o\`u vous suspectez qu'il y a une erreur (par exemple
au d\'ebut d'une fonction suspecte). Il y a deux
m\'ethodes, soit en donnant le nom de la routine, par exemple pour le
programme principal \verb|main|:\\
\verb|b main|\\
soit dans le code source, en cliquant \`a gauche de la ligne ou
en tapant \verb|Ctrl-X| puis \verb|Ctrl-A| puis \verb|Ctrl-B|
\`a la ligne souhait\'ee. 
On peut aussi taper \verb|b|
suivi par le num\'ero de ligne dans le fichier source 
(ou \verb|b nom_ficher:numero_ligne|). 
Vous pouvez mettre plusieurs points d'arr\^et.
\item Puis on lance l'ex\'ecution du programme en cliquant sur Go ou
en tapant \verb|r| (pour run)
\item Le programme s'ex\'ecute normalement jusqu'\`a ce qu'il atteigne
le point d'arr\^et. On peut alors visualiser le contenu d'une variable
en utilisant l'instruction \verb|p| suivi du nom de variable (p pour print), par exemple:\\
\verb|p modulo| puis touche \verb|Entree|\\
imprime le contenu de la variable \verb|modulo| (si elle existe).
\item L'instruction \verb|n| (next) ex\'ecute la ligne courante.
Pour ex\'ecuter ensuite plusieurs lignes \`a la suite, on tape plusieurs
fois sur la touche Entree. On peut aussi indiquer un param\`tre
num\'erique \`a la commande \verb|n|.
\item L'instruction \verb|s| (step in) permet de rentrer \`a l'int\'erieur
d'une fonction si la ligne courante doit ex\'ecuter cette fonction (alors
que \verb|n| ex\'ecute cette fonction en un seul pas, sauf si cette
fonction contient un point d'arr\^et)
\item L'instruction \verb|u| (until) ex\'ecute le programme sans arr\^et
jusqu'\`a ce que la ligne de code source suivante soit atteinte (ou une
adresse donn\'e en param\`etre). C'est
particuli\`erement int\'eressant pour sauter au-del\`a d'une boucle.
\item L'instruction \verb|c| (continue) permet de continuer l'ex\'ecution
jusqu'au prochain point d'arr\^et. On peut aussi indiquer un param\`etre
pour ignorer le point d'arr\^et un certain nombre de fois.
\item \verb|kill| permet de stopper
le programme en cours, 
\item \verb|d| permet de d\'etruire un point d'arr\^et (on donne alors
son num\'ero) ou tous les points d'arr\^et. On peut aussi temporairement
d\'esactiver ou r\'eactiver un point d'arr\^et 
(commandes \verb|disable| et \verb|enable|)
\item \verb|f 0|, \verb|f 1|, etc. permet de visualiser la
fonction appelante \`a l'ordre demand\'e, l'ordre est calcul\'e 
depuis la fonction interrompue
(0 pour la fonction actuelle, 1 pour la 1\`ere appelante, etc.),
ainsi que les variables de cette fonction. Cette commande peut
d'ailleurs \^etre utilis\'ee en cas de Segmentation fault sans mettre
de point d'arr\^et au pr\'ealable.
\item Vous pouvez corriger une erreur dans la fen\^etre d'\'edition,
recompiler le programme et revenir dans la fen\^etre \verb|gdb|
(c'est le buffer nomm\'e \verb|*gud-a.out*|) puis reprenez
ce mode d'emploi \`a l'\'etape 5
(relancer l'ex\'ecution du programme en tapant \verb|r|, etc.).
\item Pour quitter le d\'eboggueur, tapez \verb|q| (quit)
ou fermez le buffer \verb|*gud-a.out*| 
(activez ce buffer et choisissez \verb|Close|
dans le menu \verb|Files|)
\end{enumerate}

Remarques: 
\begin{itemize}
\item Les variables de type structur\'e ou les classes
s'affichent comme des structures C, m\^eme si vous avez red\'efini
l'op\'erateur \verb|<<|. Pour afficher une variable de ce type,
il est judicieux de pr\'evoir une m\'ethode:\\
\verb|void dbgprint() const { cout << *this << endl; }|\\
On peut alors visualiser une variable \verb|x| du type consid\'er\'e
en tapant\\ 
\verb|print x.dbgprint()|\\
Pour automatiser tout cela,
cr\'eez un fichier nomm\'e \verb|.gdbinit| et contenant\\
\verb|echo Defining v as print command for class types\n|\\
\verb|define v|\\
\verb|print ($arg0).dbgprint()|\\
\verb|end|\\
Dans la session \verb|gdb|, tapez \verb|v x| pour visualiser le contenu
de la variable \verb|x|.
\item Parmi les autres possibilit\'es int\'eressantes de gdb, il y a la 
modification du contenu d'une variable en cours
d'ex\'ecution (commande \verb|print variable=valeur|)
On peut aussi interrompre
le programme seulement si une condition est v\'erifi\'ee
(\verb|break .. if ..|).
\item Pour plus d'informations, vous pouvez taper \verb|help| dans la fen\^etre
du debuggueur pour obtenir l'aide en ligne ou \`a tout moment dans
\verb|emacs|, en tapant \verb|Ctrl-H I|, puis
\verb|Ctrl-S gdb| puis clic de la souris avec le bouton du milieu sur
\verb|gdb|.
\end{itemize}


\section{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)$, ce qui n'est pas optimal ($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 $O$.

On peut commencer par optimiser la vitesse d'un exécutable
en compilant avec l'option \verb|-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~:
\begin{itemize}
\item Eviter le plus possible les divisions. Par exemple
  si on additionne plusieurs entiers modulo un nombre premier
  $p$, au lieu de faire\\
  \verb|s=(a+b)%p; s=(s+c)%p;|\\
  faire \verb|s=(a+b+c)%p;|\\
  Mais il faut prendre garde au dépassement de taille maximale.
%% Pour faire de l'algèbre linéaire modulo $p$ où $p$ tient sur 31 bits,
%% on pourra utiliser une matrice d'entiers 64 bits, et représenter par
%% des entiers entre 0 et $p^2$. A chaque opération de combinaison linéaire
%% de lignes $L_i$ et $L_k$, on effectue $L_i[j]+\alpha L_k[j]$ 
%% où $\alpha$ est l'opposé de l'inverse du pivot. 
\item dans certaines situations, on peut remplacer un test par
  d'autres opérations. Par exemple ci-dessus, si $a$ et $b$ sont
  compris entre 0 et $p$, on pourrait calculer \verb|s=(a+b)%p|
  en faisant un test\\
  \verb|s=a+(b-p); if (s<0) s+=p;|\\
  Il sera plus rapide, si $s$ est un entier 32 bits signé, de faire\\
  \verb| s=a+(b-p); s += (s>>31)&p;|\\
  Explication: on retranche $p$ à $s$ ce qui donne un entier entre
  $-p$ et $p$. S'il est positif, il faut le laisser tel quel, s'il
  est négatif il faut lui ajouter $p$. C'est ce que fait la
  deuxième instruction avec le décalage de bits de 31 positions
  qui renvoie 0 (si $s$ était positif ou nul) ou un entier dont tous les
  bits sont à 1 (si $s$ était négatif) et le \verb|&|
  bit à bit avec $p$ renverra respectivement 0 ou $p$.
\item Certains tests sont implicites, par exemple dans des
  boucles. On peut tenter de ``dérouler'' une boucle en écrivant
  plusieurs fois le corps de la boucle, on évite ainsi une partie des
  tests de fin de boucle et des branchements. Le compilateur
  fait d'ailleurs cela automatiquement avec l'option d'optimisation
  mais si on le fait manuellement on peut souvent mieux gérer
  le déroulé.
\item on essaie souvent d'optimiser le nombre d'opérations
  arithmétiques à effectuer. Mais sur les architectures
  actuelles, le temps d'accès à la mémoire est le plus souvent
  prépondérant. Il faut donc chercher à optimiser les lectures/
  écritures, en particulier dans de grands tableaux (représentant
  par exemple des matrices). D'abord en utilisant des types de données
  de taille pas plus grande que ce qui est nécessaire, ensuite
  en faisant des accès localisés dans le tableau, enfin
  en réutilisant les données qui peuvent l'être.
  Par exemple, pour faire le produit de deux matrices,
  travailler par bloc sera intéressant dès que la taille
  d'un bloc permet de travailler avec moins que la taille
  du cache L1 du microprocesseur. Et calculer simultanément
  un nombre fixe d'éléments de la matrice produit (par
  exemple 4 éléments à la fois sur une même ligne) en lisant
  une seule fois les valeurs de la ligne de la première matrice.
\end{itemize}
Un site de
référence : \ahref{https://www.agner.org/optimize/}{le site d'Agner}.

\section{Quelques commandes utiles pour aller plus loin.}
\begin{itemize}
\item \verb|grep mot *|\\
Lister tous les fichiers contenant \verb|mot|
\item \verb|grep -c mot *.cc|\\
compter le nombre d'occurences de mot dans les fichiers d'extension \verb|.cc|
\item \verb|find rep -name '*bla*.cc' -print|\\
cherche récursivement dans le répertoire \verb|rep| les fichiers
dont le nom contient \verb|bla| et termine par \verb|.cc|
\item \verb|zip archive.zip *.cc *.h|\\
archiver les fichiers d'extension \verb|.cc| et \verb|.h|.
La commande de désarchivage est \verb|unzip|.
Les archives au format \verb|tar| utilisent la commande 
\verb|tar cvfz archive.tgz liste_fichiers| 
ou \verb|tar cvfj archive.tar.bz2 liste_fichiers|
pour archiver et 
\verb|tar xvfa nom_archive|  pour désarchiver
(remplacer \verb|a| par \verb|z| ou \verb|j| sur Mac OS).
\item
\begin{verbatim}
grep -l 'mot' *.h | xargs sed -i 's/mot/remplacement/g'
\end{verbatim}
Remplacer un mot par un autre dans tous les fichiers d'extension \verb|.h|
\item 
\begin{verbatim}
grep -rl 'mot' * | xargs sed -i 's/mot/remplacement/g'
\end{verbatim}
Même chose mais dans tous les fichiers récursivement
\item 
\verb|git clone url|\\
permet de créer une copie locale d'un projet utilisant git 
depuis l'URL \verb|url|. Utiliser \verb|git clone -b branche url| 
pour récupérer une branche particulière.
\end{itemize}
\end{giacjshere}
\end{document}
