Enoncé
Etudier le signe de $u$ :
- Si $\; u_0<0 \; $ et $\; q>0 $ .
- Si $\; u_0>0 \; $ et $\; q<0 $ .
- Si $\; u_0<0 \; $ et $\; q<0 $ .
- Proposer un algorithme qui donne, à partir d'un terme $a$ accompagné de son indice $p$ et de la raison $q$, n'importe quel terme d'indice demandé $N$ .
- Proposer un algorithme qui donne le signe plutôt que la valeur avec les mêmes données fournies.
Remarque: On cherche dans la question 4 à produire un programme effectuant le moins de calculs. En particulier, on évite de surcharger en multiplications. Puis il s'agit de trouver un algorithme à la question 5 qui évite les calculs complexes, par exemple lorsque les termes sont très grands.
Indications
Pour les trois premières questions, il suffit de reproduire les méthodes des exercices précédents. Il peut être sage de commencer par des exemples si l'on ne se sent pas à l'aise avec l'étude directe. Et c'est là un conseil très large que tout mathématicien finit par appliquer quand les possibilités pour ses variables sont nombreuses.
Question 4: Par exemple, montrer qu'on peut trouver $q^{10}$ en seulement 3 multiplications. Prendre en considération le fait qu'on veut un programme efficace pour des très grandes valeurs, surtout de $N$.
Question 5: Le signe de $(-1200\, \times\, +32435)$ est le même que $(-1\, \times\, +1)$. Le temps de calcul n'est pas le même. On cherche à rendre le programme le plus léger possible en calculs. Quelles sont les propriétés dans le signe d'un produit sachant le signe des facteurs?
Solution
Question 1 - Premier terme négatif et raison positive.
Par exemple $(u_0=-1)$ et $(q=1)$ vérifient les conditions. Tous les termes sont égaux à $u_0$. Dans le cas plus général où $q$ est strictement positif il vient que toutes ses puissances le sont. Ainsi le facteur $q^n$ ne modifie par le signe de l'expression $q^n\, u_0$ qui vaut $u_n$ dont nous étudions le signe. On en conclut que tous les termes adoptent le même signe que l'autre facteur qui est $u_0$. La conclusion se formalise: \[ \forall n \in \mathbb{N} \quad u_n < 0 \]
Question 2 - Premier terme positif et raison négative.
Puisque $(q<0)$ les puissances paires seront strictement positives et les autres à l'opposé: \[ \forall n \in \mathbb{N} \quad \begin{cases} q^{2n} & >0 \\ q^{2n+1} & <0 \end{cases} \] Il reste à multiplier ce résultat à un nombre $u_0$ strictement positif, donc qui ne modifie en rien le résultat: \[ \begin{cases} u_{2n} & >0 \\ u_{2n+1} & <0 \end{cases} \]
Question 3 - Premier terme et raison négatifs.
Identique à la question précédente sauf si le dernier argument, le fait que $u_0$ soit strictement négatif rend les résultats opposés: \[ \begin{cases} u_{2n} & <0 \\ u_{2n+1} & >0 \end{cases} \]
Question 4 - Algorithme de calcul d'un terme à partir d'un autre terme et de la raison.
L'algorithme se nomme $T$ et prend quatre arguments: un nombre $a$, un entier $p$ pour indiquer la position de $a$ dans la suite, un entier $q$ précisant la raison de la progression géométrique, et enfin $N$ un entier identifiant l'indice du terme à calculer. L'algorithme direct appliquant à la lettre la propriété 3.4 est un simple calcul suivi de l'affichage du résultat:
$T(a,p,q,N)$
Afficher $q^{N-p} \times a$
Fin
Seulement le calcul peut devenir très lourd si la différence $(N-p)$ est grande. Le programme aura à effectuer autant de multiplications moins une. Nous faisons appel à une procédure intermédiaire qui redéfinit le calcul d'une puissance et nous la nommons $\text{Puiss}(q,x)$ où $q$ est le nombre à élever à la puissance l'entier $x$. L'astuce consiste à décomposer $x$ suivant sa division euclidienne par 2. En effet, supposons que nous calculions $q^{10}$. La méthode directe demande à poser 9 multiplications: \[ q \times \ldots \times q \] Le programme se charge de trouver le résultat à $q\times q$ et il le multiplie à $q$ et ainsi de suite. Alors qu'il existe une autre méthode, on créé une variable intermédiaire $z$: \[ q \leftarrow q\times q \] Puis on passe directement à $q^4$ en calculant: $z \times z$ On peut pour l'instant écrase la valeur de $z$ en lui assignant ce nouveau résultat: \[ z \leftarrow z \times z \] Ainsi l'adresse mémoire $z$ reçoit la valeur de $q^4$. On modifie à nouveau par le procédé: $ z \leftarrow z \times z $. La valeur sauvegardée est $q^8$. Pour arriver à $q^{10}$ il nous suffit d'utiliser la valeur de $q^2$ mais puisqu'on l'a ecrasé il faut la recalculer. L'idée consiste alors à conserver cette valeur au début dans une autre variable $y$ par exemple. Nous reviendront plus en détail sur ce genre d'algorithme dans la rubrique consacré, il s'agissait avant tout de sensibiliser aux techniques d'économies dans le calcul.
Question 5 - Algorithme de calcul du signe de n'importe quel terme.
Il y a la méthode directe qui consiste à calculer la valeur du terme d'indice $N$ avec la propriété 3.4 mais dont le défaut est qu'elle lance un calcul que nous n'exploitons que pour son signe. L'idée est ici de remplacer les vraies valeurs par d'autres plus simples, et le calcul effectué devient rapide quelque soit les données entrées. On introduit dans l'algorithme deux variables $X$ et $Y$ qui prendront soit la valeur $+1$ soit la valeur $-1$. On effectuera le produit $XY$ et le signe recherché est celui du nombre: \[ q^{N-p} \times a \] On lance la fonction $S$ avec comme entrées $(a,p,q,N)$. On associe à $X$ la valeur $+1$ si $(a>0)$ et $-1$ si $(a<0)$. Il y a un travail supplémentaire à effectuer pour $\displaystyle q^{N-p}$. Si la différence $(N-p)$ est paire alors on associe à $Y$ la valeur $+1$. Sinon il faut vérifier le signe de $q$ qui est le même que sa puissance. L'objectif est de remplacer le calcul du nombre $(q^{N-p} \times a)$ qui peut s'avérer long par celui-ci: \[ \pm 1 \, \times \pm 1 \] qui est immédiat:
$S(a,p,q,N)$
Si $(a=0\, $ ou $\, q=0)$ Alors
Afficher "Le terme est nul"
Sinon
Si $(a>0)$ Alors $(X \leftarrow 1)$ Sinon $(X \leftarrow -1)$ FinSi
Si $(N-p)$ EstPair Alors $(Y \leftarrow 1)$
Sinon
Si $(q>0)$ Alors $(Y \leftarrow 1)$ Sinon $(Y \leftarrow -1)$ FinSi
FinSi
FinSi
Renvoyer Signe$(X \times Y)$
On utilise une fonction Signe qui vérifie le signe d'un nombre donné directement. Et une fonction EstPair qui indique si un nombre est pair. On les retrouve dans tous les langages informatiques.