Historique du paquetage Big_Number
Dernière modification : 8 juillet 2001
Retour vers la page principale
Pourquoi ce paquetage?
En 1986, je travaillais sur un programme en Pascal qui permettait de résoudre un système d´équations linéaires à coefficients entiers. Le plus souvent, il fonctionnait correctement, mais des erreurs apparaissaient parfois : les dépassements de capacité de calcul (parfois appelés débordements ou overflows) n´étaient pas détectés, et le programme se terminait en renvoyant de faux résultats. J´ai alors essayé certaines astuces en assembleur, ce qui permettait effectivement de les déceler, mais dans ce cas le programme indiquait qu´il ne pouvait pas poursuivre les calculs : assez frustrant, car je n´avais toujours pas la possibilité de travailler sur des entiers plus grands que ceux définis par ce compilateur. J´ai alors arrété le développement de ce programme.
Entre 1994 et 1996, alors que j´étais étudiant en médecine, j´ai appris le langage Ada durant mon temps libre. Ce langage m'a vraiment intérressé car il a de nombreuses fonctionnalités supplémentaires par rapport au Pascal (par exemple la notion d'algorithme générique et celle des exceptions). Il faut d´ailleurs noter que les exceptions étaient disponibles en Ada dès sa première norme, en 1983, puis reprises, nettement plus tard, dans le langage C. C´est alors, en 1996, que j´ai commencé à travailler sur certains des algorithmes de fonctions et procédures présents dans le paquetage Big_Number.
A cette époque, en raison de mes connaissances assez limitées de ce genre d´algorithme, le développement de ce paquetage était assez lent. En particulier, j´ai eu quelques problèmes pour écrire l´algorithme de division. La première version que j´ai considérée comme acceptable (version 0.00) était datée du premier mai 1998, mais la version actuelle (0.21) peut toujours être améliorée.
Retour au début de cette page
Les différentes versions de ce paquetage
Version 0.00
Cette première beta version n´a pas été diffusée (premier mai 1998).
Version 0.01
Cette version, datée du 24 mai 1998, a été la première distribuée à quelques amis. Elle comportait quelques optimisations mineures en terme de vitesse d´exécution. Elle présentait cependant quelques
erreurs, découvertes durant le calcul du nombre Pi, et qui ont été corrigées à partir de la version 0.03.
Retour au début de cette page
Version 0.02
Cette version 0.02 (23 juin 1998) contenait certaines améliorations dans quelques algorithmes (principalement dans les fonctions "+", "-" et Big_Div, dans le sous-paquetage Unsigned_Number). Elle n´a pas été diffusée.
Retour au début de cette page
Version 0.03
Cette version était datée du 30 août 1999. Deux erreurs dans la procédure Big_Div, ainsi que quelques autres erreurs, ont été corrigées : dorénavant, le nombre Pi semblait être correctement calculé. D´importantes améliorations ont été faites dans la fonction "-"(x, y : IN Big_Unsigned) RETURN Big_Unsigned (améliorations mineures de quelques autres fonctions et procédures).
J´ai ajouté toutes les procédures d´entrée/sortie vers des fichiers texte. Les variables de type Big_Unsigned et Big_Signed ne peuvent plus être converties en variable de type STRING, mais uniquement en variables de type UNBOUNDED_STRING, car cela permet des algorithmes plus simples et évite les problèmes liés à la limitation de la taille des variables de type STRING. De même, pour toutes les entrées/sorties, j´utilise des variables intermédaires de type UNBOUNDED_STRING (au lieu du type STRING).
La fonction Float_in_UString2Fraction a été ajoutée dans le sous-paquetage Fraction : elle permet de convertir en fraction un nombre réel (contenu dans une INBOUNDED_STRING).
Retour au début de cette page
Version 0.04
Cette version était datée du 26 septembre 1999. Les types Big_Signed, Big_Unsigned et Fraction sont maintenant privés : cela permet une meilleure sécurité, en évitant une manipulation dangereuse des variables de ces types dans les programmes utilisateurs.
De même, comme les variables de ces 3 types ne peuvent plus être modifiées en dehors du paquetage lui-même, certains appels de la fonction Simplify_Fraction, devenus superflus, ont pu être enlevés : cela permet une amélioration sensible de la plupart des fonctions du sous-paquetage Big_Fraction.
Une optimisation mineure a été réalisé dans la fonction "/"(x, y : IN Fraction) RETURN Fraction, et j´ai commencé à travailler sur le sous-paquetage Big_Unsigned_Random (inclu alors seulement sous forme de commentaires).
Retour au début de cette page
Version 0.05
Cette version, en date du 6 novembre 1999, a été la première diffusée sur Internet.
Certaines améliorations en terme de vitesse d'exécution ont été faites dans la procédure Big_Div(x, y : IN Big_Unsigned; Quot, Remainder : OUT Big_Unsigned) et dans la fonction "-"(x, y : IN Big_Unsigned) RETURN Big_Unsigned.
La fonction "+"(x, y : IN Fraction) a été réécrite et améliorée.
Retour au début de cette page
Version 0.06
Cette version, en date du 22 décembre 1999, a été diffusée alors que je travaillais déjà sur la version 0.07. Elle apporte d´importantes améliorations dans la procédure Big_Div(x, y : IN Big_Unsigned; Quot, Remainder : OUT Big_Unsigned).
D´autres améliorations ont été faites dans les procédures Inc(x : IN OUT Big_Unsigned) et Dec(x : IN OUT Big_Unsigned), et les procédures Inc(x : IN OUT Big_Signed) et Dec(x : IN OUT Big_Signed) ont été ajoutées.
Retour au début de cette page
Version 0.07
Cette version, en date du 20 février 2000, apporte des optimisations dans les fonctions "*"(x,y : IN Big_Unsigned) et "<"(x,y : IN Big_Signed).
Une erreur dans la fonction "+"(x,y : IN Big_Unsigned) a été corrigée.
Dans la procédure Big_Div(x, y : IN Big_Unsigned; Quot, Remainder : OUT Big_Unsigned), l´algorithme de la fonction Guess a été complétement réécrit et est dorénavant plus élégant (il n´y a plus de calculs intermédiaires sur des nombres rééls).
Quelques améliorations ont été faites dans les fonctions "/"(x : IN Fraction; y : IN Big_Unsigned) RETURN Fraction et
"*"(x : IN Fraction; y : IN Big_Unsigned) RETURN Fraction.
Un paquetage mathématique concernant les nombres réels, inclus dans les clauses "USE WITH" des programmes exemples, n´était pas nécessaire, et a donc été enlevé de cette distribution et des suivantes. Le paquetage Strings a également été enlevé, et sa fonction Del_Spaces a été incorporée dans le sous-paquetage String_Conversion : toutes les autres fonctions du paquetage Strings n´étaient pas nécessaires. Ces changements permettent des temps de compilations plus courts, et des executables plus petits, avec mon compilateur Ada (GNAT version 3.12).
Des fichiers MAKEFILE ont été optimisés pour les différentes distributions du compilateur GNAT : MAKEFILE.DOS pour les syté,mes d´exploitation avec des noms de fichier au format 8+3, et MAKEFILE.OTH pour les syté,mes d´exploitation autorisant les noms de fichier longs.
Dans les programmes d´exemple, amélioration de la troisième méthode de calcul du nombre Pi.
Retour au début de cette page
Version 0.08
Cette version, datée du 4 mars 2000, a été diffusée suite à la correction de certaines erreurs dans la conversion de variables de type STRING ou UNBOUNDED_STRING vers des variables de type Big_Unsigned ou Big_Signed.
Le sous-paquetage Big_unsigned_Number est maintenant fonctionnel (il était inclus sous forme de commentaires dans les versions 0.04 à 0.07) : je ne peux cependant pas garantir qu´il génère des nombres parfaitement "au hasard".
Les fonctions "AND"(x,y : IN Big_Unsigned) RETURN Big_Unsigned et "XOR"(x,y : IN Big_Unsigned) RETURN Big_Unsigned ont ét;é ajoutées.
Retour au début de cette page
Version 0.09
Cette version, datée du 7 avril 2000, a été diffusée suite à l´amélioration de la portabilité du paquetage pour des environnements (compilateur et/ou ordinateur) différents.
Retour au début de cette page
Version 0.10
Cette version, datée du 22 avril 2000, présente une correction de la fonction "-"(x, y : IN Big_Signed) RETURN Big_Signed : quand x et y sont égaux et tous deux positifs, le résultat est égal à Big_Signed_Zero, c´est à dire 0 avec un signe positif (le signe était auparavant négatif).
Retour au début de cette page
Version 0.11
Cette version, datée du 25 avril 2000, met à jour certains commentaires et corrige une erreur dans la fonction "<="(x, y : IN Big_Signed) RETURN BOOLEAN.
Retour au début de cette page
Version 0.12
Cette version, datée du 7 mai 2000, propose une amélioration importante de la procédure Inc(x : IN Big_Unsigned).
Retour au début de cette page
Versions 0.13 et 0.14
Ces 2 versions, datées respectivement des 4 et 11 juin 2000, apportent des améliorations mineures de la procédure Dec(x : IN OUT Big_Unsigned) et de la fonction "+"(x, y : IN Big_Unsigned) RETURN Big_Unsigned. Elles n´ont pas été diffusées en raison des tests que j´ai réalisés de façon incomplète.
Retour au début de cette page
Version 0.15
Cette version du 17 juillet 2000 apporte des corrections d´erreurs dans la fonction "**"(x : IN Fraction; y : IN My_Type) RETURN Fraction;, ainsi que dans toutes les fonctions du sous-paquetage Generic_Conversion et dans les procédures PUT(x : IN Fraction) et PUT(File : IN FILE_TYPE; x : Fraction). La fonction "**"(x : IN Fraction; y : IN Big_Unsigned) RETURN Fraction a été améliorée de façon importante, alors que d´autres gains mineurs de performance ont été obtenus dans les fonctions "/"(x : IN Fraction; y : Big_Signed) RETURN Fraction, Special_mul(x : IN Big_Unsigned; y : IN My_Type; Left_Shift : IN Index_Type) RETURN Big_Unsigned, "*"(x, y : IN Big_Unsigned) RETURN Big_Unsigned, Random(x : IN Big_Unsigned) RETURN Big_Unsigned; "<"(Left, Right : IN Fraction) RETURN BOOLEAN, "*"(x : IN Fraction; y : Big_Signed) RETURN Fraction, "+"(x, y : IN Fraction) RETURN Fraction, "*"(x, y : IN Fraction) RETURN Fraction; ainsi que dans la procédure Big_Div(x,y : IN Big_Unsigned; Quot,Remainder : OUT Big_Unsigned). Les fonctions Opposite(x : IN Fraction) RETURN Fraction, Absolute(x : IN Fraction) RETURN Fraction and Is_Null(x : IN Fraction) RETURN BOOLEAN ont été ajoutées, ainsi que les procédures Get_Line(x : OUT Fraction) et Get_Line(File : IN FILE_TYPE; x : OUT Fraction) et certaines fonctions statistiques : NCR(x,y : IN Big_Unsigned) RETURN Big_Unsigned, NPR(x,y : IN Big_Unsigned) RETURN Big_Unsigned et K(x,y : IN Big_Unsigned) RETURN Big_Unsigned.
Retour au début de cette page
Version 0.16
Dans cette version du 21 aout 2000, seuls les programmes exemples ont été modifiées : en effet, les méthodes de calcul du nombre Pi sont dorénavant beaucoup plus rapides.
Retour au début de cette page
Version 0.17
Dans cette version du 24 septembre 2000, des améliorations mineures ont été apportées dans les fonctions "+"(x, y : IN Fraction) RETURN Fraction; et Short_Div(x : IN Big_Unsigned; y : IN My_Type; Quot : OUT Big_Unsigned; Remainder : OUT My_Type);.
Retour au début de cette page
Version 0.18
Cette version du 17 décembre 2000 propose une nouvelle fonction : Number_of_Bytes(x : IN Big_Unsigned) RETURN Largest_Unsigned; dans le sous-paquetage Unsigned_Number.
Retour au début de cette page
Version 0.19
Cette version du 29 décembre 2000 corrige une erreur dans la fonction : Shift_Left(x : IN Big_Unsigned; Nb : IN Index_Type) RETURN Big_Unsigned; dans le sous-paquetage Unsigned_Number.
Retour au début de cette page
Version 0.20
Cette version du 24 janvier 2001 apporte certaines corrections dans les différentes méthodes examples pour calculer le nombre Pi, où j´ai ajouté certains fichiers manquants. J´ai également ajouté certaines fonctions annexes comme Number_of_bits(x : IN Big_Unsigned) RETURN Largest_Unsigned;, Number_of_bytes(x : IN Big_Signed) RETURN Largest_Unsigned; et Number_of_bits(x : IN Big_Signed) RETURN Largest_Unsigned;
Retour au début de cette page
Version 0.21
Cette version du 4 mars 2001 corrige 2 erreurs dans la fonction Float_in_UString2Fraction(). La premiere a été découverte et corrigée par Young A.R. et concernait une mauvaise prise en charge du signe du résultat. J´ai découvert la seconde le même jour lors des tests : cela concernait la prise en charge de la période.
Retour au début de cette page
Version 0.22
Dans cette version du 12 mars 2001, j´ai légérement amélioré la fonction Big_Div(x,y : IN Big_Unsigned; Quot,Remainder : OUT Big_Unsigned);, en corrigeant également une erreur potentelle de son algorithme.
Retour au début de cette page
Version 0.23
Dans cette version du 14 avril 2001, j´ai amélioré la vitesse d´exécution, dans certains cas, de la fonction "<"(Left, Right : IN Fraction) RETURN BOOLEAN. La fonction Mod_Number2Big_Signed a été corrigée : quand le paramètre vaut zéro, le signe du résultat est défini comme positif.
Retour au début de cette page
Version 0.24
Dans cette version du 18 avril 2001, j´ai encore amélioré la vitesse d´exécution, dans certains cas, de la fonction "<"(Left, Right : IN Fraction) RETURN BOOLEAN.
Retour au début de cette page
Version 0.25
Dans cette version du 30 avril 2001, j´ai modifié légérement l´algorithme de la fonction "<"(Left, Right : IN Fraction) RETURN BOOLEAN. J´ai corrigé des erreurs dans les fonctions Opposite(x : IN Big_Signed) RETURN Big_Signed; and
Opposite(x : IN Fraction) RETURN Fraction;
Retour au début de cette page
Version 0.26
Dans cette version du 16 juin 2001, j´ai simplifié et optimisé l´algorithme de la fonction "-"(x, y : IN Big_Signed) RETURN Big_Signed. J´ai modifié légérement la function "+"(x, y : IN Fraction) RETURN Fraction;
Retour au début de cette page
Version 0.27
Avec cette version du 25 juin 2001, j´ai amélioré légérement la procédure Dec(x : IN OUT Big_Signed); et j´ai corrigé 2 erreurs dans la procédure Inc(x : IN OUT Big_Signed);
Retour au début de cette page
Version 0.28
Cette version du 8 juillet 2001 apporte une légère optimisation dans la fonction "+"(x, y : IN Big_Signed) RETURN Big_Signed; et une correction de 2 erreurs dans la fonction "<"(Left, Right : IN Big_Signed) RETURN BOOLEAN;
Retour au début de cette page
Ce que je prévois de faire
De nombreuses fonctionnalités supplémentaires peuvent être ajoutées à ce paquetage. Par exemple, il pourrait s´agir de fonctions et procédures pour la cryptographie. D´autres améliorations en terme de vitesse, et
des structures de données plus souples, pourraient être les bienvenues : par exemple, actuellement, chaque instanciation de ce paquetage ne permet d´utiliser qu´un seul type de grands entiers ou de fractions, limités en taille.
Retour au début de cette page