TD I20, semaines 8 et 9

Calculs en multi-précision

On représente un nombre entier positif x par le tableau a de ses chiffres, en base b, de telle sorte que :
x = a0 + a1 b + a2 b2 ... + an bn
On dit que ak est le chiffre de poids k. On appelle MAX le nombre maximal de chiffres autorisés, et on utilise une déclaration :
    typedef int nombre [MAX];
  1. Ecrire, en langage C, une fonction qui affiche les chiffres de x dans l'ordre habituel, c'est à dire en commençant par le premier chiffre non nul de poids le plus fort.

  2. Ecrire, en langage C, une fonction qui calcule la somme x+y. Comment proposez-vous de traiter le cas où le nombre de chiffres de x+y dépasse MAX ?

  3. On souhaite manipuler les nombres les plus grands possibles, pour une valeur donnée de MAX ; quel est alors, à votre avis, le meilleur choix pour la base b ? (veiller à ce que la fonction précédente, pour le calcul de la somme, reste correcte).

  4. Ecrire de nouvelles versions des fonctions précédentes, en supposant qu'un entier de k chiffres (k < MAX) est représenté par un tableau de ces k chiffres, suivis de la sentinelle -1.

Développement décimal d'un rationnel

Soit un rationnel a/b positif ; l'algorithme usuel de division, qui fournit le développement décimal de la fraction, s'écrit en C :
for (i = 0; i <= n; i++) {
  q = a / b;
  r = a % b;
  a = 10 * r;
}
La partie entière de a/b, puis les n premières décimales apparaissent successivement dans la variable q.

En fait ce développement est périodique, puisqu'il n'y a qu'un nombre fini possible de restes : la période est au plus b. Pour tenter de trouver cette période, lorsqu'elle n'est pas trop grande, on stocke chaque reste r dans un tableau nommé reste, et on examine si ce reste figure déjà dans ce tableau : si oui, on a trouvé la période, sinon on continue. Il ne faut pas oublier qu'un tableau est de taille limitée, et qu'il faut donc stopper l'algorithme lorsqu'on atteint cette limite ; dans ce dernier cas, la période est supérieure à la taille du tableau.

Ecrire la fonction decimales, qui stocke la partie entière et les décimales du rationnel a/b dans un tableau, et retourne dans une structure : la longueur du développement, sa période, et l'indice de début de la partie périodique. Par exemple, si le développement vaut 3.141252525... on stocke seulement les chiffres 3,1,4,1,2,5 et on retourne :

Préciser les conventions adoptées si le tableau déborde avant découverte de la période. Comment modifier la fonction pour obtenir ce développement dans une base quelconque ?