Bibliothèque Bigint (bigbit)

Question

Je recherche une classe / bibliothèque c ++ fournissant des entiers de 1024 bits et plus, ainsi que des opérations sur bits telles que:  - peu de décalage,  - au niveau du bit OU / ET,  - position du premier bit zéro

la rapidité est cruciale, il devrait donc être implémenté avec un assemblage SIMD.

Answer 1

Il en existe plusieurs, dont GMP , mais pour des raisons de rapidité, le meilleur choix est TTmath . La décision de conception de TTmath d’utiliser des longueurs fixes basées sur des modèles lors de la compilation permet d’être assez rapide.

Answer 2

essayez la bibliothèque gmp . C'est une bibliothèque en C. À partir de GMP 4.0, un wrapper C ++ est fourni avec la version.

Answer 3

Pensez simplement à la multiplication d’entiers, la bibliothèque TTmath utilise l’algorithme Karatsuba, dont la complexité temporelle est $ O (n ^ {1.585}) $. L'algorithme le plus rapide est $ O (n log n log log n) $, en utilisant la FFT.