Calcul multiprécision

Présentation du problème

Dans le cours d'algorithmique de première année, nous avons étudié le modèle de donnée nombre et nous avons vu que la représentation des nombres en machine posait certains problèmes, taille limitée, précision des calculs, etc.

On cherche dans ce chapitre à dépasser la limitation physique imposée par les processeurs qui ne permettent de réaliser des calculs arithmétiques que sur des entiers (ou des flottants) dont la taille ne dépasse pas celle d'un registre machine, soit 64 bits pour la plupart des machines modernes. Nous nous limiterons aux quatre opérations arithmétiques +, −, × et / sur les entiers naturels pour ne pas compliquer inutilement le propos.

Quelle est l'entier naturel le plus grand que l'on peut représenter sur une machine 64 bits ? Quelle est la condition sur les tailles de deux entiers \(a\) et \(b\) pour lesquelles on peut réaliser l'opération de multiplication \(a* b\) en machine  ?
À l'aide de la formule de Stirling, donnez un encadrement du nombre de chiffres nécessaires pour représenter la factorielle \(n!\) d'un entier naturel \(n\) en base \(2\).

Pour dépasser la limitation des registres en machine, on représente un nombre entier à l'aide de la liste de ses chiffres. Comme nous lisons (occidentaux) de la gauche vers la droite, il est naturel de placer le chiffre le plus significatif à gauche et le moins significatif à droite afin de pouvoir estimer rapidement la magnitude du nombre avant même d'en terminer la lecture. Il est donc tentant de calquer cette représentation dans la liste, mais en plaçant les chiffres dans la liste du moins significatif au plus significatif, et en indexant la liste à partir de 0, l'index fournit la puissance de la base associée ce qui facilite l'écriture des algorithmes. Ainsi le nombre \(N=3014\) en base 10 est représenté par la liste \[L=[4,1,0,3]\] et on a par définition \[N=\sum_{i=0}^3L[{\color{yellow}i}]10^{\color{yellow}i}.\] Avec cette représentation, les nombres ne sont limités en taille que par l'espace mémoire disponible dans la machine et il est très facile de coder un entier de plusieurs milliers de chiffres. C'est de cette manière que certains langages de programmation, comme Python, permet d'effectuer des calculs sur des entiers arbitrairement grands.

Pour effectuer une addition, nous allons tout simplement appliquer l'algorithme étudié au primaire. Si \(A\) et \(B\) désignent les deux nombres représentés par un tableau, on additionne les chiffres des deux tableaux terme-à-terme dans l'ordre croissant des indices en propageant une retenue si la somme est supérieure ou égale à la base \(b\). La table ci-dessous traite l'addition des deux entiers \(4.521.078+294.383.493\) comme nous l'avons apprise, la progression du calcul se faisant de la droite vers la gauche de la table, donc en partant des chiffres des unités :

indice 9 8 7 6 5 4 3 2 1 0
retenue 1 1 1
\(A\) 4 5 2 1 0 7 8
\(B\) 2 9 4 3 8 3 4 9 3
\(A+B\) 2 9 8 9 0 4 5 7 1
Addition des deux entiers 4.521.078 et 294.383.493 en base 10.

L'algorithme s'en déduit sans grande difficulté. Il faut prendre garde aux dé­bor­de­ments de liste, les tailles de \(A\) et \(B\) ne sont pas nécessairement égales. Ici, on règle la différence des tailles en testant à chaque étape si l'on déborde ou non de chacune des listes. L'intégration de la dernière retenue dans le résultat du calcul est obtenue en avançant jusqu'à \(n\) inclus, c'est-à-dire en débordant d'une unité de la taille maximale des deux listes. 

Addition(A,B,base):liste d'entiers
DONNÉES
   A,B: listes d'entiers
   base: entier
VARIABLES
   i,n,retenue,xi,yi: entiers
   R: liste d'entiers
DEBUT
   n ← max(|A|,|B|)
   R ← Allouer(n + 1, |entier|) // cellules initialisees a 0
   retenue ← 0
   i ← 0
   TQ (i ≤ n) FAIRE
      xi ← (i < |A|) ? A[i] : 0
      yi ← (i < |B|) ? B[i] : 0          
      R[i] ← A[i] + B[i] + retenue
      retenue ← 0
      SI (R[i] ≥ base) ALORS
         retenue ← 1
         R[i] ← R[i] - base
      FSI 
      i ← i + 1
   FTQ
   SI (R[i - 1] > 0) ALORS
      Effacer(R[i - 1])
   FSI
   RETOURNER R
 FIN

Nous allons résoudre le problème de la multiplication de deux entiers \(A\cdot B\), là aussi avec l'algorithme étudié au primaire dans lequel chaque chiffre de \(B\) est multiplié à chaque chiffre de \(A\), en commençant par les chiffres des unités.

Écrivez le détail de la multiplication des deux entiers \(1.202\times 937\) conformément à l'algorithme étudié en primaire.

Observons l'algorithme de la multiplication. Les retenues des produits successifs dans la table sont listées dans l'ordre inverse chronologique pour correspondre aux positions des chiffres de \(B\).

indice 9 8 7 6 5 4 3 2 1 0
retenues 1241 0010 0000
\(A\) 5 2 1
\(B\) 2 4 9 3
\(j=0\) 1 5 6 3
\(j=1\) 4 6 8 9
\(j=2\) 2 0 8 4
\(j=3\) 1 0 4 2
\(A\cdot B\) 1 2 9 8 8 5 3
Produit des deux entiers 521 et 2.493 en base 10.

Il est inutile de stocker les \(|B|\) lignes des produits successifs par les chiffres \(B[j]\) de \(B\), il suffit d'additionner les résultats au fur et à mesure du calcul, le décalage des indices vers la gauche étant fourni par la variable \(j\) indexant les chiffres de \(B\) : 

Multiplication(A,B,base):liste d'entiers
données
   A,B: listes d'entiers
   base: entier
variables
   i,j,retenue: entiers
   R: liste; 
debut    
   R ← Allouer(|A| + |B|, |entier|); // cellules initialisees à 0
   j ← 0; // indice des chiffres de B
   TQ (j < |B|) FAIRE
      retenue ← 0
      i ← 0; // indice des chiffres de A
      TQ (i < |A|) FAIRE
         R[i + j] ← R[i + j] + A[i] * B[j] + retenue
         retenue ← R[i + j] DIV base
         R[i + j] ← R[i + j] MOD base
         i ← i + 1
      FTQ
      R[i + j] ← retenue
      j ← j + 1
   FTQ
   RETOURNER R
 FIN

Complexité

On rappelle qu'en base \(b\) un nombre \(N\) s'écrit sur \(\lfloor\log_b N\rfloor+1\) chiffres. L'analyse de la complexité ne pose aucune difficulté particulière. Pour l'addition, puisque nous construisons le résultat \(R\) à \(1+n=1+\max\{|A|,|B|\}\) chiffres, il faut \(\Theta(n)\) opérations.

La multiplication demande \(|A|\cdot|B|\) produits de chiffres pour multiplier l'ensemble des chiffres de \(A\) avec ceux de \(B\). Il y a également \(|A|\cdot|B|+1\) additions sur \(\max\{|A|,|B|\}\) chiffres pour obtenir les chiffres du résultat. Donc \(\Theta(|A|\cdot|B|)\) opération globalement.

Travaux pratiques

Les programmes sont à écrire en langage \(C\). Les types préfixés par la lettre u/l sont en fait préfixés par unsigned/long, par exemple uchar désigne le type unsigned char et ullong désigne le type unsigned long long.
Déclarez la structure tnombre suivante pour représenter les nombres mul­ti­pré­ci­sion : 
typedef struct {
  uint nbc;
  uint* chiffres;
} tnombre;
et implantez la fonction tnombre I2N(int n, uint base) qui convertit un entier en nombre multiprécision en base base.
Écrivez une fonction ullong Factorielle(uchar n) qui calcule de manière itérative la factorielle \(n!\) d'un entier naturel \(n\), i.e. \[n!=n(n-1)(n-2)\ldots 3.2.1.\] Testez votre programme pour \(n=20\). Combien de chiffres contient le résultat ? Combien de bits sont nécessaires pour stocker ce résultat ? Quelle est la plus grande valeur \(n\) pour laquelle votre calculatrice est capable de calculer la factorielle ?
Écrivez une fonction tnombre S2N(char *chaine) qui à partir d'une chaîne de caractères chaine, renvoie une structure tnombre contenant le tableau des symboles transtypés en entiers qui la constitue et dans l'ordre inverse. Par exemple, si ch = "320154" la fonction renvoie la structure contenant le tableau [4,5,1,0,2,3] et le nombre de chiffres \(6\). Écrivez une fonction char *N2S(tnombre N) qui réalise l'opération inverse, à savoir, qui transforme un tableau d'entier en chaîne de caractères dans l'ordre inverse.
Écrivez deux fonctions
  1. tnombre Addition(tnombre A, tnombre B, uint base)
  2. tnombre Multiplication(tnombre A, tnombre B, uint base)
qui réalisent respectivement l'addition et la multiplication multiprécision sur les entiers A et B représentés par les listes de leurs chiffres. On supposera initialement que la base est un entier inférieur ou égal à \(10\) pour pouvoir exploiter les fonctions de conversion S2N(chaine) et N2S(liste).
Écrivez une fonction tnombre FactMP(uint n) qui calcule la factorielle d'un entier naturel n en multiprécision. Combien y-a-t-il de \(0\) dans \(n!\) ?
Soit \(n\in{\mathbb N}\). Quelle est la taille exacte (i.e. le nombre de chiffres) de \(n!\) en base \(b\) ?

Remarques : (1) Pour augmenter les performances de ces algorithmes, on peut s'appuyer sur l'ual du processeur qui est capable de réaliser des additions sur \(n\) bits (32 ou 64 selon l'architecture). Autrement dit il est beaucoup plus efficace de travailler en base \(2^{32}\) au lieu de la base 10. Les chiffres de la base sont alors saisis sous forme d'entiers naturels représentant leur ordre dans la numération choisie. Par exemple, pour la base 16, on n'utilisera pas les symboles \(A,B,C,D,E,F\) pour coder les 6 chiffres manquants mais tout simplement \(10\), \(11\), \(12\), \(13\), \(14\) ,\(15\).

(2) Il faut noter qu'en langage Python, contrairement au langage \(C\), les calculs multiprécision sont déjà intégrés, les exercices ci-dessus décrivent simplement comment procéder. Il existe évidemment d'autres algorithmes beaucoup plus efficaces pour additionner et multiplier rapidement (cf. TD), ceux présentés ici ne sont rien d'autre que ceux qui ont été appris à l'école primaire.