Int128 : une bibliothèque pour entiers sur 128 bits
Soyez le premier à donner votre avis sur cette source.
Vue 3 495 fois - Téléchargée 351 fois
Description
Int128 est une bibliothèque qui permet d'utiliser des entiers sur 128 bits ( ou 16 octets ), lesquels vont de -2^127 à 2^127-1, aussi facilement que les entiers natifs du langage C++ grâce à une classe spécialement développée pour cela. Chacun de ces entiers y est mémorisé par 2 entiers sur 64 bits : un int64_t et un uint64_t. La bibliothèque Int128 fournit principalement plusieurs constructeurs, l'affectation, les quatre opérations de base de l'arithmétique, l'exponentiation, la comparaison et la conversion en formats décimal et hexadécimal. Ces opérations et fonctions sont valides avec les entiers Int128, mais elles fonctionnent aussi entre les entiers Int128 et les entiers 64 bits ou 32 bits. Il y a deux cas de fin d'exécution en erreur dont la division par 0 : voir main.bat. Des fonctions supplémentaires peuvent assez facilement y être ajoutées : not, and, or, xor, les bit shifts, racine carrée ou même pgcd, ppcm et l'arithmétique modulaire, etc.
Contrairement aux bibliothèques GMP, NTL ou Boost qui permettent la multiprécison, c'est à dire l'emploi d'entiers de longueur aussi grande que nécessaire, Int128 ne permet que l'emploi d'entiers de longueur maximum 16 octets. Mais, l'avantage principal de Int128 est sa grande facilté d'emploi : il n'y a pas besoin d'un apprentissage compliqué. L'avantage secondaire est la maîtrise du code source, cependant les performances et l'exactitude sont peut être encore à contrôler, malgré les essais déjà effectués.
Pour en montrer l'emploi on a joint un programme qui vérifie que l'expression 4^n+6n-1 est divisible par 9, ce qui est vrai quelquesoit n. Ce programme en fait ici la démonstration pour n de 0 à 63. Avec des entiers sur 64 bits on est limité à 31.
Source :
// ---- fichier int128.hpp -- @author pgl10 ----
#ifndef INT128_HPP
#define INT128_HPP
#include <stdint.h>
#include <string>
class Int128 {
public:
~Int128();
Int128();
Int128(int a);
Int128(unsigned int a);
Int128(int64_t a);
Int128(uint64_t a);
Int128(int64_t a, uint64_t b);
Int128(const Int128& a);
int64_t getHi() const;
uint64_t getLo() const;
void setHi(const int64_t a);
void setLo(const uint64_t a);
Int128 operator - () const;
Int128 operator = (const Int128& a);
Int128 operator += (const Int128& a);
Int128 operator - (const Int128& a) const;
Int128 operator -= (const Int128& a);
Int128 operator *= (const Int128& a);
Int128 operator / (const Int128& a) const;
Int128 operator /= (const Int128& a);
Int128 operator % (const Int128& a) const;
Int128 operator %= (const Int128& a);
Int128 operator ++ ();
Int128 operator ++ (int);
Int128 operator -- ();
Int128 operator -- (int);
int signe() const;
std::string hexa() const;
std::string deci() const;
private:
int64_t _hi;
uint64_t _lo;
};
Int128 operator + (const Int128& l, const Int128& r);
Int128 operator - (const int& l, const Int128& r);
Int128 operator * (const Int128& l, const Int128& r);
bool operator == (const Int128& l, const Int128& r);
bool operator != (const Int128& l, const Int128& r);
std::ostream& operator << (std::ostream& ost, const Int128& v);
int cmp128(const Int128& a, const Int128& b);
Int128 pow128(const Int128& x, const int& n);
int64_t toInt(const Int128& a);
#endif // INT128_HPP
// ---- fichier main.cpp -- @author pgl10 ----
#include <iostream>
#include "int128.hpp"
void main() {
Int128 p, q;
std::cout << std::endl << "n : p = 4^n+6*n-1 = 9*q"
<< std::endl << std::endl;
for(int n=0; n<64; n++) {
p = pow128(4,n) + 6*n - 1;
q = p / 9;
if(p == 9*q)
std::cout << n << " : " << p << " = 9*" << q << std::endl;
}
std::cout << std::endl << std::endl;
}
- Messages postés
-
326
- Date d'inscription
- samedi 18 décembre 2004
- Statut
- Membre
- Dernière intervention
- 5 janvier 2021
2Il me semble que votre programme ci-dessus montre bien que votre union U64 permet de faire les calculs sur les entiers de 64 bits comme vous le souhaitez pour les valeurs positives. Mais que se passe-t-il pour les nombres négatifs avec cette représentation ? Pour cette raison, dans Int128 je représente un entier 128 bits par un int64_t (signé) et un uint64_t. Si les int64_t ont rendu obsolète votre ancien développement à base de U64, il en sera de même pour Int128 parce que les int128_t arrivent déjà avec certains compilateurs mais pas tous actuellement. Le mien : Visual Studio 2012 Express for Windows Desktop en français ne les a pas. Si vous souhaitez développer votre solution à base de l'union U128 pour les entiers positifs sur 128 bits cela devrait fonctionner. Je ne sais pas si vous souhaitez traiter aussi les nombres entiers négatifs sur 128 bits. Si oui, quelle sera la représentation du signe ? D'autres avis éventuels sont les bienvenus.
Merci pour votre réponse.
J'espère ne pas "abuser" en me permettant de présenter une autre "idée":
Il y a bien longtemps, lorsque les nombres sur 64 bits n'étaient qu'un rêve, j'avais fait des routines pour simuler ces "immenses" entiers.
Malheureusement, devenu inutile par la suite, je n'en ai pas gardé les sources.
Je me souviens seulement que j'avais utilisé la notion union de C, qui devait correspondre à:
union U64 { uint32_t u32[2]; uint16_t u16[4]; };Cela me permettait d'écrire les routines d'addition, de multiplication, etc, sans "encombrer" les codes de shifts, de masques et d'opérations binaires.
Dans le code qui suit, j'ai ajouté à la fin dans l'union
uint64_t u64
pour pouvoir "vérifier" (aujourd'hui, en 64 bits) certaines valeurs:
#include <stdint.h> #include <stdio.h> union U64 { uint32_t u32[2]; uint16_t u16[4]; uint64_t u64; }; int main() { printf("sizeof(U64) = %i\n\n",sizeof(U64)); // L'initialisation se en fonction de la première variable de l'union U64 x = {654321,171717}; // correspond à 279172874257: x.32[0]=654321; x.u32[1]=17 printf("x.u16[3] = %u, x.u16[2] = %u, ",x.u16[3],x.u16[2]); printf("x.u16[1] = %u, x.u16[0] = %u",x.u16[1],x.u16[0]); printf("\nx.u32[1] = %u, x.u32[0] = %u\n",x.u32[1],x.u32[0]); printf("x.u64 = %llu\n\n",x.u64); printf("x = x.u16[0] + 2^16*x.u16[1] + 2^32*x.u16[2] + 2^48*x.u16[3] = %llu\n" ,x.u16[0]+0X10000*x.u16[1]+0X100000000*x.u16[2]+0X100000000*x.u16[3]); printf("x = x.u32[0] + 2^32*x.u32[1] = %llu\n",x.u32[0]+0X100000000*x.u32[1]); printf("x = x.u64 = %llu",x.u64); getchar(); } /* Output: sizeof(U64) = 8 x.u16[3] = 2, x.u16[2] = 40645, x.u16[1] = 9, x.u16[0] = 64497 x.u32[1] = 171717, x.u32[0] = 654321 x.u64 = 737518899821553 x = x.u16[0] + 2^16*x.u16[1] + 2^32*x.u16[2] + 2^48*x.u16[3] = 174577536334833 x = x.u32[0] + 2^32*x.u32[1] = 737518899821553 x = x.u64 = 737518899821553 */Pour laisser au compilateur les opérations "obscures" sur les bits, pourrait-on d'une manière analogue simuler les entiers de 128 bits en utilisant:
union U128 { uint64_t u64[2]; uint32_t u32[4]; };?Merci d'avance pour votre avis.
Bonne continuation ...
- Messages postés
-
326
- Date d'inscription
- samedi 18 décembre 2004
- Statut
- Membre
- Dernière intervention
- 5 janvier 2021
2Je suis admiratif pour cet examen très attentif. J'ai donc compté, moi aussi, le nombre de multiplications effectuées dans la fonction dix() pendant le test de Int128 et j'ai trouvé moi aussi 94848. J'ai aussi compté le nombre de fois où dix() a été appelée et j'ai trouvé 4992. En effet cette fonction est appelée plusieurs fois pendant l'exécution de decistr(). Ce qui montre que dix(int n){} qui calcule 10^n effectue bien, comme attendu, n multiplications à chaque appel. C'est pourquoi je retiens la nouvelle version modifiée de dix() comme vous l'avez proposée : elle est plus performante. Merci pour ce commentaire et cette amélioration.
En parcourant le code source que vous proposez, mon attention a été attirée par la fonction:
Int128 dix(int n) { // calcul de : 10^n Int128 x = 1; int i = 0; while(i<n) { x = x * 10; i = i + 1; } return x; }qui n'est utilisée que dans Int128::decistr(), c'est-à-dire pour la "transformation en décimales".En comptant le nombre de multiplications x = x * 10 qui y sont calculées lors du test, j'arrive à 94848 !
Pourquoi ne pas appliquer le même algorithme que vous utilisez plus bas:
Int128 pow128(Int128 x, int n) { if (n == 0) return 1; if (n == 1) return x; Int128 t = pow128(x, n/2); if (n%2 == 0) return t*t; else return x*t*t; }Ce qui pourrait donner:
Int128 dix(int n) { if (n == 0) return 1; if (n == 1) return 10; Int128 t = dix(n/2); if (n%2 == 0) return t*t; return t*t*10; }En utilisant cette fonction, le nombre de multiplications est réduit à 24448 !
Ce qui me semble toujours énorme !
Comme la fonction dix(n) est toujours utilisée avec (0 <= n <= 38), on peut réduire ce nombre de multiplications à zéro (ou 38), en donnant un tableau de 39 valeurs précalculées (*).
(*) Remarque sur la "météo": attention à l'orage !
En ce qui concerne l'algorithme utilisé dans Int128 pow128(Int128 x, int n), je ne le connaissais pas et il semble être plus efficace que l'algorithme le plus souvent proposé:
Int128 pow128(Int128 x, int n) { // n>=0 Int128 p = 1; for (; n>0; n>>=1) { if (n&1) p *= x; x *= x; } return p; }En effet, votre test effectue 513 multiplications avec la fonction ci-dessus, alors qu'avec celle que vous proposez, il n'en calcule que 387 !Merci pour vos apports et votre fair-play.
- Messages postés
-
326
- Date d'inscription
- samedi 18 décembre 2004
- Statut
- Membre
- Dernière intervention
- 5 janvier 2021
2Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.