Algorithmique ii - 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 relatifs 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  ?
Démontrez ce lemme, puis à 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\).
Écrivez un programme Python 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=1000\). Combien de chiffres contient le résultat ? Ce résultat peut-il être stocké dans un registre de 64 bits ? Quelle est la plus grande valeur \(n\) pour laquelle votre calculatrice est capable de calculer la factorielle ?

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 grandes difficultés, il faut en particulier prendre garde aux dé­bor­de­ments de tableaux, leurs tailles ne sont pas nécessairement égales. Dans cette solution, on échange si nécessaire le rôle des tableaux \(A\) et \(B\) de manière à ce que le plus petit détermine la butée de la première boucle. Il ne reste plus ensuite qu'à propager l'éventuelle retenue sur les chiffres qui reste dans le nombre le plus long (boucle à la ligne #26).

Addition(A,B,base):liste
données
   A,B: liste
   base: entier
variables
   i: entier
   C: liste 
   retenue: entier
debut    
   SI (#B > #A) ALORS
      Echanger(A,B)
   FSI
   C ← Allouer(#A + 1,0) // cellules initialisees a 0
   i ← 0
   retenue ← 0
   TQ (i < #B) FAIRE
      C[i] ← A[i] + B[i] + retenue
      SI C[i] ≥ base ALORS
         retenue ← 1
         C[i] ← C[i] - base
      SINON
	 retenue ← 0
      FSI 
      i ← i + 1
   FTQ
   TQ (i < #A) FAIRE
      C[i] ← A[i] + retenue
      SI C[i] ≥ base ALORS
         retenue ← 1
         C[i] ← C[i] - base
      SINON
	 retenue ← 0
      FSI 
      i ← i + 1
   FTQ
   SI (retenue > 0) ALORS
      C[i] ← retenue
   SINON
      Effacer(C[i])
   FSI
   RETOURNER C
 FIN

Nous allons résoudre le problème de la multiplication de deux entiers \(A\times 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 le chiffre des unités.

Écrivez le détail de la multiplication des deux entiers \(1.202\times 937\) conformément à l'algorithme étudié en primaire.
Multiplication(A,B,base):liste
données
   A,B: listes
   base: entier
variables
   i,j: entier
   C: liste; // #C = #de termes de C
   retenue:entier
debut    
   C ← Allouer(#A + #B,0); // cellules initialisees à 0
   i ← 0; // indice de parcours des chiffres de B
   TQ (i < #A) FAIRE
      retenue ← 0
      j ← 0; // indice de parcours des chiffres de A
      TQ (j < #B) FAIRE
         C[i + j] ← C[i + j] + A[i] * B[j] + retenue
         retenue ← C[i + j] DIV base
         C[i + j] ← C[i + j] MOD base
         j ← j + 1
      FTQ
      SI (retenue > 0) ALORS
         C[i + j] ← retenue
      FSI
      i ← i + 1
   FTQ
   RETOURNER C
 FIN

Complexité

L'analyse de la complexité ne pose aucune difficulté particulière. Notons \(n\) et \(m\) le nombre de chiffres des entiers \(A\) et \(B\) (rappelons qu'en base \(b\) un nombre \(N\) s'écrit sur \(\lfloor\log_b N\rfloor+1\) chiffres). La somme s'obtient en \(\hat T_{+}=\min\{n,m\}\) étapes dans le meilleur des cas et en \(\check T_{+}=\max\{n,m\}\) dans le pire des cas. Le produit demande \(n\times m\) étapes pour multiplier l'ensemble des chiffres de \(A\) avec ceux de \(B\) puis \(n+m+1\) additions sur \(\max\{n,m\}\) chiffres pour obtenir les chiffres du résultat, soit \(\Theta(nm)\).

Travaux pratiques

Écrivez une fonction S2L(chaine) qui à partir d'une chaîne de caractères chaine, renvoie la liste des symboles transtypés en entiers qui la constitue et dans l'ordre inverse. Par exemple, si ch = "320154" la fonction renvoie la liste [4,5,1,0,2,3]. Ecrivez une fonction L2S(liste) qui réalise l'opération inverse, à savoir, qui transforme une liste en chaîne de caractère dans l'ordre inverse.

Écrivez deux fonctions somme(A,B) et produit(A,B) qui réalisent respectivement l'addition et la multiplication multiprécision sur les entiers A et B.

Si l'on veut 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. Modifiez votre programme en tenant compte de cette nouvelle base de calcul.

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

[Solution en C]
[Solution en Python]