Les principes mathématiques

Mathématique interne : le binaire

Histoire

On attribue le système binaire à Leibniz vers 1700, mais ceci cette version a été contestée par John W. Shirley dans "Binary Numeration before Leibniz".
il y a même une référence aux hexagrammes du Yi Jing (classique des changements) qui peuvent être représentés par un code binaire sur 6 bits (un bit est un chiffre qui vaut 0 ou 1).

Les bases de calcul

En base 10, on utilise les chiffres de 0 à 9 associés à un multiplicateur exprimé par une puissance de 10. En base 2 on utilise les chiffres 0 et 1 associés à un multiplicateur exprimé par une puissance de 2. On pourrait généraliser ce principe à n'importe quelle base de représentation des nombres. Pour des bases supérieures à 10, on utilise des symboles en plus des chiffres de 0 à 9 que l'on appelle digits. En informatique, on utilise également la base 16 qui utilise les digits de 0 à 9 et A à F (majuscule ou minuscule).

Représentation des entiers

On distingue les entiers non signés (ensemble ℕ) et les entiers signés (ensemble ℤ).

Les entiers non signés

En appliquant ce qui vient d'être expliqué précédemment, on peut écrire la relation qui permet d'exprimer un nombre en base 10 à partir d'un nombre exprimé en base 2 sur n bits : $N_{10}={\displaystyle \sum _{k=0}^{n-1}}{a}_k{2}^k$.
Cette relation permet de convertir un nombre exprimé en base 2 en un nombre exprimé en base 10.

Prendre un papier et un crayon, puis demander un nombre binaire

La conversion décimale binaire est réalisée à l'aide d'une suite de divisions pas 2 jusqu'à ce que le quotient vaille 0.

Prendre un papier et un crayon, puis demander un nombre décimal

A la place des divisions, je propose une méthode avec un tableau. On construit le tableau des puissances de 2 de 128, qui est la puissance de deux immédiatement inférieure à 173, jusqu'à 1

Prendre un papier et un crayon, puis demander un nombre décimal

Les entiers signés

Pour représenter les nombres négatifs dans une base, on utilise le complément à la base en utilisant la relation $-{\displaystyle \frac{b^n}{2}}\le N\le {\displaystyle \frac{b^n}{2}}-1$ où N est le nombre signé et n le nombre de bits maximium utilisé pour la représentation. Cela signifie qu'un nombre signé ne peut être identifié comme signé que sur un nombre de bits connus. Cela ne pose pas de problème pour les calculatrices et ordinateurs car le nombre de bits est fixé par la structure matérielle de la machine et peut être 8,16,32 ou encore 64 bits (8 et 16 étant maintenant obsolètes).

Dans le cas de la base 2 cette relation donne $-{\displaystyle \frac{2^n}{2}}\le N\le {\displaystyle \frac{2^n}{2}}-1\Rightarrow -2^{n-1}\le N\le 2^{n-1}-1$. Ce qui fait que c'est le bit de poids le plus fort (rang n-1), pour un nombre exprimé sur n bits, qui représente le signe du nombre, ce qui fait que le nombre en base 10, peut s'écrire en utilisant la relation : $N_{10}=-a_{n-1}{2}^{n-1}+{\displaystyle \sum _{k=0}^{n-2}}{a}_k{2}^k$ .

Une remarque importante :
la valeur négative -83 donne la même suite binaire que 173 sur 8 bits. On en déduit que la valeur binaire ne permet pas de savoir si le nombre est négatif ou positif. Ceci explique que certains langage de programmation distinguent les entiers signés des entiers son signés et d'autres utilisent uniquement des entiers signés. Au niveau du processeur c'est un registre particulier, nommé registre d'état qui contient les informations de signe après chaque calcul.
Sur les calculatrices les fonctions de conversions qui traitent les nombres négatifs utilise un certain nombre de bits (en général 16) qu'il faut respecter pour obtenir le bon résultat.

Addition en binaire

L'addition en binaire donne un résultat binaire identique pour les nombres signés et non signés. Cela vient de la représentation des entiers signés en complément à 2 et confirme que la représentation binaire ne permet de définir le type d'entier signé ou non signé.

Le résultat ne peut pas être exprimé sur 9 bits, la retenue n'est pas affichée, car les microprocesseurs expriment le résultat sur le même nombre de bits que les opérandes :

L'addition de deux nombres non signés de n bits donne normalement un nombre sur n bits. Le résultat est exprimé sur sur n bits, il y a donc des cas ou le résultat sera erroné.
L'addition de deux nombres signés de n bits peut également fournir des résultats erronés, comme la somme de deux nombres positifs qui donnent un nombre négatif ou bien la somme de deux nombres négatifs qui donnent un résultat positif, dans ce cas on parle de dépassement dans les calculs.

En base 10 faire une soustraction revient à ajouter l'opposé du nombre. En base 2, faire une soustraction revient également à ajouter la valeur négative du nombre qui est le complément à 2 du nombre.

Le calcul du complément à 2
Pour transformer un nombre positif en un nombre négatif en base 10, on ajoute le signe moins devant le nombre. En base 2 on calcule le complément à 2 qui consiste à prendre le complément à 1 du nombre puis ajouter 1. Le complément à 1 consiste à changer la valeur de chaque bit : un 0 devient un 1 et un 1 devient un 0.
L'exemple ci-dessous montre comment calculer le complément à 2 de la valeur 83 en base 10, et vérifie que le résultat donne bien -83.

Prendre un papier et un crayon, puis demander une opération

Représentation des réels

Réels en virgule fixe

Un nombre en virgule fixe possède une partie entière et une partie fractionnaire (les chiffres après la virgule). Chaque partie est exprimée sur un nombre maximum de bits.
On procède de manière identique à la méthode des nombres non signés pour la partie entière, exprimée sur n bits, et, en ajoutant des puissances négatives de 2 pour la partie fractionnaire exprimée sur p bits : $N_{10}={\displaystyle \sum _{k=-p}^{n-1}}{a}_k{2}^k$.
La conversion de la forme binaire vers la forme décimale se fait également en appliquant la définition :

La conversion de la valeur décimale de la partie entière utilise les mêmes méthodes que pour les nombres non signés. Pour la partie fractionnaire, on utilise une suite de multiplications par 2 de la partie fractionnaire jusqu'à obtenir 0 pour la partie entière et pour la partie fractionnaire. La valeur binaire est composée de la suite des parties entières des résultats des multiplications.

Prendre un papier et un crayon, puis demander un nombre décimal

Réels en virgule flottante

La représentation virgule flottante est identique à la notation scientifique en base 10 qui utilise un nombre, nommé mantisse, multiplié par une puissance de 10. En base 2 on utilise une puissance de 2 ce qui donne $N_{10}={(-1)}^s(1+m)2^e$, avec s bit de signe (0 ou 1), m mantisse de type réel compris entre 0 et 1, et e exposant décalé pour obtenir des valeurs d'exposants négatifs. Un exposant décalé est de la forme e=E-D avec D décalage qui dépend du nombre de bits.
La norme IEEE 754 définit différentes précisions en fonction du nombre de bits affectés à la mantisse et à l'exposant. La valeur réelle est de la forme $N_{10}={(-1)}^s(1+m)2^{E-D}$. Les différentes précisions sont rappellées dans le tableau ci-dessous :

Il existe une représentation IEEE754 de π pour toutes ces précisions.

On peut calculer la représentation d'un nombre en virgule flottante en partant de la représentation en virgule fixe de ce nombre. Pour cela il suffit de décaler la valeur en virgule fixe pour obtenir la forme 1,m en ajoutant l'exposant qui correspond à ce décalage.

Calcul des fonctions mathématiques

Algorithme CORDIC

CORDIC signifie COordinate Rotation DIgital Computer (calcul numérique par rotation de coordonnées).
C'est un algorithme de calcul des fonctions trigonométriques et hyperboliques qui a été décrit pour la première fois par Jack E. Volder en 1959.
Il a été utilisé dans les premières calculatrices, comme la HP-35 qui utilisait la notation polonaise inverse, car il est parfaitement adapté aux faibles puissances de calcul et aux faibles capacités mémoires. Il a été également utilisés dans les premiers ordinateurs des années 1970.
Le calcul, qui utilise les formules de trigonométrie, est ramené dans un intervalle restreint en utilisant les propriétés des fonctions mathématiques.

Le principe mathématique de ce calcul est la rotation dans le plan.
Pour calculer $x=\cos (\theta )$ et $y=\sin (\theta )$ sur $[0,{\displaystyle \frac{\pi }{2}}]$, on calcule les nouvelles valeurs $x_{i+1}=\cos ({\theta }_{i+1})$ et $y_{i+1}=\sin ({\theta }_{i+1})$ en fonction des valeurs précédentes $x_i=\cos ({\theta }_i)$ et $y_i=\sin ({\theta }_i)$ en appliquant : ${\theta }_{i+1}={\theta }_i+{\gamma }_i$, cela donne les équations :

En posant $x_i=\cos ({\theta }_i)$, $y_i=\sin ({\theta }_i)$ , $x_{i+1}=\cos ({\theta }_{i+1})$, $y_{i+1}=\sin ({\theta }_{i+1})$ on obtient : Dans une calculatrice, on fonctionne en binaire, on pose : $\tan ({\gamma }_i)=2^{-i}\Rightarrow {\gamma }_i=\arctan (2^{-i})$ ce qui donne : Le coefficient $\frac{1}{\sqrt{1+2^{-2i}}}$ converge rapidement vers sa limite, et peut donc être considéré comme constant et mémorisé dans la machine, il vaut : $\underset{n\to \mathrm{\infty }}{lim}{\displaystyle \prod _{k=0}^{n-1}}{\displaystyle \frac{1}{\sqrt{1+2^{-2k}}}}\approx 0.6073$

En 1971, J. Walther, ingénieur chez Hewlett Packard, généralisa l'algorithme CORDIC aux fonctions hyperboliques, ce qui permit de calculer le logarithme, l'exponentielle ainsi que la racine carrée, en utilisant toujours les propriétés des fonctions afin de réduire l'intervalle de calcul.

Constantes de calculs
Pour le mode circulaire, on a déjà la constante multiplicative à appliquer au resultat : $\underset{n\to \mathrm{\infty }}{lim}{\displaystyle \prod _{k=0}^{n-1}}{\displaystyle \frac{1}{\sqrt{1+2^{-2k}}}}\approx 0.6073$.
Pour le mode hyperbolique, on a également une constante multiplicative à appliquer au résultat : $\underset{n\to \mathrm{\infty }}{lim}{\displaystyle \prod _{k=0}^{n-1}}{\displaystyle \frac{1}{\sqrt{1-2^{-2k}}}}\approx 1.205$ .

Domaine de définition ou de convergence
Les calculs de l'algorithme CORDIC convergent vers la fonction uniquement dans un intervalle fini et limité. Cette Limite vient des valeurs extrêmes possible de l'angle θ (valeurs maximales possibles de z). Dans le fonctionnement trigonométrique, cette limite vaut , ce qui valide le fait de travailler entre 0 et π/2.
Dans le fonctionnement hyperbolique, cette limite vaut , cette limite implique une limite sur x₀ et y₀ dans le mode vecteur qui vaut ${\displaystyle \frac{y_0}{x_0}}\approx 0.78$.
Cela signifie qui faut utiliser les propriétés des fonctions pour étendre le calcul en dehors de ces limites, comme par exemple pour l'exponentielle en utilisant la relation $x=q\log (2)+r$ avec q entier, les valeurs de q et r se calculent de la façon suivante : $q=\lfloor {\displaystyle \frac{x}{\log (2)}}\rfloor$ et $r=x-q\log (2)$ ainsi l'exponentielle devient $e^x=2^q{e}^r$ .