Vous devez maintenant avoir une certaine expérience du C. Les exercices qui vont suivre ne sont pas plus compliqués à programmer que les précédents. Par contre, il est nécessaire de procéder méthodiquement pour arriver à un résultat. En particulier, il faudra utiliser des bibliothèques de fonctions et un makefile pour le générer.

Vous devrez réaliser les exercices suivants, vous n'êtes obligé de tout faire que si cela vous amuse. Seule la première partie (représentation, opérations de base) est représentative du niveau que vous avez atteind car elle vous obligera à devenir un roi du débogueur pour mettre au point vos programmes.
Dans votre compte rendu (une page ou deux) vous devrez indiquer, la structure du programme, ce que contiennent les bibliothèques et le listing du fichier Makefile ainsi que le répertoire où se trouvent les fichiers.



Les calculs sur les grands nombres ont quelque chose de fascinant. Il repoussent les possibilités de la machine et donnent l'impression de jongler avec l'infini. Les capacités des ordinateurs actuels et les besoins en cryptographie ont fait faire à ce domaine des progrès fantastiques. Il n'est pas possible à cause des limitations en mémoire de la représentation des variables, d'effectuer les calculs sans redéfinir un type de variable et les opérations de base. Ce chapitre se divise en deux parties. Dans la première nous allons écrire les routines nécessaires à la manipulation des variables du type que nous allons définir pour traiter les grands nombres. Dans une seconde partie nous utiliserons ces procédures élémentaires pour résoudre des problèmes mathématiques.

La représentation que nous allons choisir n'est ni optimale en mémoire, ni en temps de calcul. Elle présente néanmoins l'avantage d'être très proche de la représentation des nombres sur une feuille de papier, de ce fait les algorithmes que nous allons écrire pour manipuler les grands nombres sont proches de ceux étudiés par les écoliers.

La structure que nous allons utiliser contient trois champs :

Une petite optimisation consistera à stocker les chiffres de la droite vers la gauche. Cela facilite la propagation de la retenue en évitant de décaler tous les chiffres.

Comment sont représentés les nombres 1, -7, 321, -45, 3.141592 et 0 ?

Ecrire une fichier GrandNombre.h qui contient la déclaration de la structure.



Opérations de base et échauffements

Ce chapitre regroupe l'ensemble des procédures et de fonctions nécessaire à la manipulation des grands nombres. Elles sont rangées par ordre d'importance et de difficulté: les procédures de saisie, d'affichage et de manipulation des grands nombres, puis les procédures d'addition et de soustraction des grands nombres et enfin les procédures de multiplication et de division. Les exercices suivant ont pour but de vous aider à décomposer le problème suivant l'ordre indiqué précédemment. Ces exercices ne sont pas indépendant, ils reposent sur ceux qui ont été résolus précédemment. Ainsi les procédures de multiplication se basent sur les procédures d'addition de grands nombres. En même temps que les procédures de base, nous donnerons quelques exercices qui permettront de les tester au fur et à mesure qu'elles seront écrites.

Ecrire les procédures de saisie et d'affichage des grands nombres.
N´oubliez pas de ranger les chiffres de la droite vers la gauche

Un contrôle d'erreur est-il nécessaire pour corriger les erreurs de frappe de l'utilisateur?

Vérifier le fonctionnement de ces procédures en écrivant un programme qui saisit un grand nombre et l'affiche.

Est-ce que cette fonction de test doit être mise dans la bibliothèque ?

Ecrire trois procédures qui :

N´oubliez pas de tester le résultat.

Ecrire une procédure qui convertit une variable de type entière en grand nombre.

Ecrire une autre procédure qui fait la même chose pour une variable de type réel.

Ecrire une procédure inverse qui traduit un grand nombre en un réel.

Ecrire une procédure d'affectation qui recopie le contenu d'une variable grand nombre dans une autre variable de ce type.

Ecrire une procédure comparant deux grands nombres et retournant -1 si le premier nombre est plus petit, 0 s'ils sont égaux et + 1 si le second nombre est plus petit.

Tester la procédure. Est-ce que 030 = 30 ?



Ecrire une procédure d'addition, sans tenir compte du signe, de deux grands nombres.

Nous pouvons déjà traiter quelques problèmes.

La légende dit que le roi de Perse voulut récompenser l'inventeur du jeu d'echec. Il lui demanda quel cadeau lui ferait plaisir. L'inventeur demanda que le roi mit un grain de blé dans la première case de l'échiquier, puis deux grains dans la seconde, quatre grains dans la troisième. Ainsi de suite jusqu'à ce que l'échiquier soit rempli.

Calculer le nombre de grains de blé nécessaires pour remplir l'échiquier (qui comporte 64 cases).

Revenons à nos procédures de base.

Ecrire une procédure de soustraction, sans tenir compte du signe, de deux grands nombres.

Ecrire les procédures qui font l'addition et la soustraction signées de deux nombres.

Ecrire une procédure de multiplication d'un grand nombre par un scalaire.

Encore une petite pause dans l'écritures des procédures de base. Les quelques exercices suivants peuvent être résolus avec les procédures qui viennent d'être implantées.

Vérifier le bon fonctionnement des procédures en testant l'égalité suivante:

Vérifier que si l'on place un 1 à droite et à gauche de 112 359 550 561 797 752 809 on obtient un nombre 99 fois plus grand. Ce nombre est le plus petit connu qui possède cette propriété (Ca on ne vous demande pas de le vérifier).

Calculer la factorielle d´un nombre entier. Vérifier la formule de Stirling :

Revenons aux procédures des base

Ecrire une procédure de multiplication de deux grands nombres.

Ecrire une procédure de division d'un grand nombre par un scalaire en s'inspirant de la méthode utilisée pour faire les divisions sur une feuille de papier.
Cette procédure rend aussi le reste de la division.

Cet exercice permet de tester les procédures de division.

Quel est le premier terme de la suite qui n'est pas entier ?



Ce n´est pas la fin de la première partie, mais si vous avez rencontré des difficultés, vous pouvez vous arrêter là.

Ecrire une procédure de division de deux grands nombres.

Vérifier le bon fonctionnement des procédures en refaisant la multiplication à partir des résultats trouvés.

Fin de la première partie

Calcul de `e' et `pi'

Avec les primitives que nous venons de définir, nous pouvons calculer les valeurs de e et de p avec une grande précision. En fait, puisque nous n'avons défini que des calculs sur des entiers, nous calculerons e.10n et p.10n où n représente le nombre de chiffres que nous voulons obtenir.

Les mathématiciens ont prouvé que la suite

tend vers e quand n tend vers l'infini.

Ecrire un programme qui calcule la valeur de e. N'oubliez pas d'insérer à la fin du programme des instructions pour sauvegarder les données sur le disque ou pour les imprimer. Il serait dommage de perdre plusieurs heures de calcul!

I1 est intéressant de mesurer à quelle vitesse le programme converge vers e. Pour cela, faire un premier calcul de e qui va nous donner la valeur "exacte" puis reprendre le calcul avec la même précision et afficher à l'aide de xgraph la courbe de la fonction Un-e.

I1 est aussi intéressant de mesurer l'erreur de calcul. Les calculs qui devraient être faits sur des réels le sont sur un nombre fini de chiffres; des erreurs d'arrondi apparaissent. Pour les visualiser, calculer e avec une précision de 20 chiffres, puis avec une précision de 100 chiffres et comparer les 20 premiers chiffres des deux résultats. Conclusion ?

Après ce hors-d'oeuvre, nous allons passer au calcul des décimales de pi, Ce calcul est bien plus fastidieux que la recherche des décimales de e, car la convergence est beaucoup moins rapide.

La première formule pour calculer pi nous est donnée par Wallis. John Wallis (1616-1703) était un mathématicien anglais. Il est surtout connu pour avoir introduit les symboles x, <, et > utilisés de nos jours dans les mathématiques. La formule de Wallis pour pi est :

Puisque nous ne disposons que d'opérations entières pour résoudre cette équation, il faut effectuer le calcul du numérateur, le calcul du dénominateur, multiplier le numérateur par 10n et effectuer la division.

Que pensez-vous de la convergence de la suite ?

Une autre méthode pour calculer pi nous est donnée par Gottfried Leibniz (1646-1716). Elle revient à calculer le développement en série de la fonction arctg, ce qui donne la série suivante :

Or arctg (1) = p/4 , en remplaçant dans la formule on obtient:

En la programmant, vous pourrez vous rendre compte que cette série converge très lentement. On peut améliorer la convergence en regroupant deux par deux chacun des éléments de la série, on obtient les séries suivantes :

En faisant la moyenne on obtient la formule suivante :

Ecrire un programme implémentant cette formule et faites la même étude (convergence et erreur) que pour e.

Issac Newton (1642-1727) est parti du développement en série de la fonction arcsin(x) :

en remplaçant x par 1/2 on obtient arcsin (1/2) = p/6 et la série suivante :

Le premier calcul sur ordinateur a été effectué en 1949 sur un Eniac, il permit d'obtenir après 70 heures de calcul 2037 décimales. La formule suivante a été utilisée :
d'où la série suivante :

Cette formule avait déjà été utilisée par John Machin (1680 - 1752) pour obtenir les 100 premières décimales de pi. En 1974 J. Guilloud et M. Bouyer obtiennent après 22 heures et 11 minutes de calcul sur un CDC 7600 1 000 000 décimales en utilisant la formule :

Les résultats ont été publiés sous forme d'un volume de 415 pages contenant aussi des tests statistiques. Dans un entretien accordé au journal "Le petit Archimède" Jean Guilloud parle de son record.

LPA:
"Pourquoi calculer pi ?
JG:
C'était pour moi un exercice de programmation, j'aurais pu choisir un autre nombre mais e c'est trop facile et c (constante d'Euler) trop difficile ! et puis il y avait le record !
LPA:
Pourquoi vous êtes vous arrêté 1 000 000 ?
JG:
Parce que c'est un nombre rond !
LPA:
Mais alors si demain on en publie une de plus, vous perdez votre record ?
JG:
Ce n'est pas sûr, j'en ai gardé quelques-unes en réserve.
LPA:
Combien ?
JG:
Suffisamment !"
Et pour finir voila un texte qui peut être utile pour vérifier vos résultats:
Que j'aime à faire apprendre un nombre utile aux sages ! 
Glorieux Archimde, artiste ingénieux, 
Toi de qui Syracuse aime encore la gloire, 
Soit ton nom conservé par de savants grimoires ! 
Jadis, mystérieux, un problème bloquait 
Tout l'admirable procédé, l'oeuvre grandiose 
Que Pythagore découvrit aux anciens Grecs. 
O quadrature ! vieux tourment de philosophe ! 
Insoluble rondeur, trop longtemps vous avez 
Défié Pythagore et ses imitateurs. 
Comment intégrer l'espace plan circulaire ? 
Former un triangle auquel il équivaudra ? 
Nouvelle invention: Archimède inscrira 
Dedans un hexagone; appréciera son aire 
Fonction du rayon. Pas trop ne s'y tiendra: 
Dédoublera chaque élément antérieur; 
Toujours de l'orbe calculée approchera; 
Définira limite; enfin, l'arc, le limiteur 
De cet inquiétant cercle, ennemi trop rebelle ! 
Professeur, enseignez son problème avec zèle !...



Racine carrée

Nos ancêtres qui n'avaient pas de calculatrice connaissaient un algorithme pour extraire une racine carrée d'un nombre. Cet algorithme est assez proche de celui de la division entre deux nombres que nous avons définie précédemment:
Ecrire un programme qui calcule racine de 2 avec 1000 chiffres après la virgule.