|
La multi-précision en C++ est la possibilité d'utiliser des variables qui représentent des nombres entiers, ou même des rationnels, ayant autant de chiffres significatifs que nécessaire. En standard les compilateurs C++ actuels permettent d'utiliser les int16_t, les int_32_t et les int64_t. Il y a déjà des compilateurs C++ qui permettent d'utiliser les int128_t. Chacune de ces représentations imposent que l'entier traité soit compris entre certaines limites, par exemple : les int64_t vont de -(2^63) à (2^63)-1. Si on veut faire des calculs avec des entiers aussi grands que nécessaire, il faut utiliser une bibliothèque prévue pour cela. On trouve facilement sur Internet beaucoup de bibliothèques de ce genre. Les plus connues sont : GMP, MPIR, MPFR, NTL, BOOST, MIRACL, PARI, FLINT, LiDIA et LIP. A noter que LIP, développée par Arjen K. Lenstra est l'une des plus anciennes et n'est plus utilisée maintenant. Les autres sont maintenues par leurs auteurs ou par un groupe spécifique de programmeurs. En général le source est disponible. En raison des nombreux modes de compilation et d'utilisation : Debug ou Release, Win32 ou x64 et DLL multithread (/MD) ou Multithread (/MT), ou bien avec GCC d'une part et d'autre part pour Linux, Macintosh ou Android, il est souvent préférable ou même exigé d'en faire soi même la compilation, ce qui n'est pas toujours facile. En plus des solutions classiques bien connues et maintenues, on trouve aussi sur Internet un très grand nombre de solutions de ce type développées occasionnellement par divers auteurs. Ce genre de développement est souvent demandé aux étudiants en travaux pratiques, ce qui rend disponibles des résultats d'étudiants ou de professeurs. FLINT et MpNT en sont des exemples réputés et beaucoup d'autres se nomment Bignum, BigInt, BigInteger ou Integer. Parmi d'autres, le livre de Steven S. Skiena : The Algorithm Design MANUAL, Second Edition, 2008, 730 pages, facilite la construction de ces bibliothèques. Le livre de Henri Cohen, l'auteur de PARI : A Course in Computational Algebraic Number Theory, 1996, 545 pages, est aussi un grand classique, mais il est un peu plus ancien. Pour une présentation rapide avec une comparaison de quelques unes de ces bibliothèques, on peut consulter le document suivant soit en téléchargement soit en présentation résumée. GMP a la réputation d'être l'une des plus connues et des plus performantes de ces solutions. Mais le groupe des développeurs qui maintient GMP préfère se préoccuper seulement de son utilisation sous Linux. C'est pourquoi son utilisation sous Windows est possible mais assez difficile. Pour cette raison, un autre groupe de développeurs maintient, à partir de GMP, MPIR qui est prévu pour fonctionner aussi sous Windows tout en conservant une très bonne compatibilité avec GMP. On trouvera donc ci-après un petit logiciel de factorisation d'un grand entier, utilisant l'algorithme rho de Pollard, écrit successivement avec GMP, MPIR et la bibliothèque BigInteger pour en comparer les utilisations. On y précise à chaque fois le téléchargement, la documentation, l'adaptation au projet, les modalités de compilation, le source, l'exécutable, l'exemple d'utilisation et les performances obtenues. Retour |