Suite géométrique

Création d'un tableau

L'objectif de cet algorithme est de construire une suite géométrique sur une machine. Nous voulons enregistrer chaque terme, bien sûr pour des raisons de limitations techniques il est impossible de tous les conserver, une suite devient une liste dans la mémoire d'un ordinateur. Choisissons pour notre exemple une liste de taille 11, c'est-à-dire pouvant accueillir 11 valeurs.

Le type de cette donnée est appelé tableau. Comme pour un nombre, il suffit de procéder à une affectation pour le créer, à ceci près qu'il faut préciser sa taille et pour certains langages le préremplir. Nous évitons ces détails et conservons uniquement la notion de taille.

Soit $u$ une suite géométrique de raison $q$ et de premier terme $u_0$ pour réutiliser les notations du chapitre 3. Le terme $u_i$ sera donc la case $u[i]$ dans le tableau, en particulier certains langages demandent aussi à indiquer la valeur du premier indice. On peut très bien le choisir nul comme dans notre cas, ou 1, ou même n'importe quel entier relatif. Les autres indices du tableau sont alors définis en fonction du premier. Un tableau à 11 entrées de premier indice 0 sera de la forme: \[ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline \\ u_0 & u_1 & u_2 & u_3 & u_4 & u_5 & u_6 & u_7 & u_8 & u_9 & u_{10} \\ \hline \end{array} \] avec des nombres à la place de chaque terme $u_i$. Reste à savoir quelle place mémoire est accordée aux nombres dans le langage utilisé. L'un des plus connus, le langage C consacre de base aux entiers 32 bits d'information. C'est-à-dire 32 cases pour loger un chiffre binaire (0 ou 1) dans chacune d'elles.

Remarque

Avant de proposer quelques résolutions, nous faisons remarquer qu'il s'agit avant tout ici de mettre en évidence l'importance de la complexité dans un algorithme. Deux méthodes aboutissant au même résultat peuvent ne pas avoir la même efficacité. La gestion du calcul et de la mémoire est primordiale, l'exposé cherche avant tout à montrer comment il peut être astucieux de réutiliser un calcul, et comment gérer sa mémoire pour en utiliser le moins possible.

Résolution basique

Présentation

Nous appelons $G$ la fonction qui prend en argument un nombre réel (décimal pour la machine) noté $a$ et un autre réel $q$ pour renvoyer un tableau à 11 compartiments représentant les termes de la suite géométrique $u$ de premier terme $a$ et de raison $q$. La fonction créant un tableau sera notée Tab$(L)(p)$ où $L$ est la taille, $p$ l'indice du premier terme. On suppose qu'elle remplit le tableau avec le nombre 0 par défaut.

La manière forte consisterait à utiliser la formule explicite de la propriété 3.3 du cours. Elle a la même structure pour tout $i$ variant de 0 à 10, il suffit simplement de faire varier l'indice pour exprimer chacun des termes. Ce qui demande une boucle de type: Pour $i$ de 0 à 10 Faire (...) FinPour. Soit l'algorithme:

$G(a,q)$

$u \leftarrow \text{Tab}(11)(0)$

Pour $i$ de 0 à 10 Faire

$u[i] \leftarrow a \times q^{i}$

FinPour

Afficher $u$

Opérations élémentaires

L'algorithme démarre sur la création d'un tableau, il ne nous sera pas possible d'améliorer ceci puisque nous devons renvoyer un tableau, au mieux s'il existe une option permettant de préremplir l'ensemble des mêmes cases par une autre valeur que zéro par défaut, alors nous pouvons choisir de placer le terme $a$ partout et ainsi débuter les opérations sur $u[1]$.

Pour $u[0]$ il est effectué une affectation directe, nous ne tenons pas compte ni de l'opération $q^0$ ni de $(a\times 1)$

Pour $u[1]$ la recherche de $q^1$ est directe, ne nécessite aucune opération et $a\times q$ vaut pour une multiplication.

Pour $u[5]$ nous devons calculer $q^5=q\times q\times q\times q\times q$. Le processus enclenché calculera dans un premier temps $(q\times q)$ puis multipliera le résultat par $q$ et ainsi de suite: \[ \begin{array}{rl} u[i]= \left( (q\times q)\times q\right)\times q & \times q \\ \left( q^2\times q\right) \times q & \times q \\ q^3\times q & \times q \\  \qquad q^4 & \times q \\ & \; \; q^5 \end{array} \] Comptons le nombre d'opérations, il suffit pour cela de voir qu'il y en a autant que de lignes proposées ci-dessus moins un ou que de signes "$\times$" plus simplement. Il y en a quatre, à cela s'ajoute le dernier calcul: $q^i \times a$. Pour $u[5]$ il faut 5 opérations élémentaires de type multiplication.

Pour $u[i]$ avec $i$ variant de 0 à 10 il faut $i$ opérations. Le nombre d'opérations au final est la somme de celles qu'il a fallu effectuer pour chaque $u[i]$. Ceci est un résultat élémentaire applicable à toute boucle de type "Pour...FinPour". D'où le résultat: \[ \sum_{i=0}^{10} i = 0+1+2+3+4+5+6+7+8+9+10 = \frac{10\times 11}{2} \] il s'agit de la somme des dix premiers termes d'une suite arithmétique, et la plus simple qui est celle des entiers, en appliquant la formule vue en propriété 3.8 nous trouvons qu'il faut 55 multiplications.

Algorigramme

Pour représenter graphiquement cet algorithme, plutôt que de créer un élément pour la boucle "Pour(...) Faire(...) FinPour" nous utilisons son équivalent "TantQue(...) Faire(...) FinTantQue" dont voici l'analogie à appliquer:

• La boucle (i allant de 0 à 10) devient la condition (i différent de 11) précédée d'une initialisation (i reçoit 0)
• L'affectation $(u[i] \leftarrow q^ia)$ reste inchangée et on rajoute l'affectation $(i \leftarrow i+1)$

Il ne faut pas s'étonner de voir une variable recevoir en affectation sa propre valeur augmentée de 1. Dans l'affectation $(i \leftarrow i+1)$ le $i$ à gauche est une case mémoire dont le nom est $i$ alors que l'expression à droite $(i+1)$ est un nombre défini comme somme de la valeur contenue dans la case nommée $i$ avec l'entier 1. Une fois la somme effectuée, la nouvelle valeur dans la case $i$ devient l'ancienne incrémentée d'une unité. Chaque fois que l'on agit de la sorte en affectant à une variable une expression faisant intervenir sa valeur actuelle, celle-ci disparaît pour laisser place au résultat du calcul. L'avantage principal du procédé est de minimiser l'occupation de la mémoire. Dès lors qu'une valeur n'a plus d'intérêt pour le programme, l'adresse mémoire affectée peut servir à autre chose.

[[{"type":"media","view_mode":"media_original","fid":"160","attributes":{"alt":"","class":"media-image","height":"578","typeof":"foaf:Image","width":"495"}}]]

La structure de l'algorithme devient:

$G(q,a)$

$u \leftarrow \text{Tab}(11)(0)$

$i \leftarrow 0$

TantQue $i\neq 11$ Faire

$u[i] \leftarrow q^i \times a$
$i \leftarrow i+1$

FinTantQue

Afficher $u$

Optimiser l'algorithme

Voyons comment cet algorithme sera exécuté. Dans un premier temps deux variables sont créées, un tableau $u$ et un entier $i$. Ils sont initialisés directement au moment de l'affectation. Puis une boucle apparaît, elle se produit tant que $i$ est différent de 10. Au premier passage, l'entier vaut 0 et donc elle est enclenchée.

L'élément $u[0]$ reçoit $a$ en mémoire. Le calcul de $q^0$ ne compte pas, la machine possédant un algorithme de calcul de la puissance lui évitant tout calcul inutile, de même $(1 \times a)$ n'est pas effectué. Ensuite, l'indice $i$ est incrémenté, il vaut à présent 1 et la boucle est renvoyée au test.

Le test $(i=10)$ est encore négatif, et on lance les deux affectations: $u[1]$ reçoit le résultat de l'opération $(q\times a)$ et $i$ est incrémenté après ce calcul. On retourne au test, et c'est là qu'il y a un manque d'optimisation dans l'algorithme. L'élément $u[2]$ sera rempli par le résultat du calcul: \[ q \times q \times a \] Peu importe dans quel ordre la machine effectue l'opération, elle fera 2 multiplications alors que le nombre $(q\times a)$ a déjà été calculé.

Mémoriser un résultat

Lorsqu'on sait qu'un calcul intermédiaire peut s'avérer utile dans la suite d'un algorithme il est judicieux de le conserver en mémoire. S'il s'agit d'une ou deux réutilisations ce n'est pas forcément vital, mais supposons que nous ayons à créer un tableau à un million d'élément de $u_0$ à $u_{10^6}$ alors le nombre d'opérations répétées eût été énorme (environ cinq-cents milliards).

Dans notre petit exemple, nous voyons qu'à la fin $u[9]$ est calculé et mémorisé, mais lorsqu'on lance le calcul de l'élément suivant $u[10]$, il suffit de multiplier la valeur $u_9$ par la raison pour avoir le terme suivant de l'indice, au lieu de cela nous recommençons toutes les opérations. C'est un gâchis en temps qu'il faut savoir repérer.

La solution est simple et inscrite dans la définition récursive de la suite $u$: les premières étapes restent inchangées, il faut créer un tableau et initialiser un indice $i$ pour effectuer 11 tâches similaires. Le calcul de $u[i+1]$ consiste en celui de $u[i]$ que l'on multiplie par la raison $q$. Une fois le tableau créé nous initialisons le premier élément avec une affectation directe $(u[0] \leftarrow a)$ et on lance la boucle allant de 0 à 10, puisqu'on traite le terme $u_{i+1}$ lors du passage à l'étape $i$:

$G(a,q)$

$u \leftarrow \text{Tab}(11)(0)$
$u[0] \leftarrow a$
$i \leftarrow 0$

TantQue $i \neq 10$ Faire

$u[i+1] \leftarrow q \times u[i]$
$i \leftarrow i+1$

FinTantQue

Afficher $u$

Le gain en calcul est conséquent. Il n'y a qu'une multiplication par étape, il y a toujours l'addition $(i+1)$ mais sans importance comparé aux opérations possibles si les termes $u_n$ sont de grands nombres. On passe de 55 multiplications à 10 multiplications. Pour $10^{6}$ termes on obtiendrait autant de multiplications contre les $5\cdot 10^{11}$ avec la résolution basique.

Il y a autant d'opérations que d'affectations à exécuter, on en déduit qu'il s'agit de l'algorithme le moins coûteux en temps de calcul. L'objectif recherché de cet article n'était pas tant de résoudre un problème aussi simple mais d'illustrer l'importance du choix des formules de calcul pour atteindre la solution.

[[{"type":"media","view_mode":"media_original","fid":"161","attributes":{"alt":"","class":"media-image","height":"481","typeof":"foaf:Image","width":"544"}}]]