Multiprécision - Algorithmique II

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  ?

À 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 :

L'algorithme s'en déduit sans grandes difficultés, il faut en particulier prendre garde aux débordements 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 #25).

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.

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 \(\Theta(n)\) dans tous les cas puisqu'il faut balayer l'ensemble des chiffres du plus grand des deux nombres pour construire le résultat \(R\). Cependant, pour des raisons d'efficacité il peut arriver que l'on utilise la plus grande des deux listes pour y ranger le résultat, à la manière de l'accumulateur la machine ram, dans ce cas on distingue un meilleur des cas où la somme s'obtient en \(\hat T_{+}=\min\{n,m\}\) étapes et un pire des cas où il faut balayer tous les chiffres \(\check T_{+}=\max\{n,m\}\).

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)\).

Déclarez la structure tnombre suivante pour représenter les nombres multiprécision :

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

tnombre Addition(tnombre A, tnombre B, uint base)
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\). Modifiez votre programme en conséquence.

(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 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.

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