Voici un algorithme pour calculer une approximation de :
<< Aller dans un pub, s'assurer qu'il contient bien un jeu de fléchettes et que la cible est un disque inscrit dans un carré, prier l'un des consommateurs de lancer des fléchettes n'importe où dans le carré, compter le nombre de fléchettes qui sont plantées dans le disque, et faire le quotient de ce nombre par le nombre total de fléchettes plantées dans le carré ; multiplier par 4 ce quotient ; retourner ce produit. >>
Figure: Calculer avec des fléchettes
Si vous ne disposez pas des ressources nécessaires à l'implémentation de
cet algorithme, vous pouvez recourir à un ordinateur et le programmer
comme suit ; vous devrez simuler le lancer de fléchettes par un tirage
de nombres aléatoires, et représenter le cadran supérieur droit du
disque de la cible par une fonction , avec
:
#include <stdio.h> #include <math.h> double f(double x) { /* x doit être compris entre -1 et 1 */ return sqrt(1 - x*x); } double calcul_pi(int n) { /* évalue PI par une méthode de Monte-Carlo */ int k = 0; int i; for (i=0; i<n; i++) { double u = drand48(); double v = drand48(); if (v <= f(u)) { k = k+1; } } return 4 * (double)k/n; } int main() { int N = 1000000; double pi = calcul_pi(N); printf("%6.5f\n", pi); return 0; }
Ce programme consiste en la définition de trois fonctions qui sont appelées f, calcul_pi et main. Ces fonctions en utilisent trois autres : f utilise sqrt, calcul_pi utilise drand48 et main utilise printf.
Ces trois autres fonctions, qui ne sont pas définies dans ce programme, sont déclarées dans les trois premières lignes : la fonction de génération de nombres pseudo-aléatoires, drand48, ainsi que la fonction << racine carrée >> sqrt, sont déclarées au moyen de #include <math.h>, et la fonction d'impression printf, au moyen de #include <stdio.h>.
Chaque définition de fonction a pour rôle d'introduire un nom (drand48, etc), de déclarer la façon de l'utiliser (c'est son en-tête), et enfin de dire ce qu'elle fait (c'est son corps, placé entre << { >> et << } >>). Examinons la définition de f :
double f(double x) { return sqrt(1 - x*x); }
L'en-tête de f est << double f(double x) >>. On y voit, outre f, deux autres noms, double et x : le premier est le nom d'un type de données, celui des nombres flottants en double précision, le second est celui d'un paramètre, qu'on retrouvera plus loin dans son corps. Cet en-tête déclare les conditions d'usage de la fonction : elle prend un argument de type double et donne un résultat de type double (on dit qu'elle retourne un double). C'est bien ainsi qu'elle est utilisée dans le corps de calcul_pi où l'on voit un appel << f(v) >>.
Le corps de f contient une seule instruction,
<< return sqrt(1 - x*x); >>, qui contient l'expression
<< sqrt(1 - x*x) >>, exprimant , laquelle est un
appel à la fonction sqrt ; l'argument de cet appel est
l'expression << 1 - x*x >>. Cette dernière expression est
formée à partir des opérateurs << - >> et << * >>, de
la constante 1 et du nom x.
Le texte compris entre << /* >> et << */ >> est un commentaire (ou remarque) : inutilisables par la machine, les commentaires facilitent la compréhension des programmes.
Examinons les deux autres en-têtes :
int main() { int N = 1000000; double pi = calcul_pi(N); printf("%6.5f\n", pi); return 0; }
Il commence par définir deux variables locales N
et pi ; la première est initialisée par la constante
1000000, la seconde par le résultat de l'appel <<
calcul_pi(N) >>. Puis il appelle la fonction printf
pour afficher à l'écran la valeur calculée de . Enfin, il retourne
0 (cette dernière valeur est entièrement conventionnelle et ne
concerne pas l'algorithme proprement dit).
Le corps de calcul_pi est un peu plus élaboré :
double calcul_pi(int n) { int k = 0; int i; for (i=0; i<n; i++) { double u = drand48(); double v = drand48(); if (v <= f(u)) { k = k+1; } } return 4 * (double)k/n; }
Après avoir défini deux variables, k et i, la première étant initialisée à zéro, il y a ensuite une instruction d'itération, qui débute par for, qui fait le gros du travail, puis un return. La valeur retournée est celle du produit de 4 par le résultat de la division de k, converti en flottant, par n.
Ce programme, écrit dans un fichier pub.c est compilé par gcc sur un 486-DX 66 sous Linux, à l'aide de la commande
unix% gcc -o pub pub.c -lm
Le programme exécutable, pub, est exécuté sur cette machine ;
on obtient 3.14138 comme estimation de , soit seulement
trois décimales exactes, après un million de << lancers >> (c'est le
int N = 1000000;) et en 11.41 secondes (la moitié de ce temps
est consacré aux appels des fonctions externes sqrt et de
rand48). Il y a heureusement des méthodes de calcul de
qui
sont bien meilleures
.