Bibliothèque d'entiers 128 bits la plus rapide

Question

Je travaille sur une application de calcul numérique à forte consommation de CPU. Sans entrer dans de nombreux détails, c'est un projet de recherche mathématique computationnelle qui implique le calcul d'une certaine fonction f (x) pour un grand entier x. À l'heure actuelle, tout est implémenté en mode C++ en mode x64, en utilisant des octets 64 bits natifs. Cela me limite à x < 2^64 ~ 1.8 * 10^19. Je veux aller plus loin, pour ce faire, j'ai besoin d'une bibliothèque qui fait de l'arithmétique 128 bits. Et ça doit être très rapide. En particulier, les divisions entières devraient être rapides. Sinon, je serai assis ici en attendant les résultats jusqu'à Thanksgiving. Et je préfère ne pas réinventer la roue. J'ai trouvé une liste de ~ 20 grandes bibliothèques d'entiers sur Wikipedia, mais la plupart d'entre elles semblent cibler des nombres de précision arbitraires, ce qui est exagéré pour ma tâche, et je n'ai pas besoin de coûts supplémentaires associés à cela.

Est-ce que quelqu'un sait quelle bibliothèque peut fonctionner sur des entiers de 128 bits le plus rapidement?

Answer 1

Vous n'avez pas mentionné vos exigences de plateforme/portabilité. Si vous êtes prêt à utiliser gcc ou clang, sur les plates-formes 64 bits, ils ont un type de 128 bits intégré qui viennent gratuitement, __uint128_t et __int128_t. Peut-être que d'autres plateformes ont des extensions de type similaires.

Dans tous les cas il devrait être possible de trouver le code générique correspondant dans les gcc sources qui assemble deux des nombres entiers de largeur N pour synthétiser un nombre entier de largeur 2N. Ce serait probablement un bon point de départ pour faire une bibliothèque autonome à cette fin.

Answer 2

Cela peut ne pas être pour tout le monde, mais ce que je ferais est de choisir la bibliothèque entière arbitraire la plus performante avec le code source et convenant au travail, et de la hacker pour des tailles entières fixes. Changez certaines variables "nbits" en 128 codées en dur. Il alloue probablement de la mémoire à l'exécution, ne connaissant pas le nombre d'octets jusque-là. Changez-le pour utiliser struct avec des données sur place, en enregistrant un déréférencement de pointeur chaque fois que des données sont lues. Dérouler certaines boucles critiques à la main. Hard-code toute autre chose qui pourrait être critique. Ensuite, le compilateur aura probablement plus de temps pour optimiser les choses. Bien sûr, une grande partie de ce sera l'assemblage, en utilisant SIMD fantaisie avec quelle que soit la technologie utilisée cette semaine.

Ce serait amusant! Mais ensuite, en tant que programmeur, j'ai commencé avec du code machine et des trucs de très bas niveau.

Mais pour ceux qui ne sont pas aussi fous que moi, peut-être que l'une des bibliothèques disponibles utilise des modèles ou a un moyen de générer du code personnalisé à une certaine taille. Et, certains compilateurs ont un type entier "long long" qui pourrait convenir.

Answer 3

La bibliothèque ttmath fait ce que vous voulez.