Int128 : une bibliothèque pour entiers sur 128 bits.
pgl10
Messages postés
380
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
29 octobre 2023
-
1 oct. 2014 à 20:54
pgl10 Messages postés 380 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 29 octobre 2023 - 26 oct. 2014 à 16:44
pgl10 Messages postés 380 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 29 octobre 2023 - 26 oct. 2014 à 16:44
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/100764-int128-une-bibliotheque-pour-entiers-sur-128-bits
https://codes-sources.commentcamarche.net/source/100764-int128-une-bibliotheque-pour-entiers-sur-128-bits
26 oct. 2014 à 16:44
Il 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.
26 oct. 2014 à 13:08
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 ...
25 oct. 2014 à 13:08
Je 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.
25 oct. 2014 à 10:59
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.
2 oct. 2014 à 14:54
2 oct. 2014 à 14:02
Il y a fort heureusement une solution, qui est d'écrire les opérateurs commutatifs en dehors de la classe.
Par exemple: Int128 operator+(const Int128& l, const Int128& r);
Ainsi, x + 10 devient operator+(x, 10) et 10 + x devient operator+(10, x), ce qui est valide.
Bien entendu, il ne faut plus avoir d'operator+ au sein de la classe, sinon il y a ambiguïté (et ça ne compilera pas).
D'une manière générale:
- Opérateurs commutatifs: en dehors de la classe (+, *, ==, != /, etc...)
- Opérateurs non commutatifs: au sein de la classe (!, ++, --, +=, -=, %=, etc...).
C'est vrai, mais c'est faisable par surcharge d'opérateurs, c'est le point que je voulais mettre en avant :).
2 oct. 2014 à 13:27
Merci pour ces remarques et observations très intéressantes. J'ai aussi plusieurs modifications à effectuer, je vais donc y inclure cela. Mais je crois que je ne pourrai pas appliquer tout, en particulier shr128 doit opérer sur un Int128 et l'opérateur >> pour un Int128 n'est pas encore disponible et de même std::cout << std::dec << ... ne peut pas fonctionner sur un Int128 actuellement. En plus je bute aussi sur le problème suivant : Si x est un Int128 et n un int, alors x+n ou x*n ou ... sont des expressions valides et je sais pourquoi. Mais n+x ou n*x sont des expressions refusées par le compilateur. C'est normal, il n'y a nulle part ce qu'il faut pour les faire accepter. Et je souhaite obtenir le même Int128 comme résultat des expressions n+x ou n*x ... identiquement à x+n ou x*n ... Je cherche ce qu'il faut pour cela. Quant à l'opérateur << pour un Int128 il n'est pas encore disponible mais je crois que c'est aussi à faire ! Cordialement, pgl10
Modifié par cptpingu le 2/10/2014 à 10:40
Pas remarque particulière, c'est propre. Quelques petits détails, néanmoins:
À la place de:
On peut utiliser:
namespace { const uint64_t ALLBITS = 0xFFFFFFFFFFFFFFFFLL; const uint64_t HIGHBITS = 0x8000000000000000LL; } // namespaceCe qui permet d'éviter une macro, et d'avoir des constantes fortement typées.
Plutôt que plusplus() et moinsmoins(), on peut utiliser:
Int128& operator++() // prefix ++ { _hi = _hi + (_lo == ALLBITS); _lo = _lo + 1; } Int128 operator++(int) // postfix ++ { return operator++(); }Idem pour shr128, qui peut être remplacé par operator>> et shl par operator<<.
Pour convertir en hexa, octal ou décimal, il n'est normalement pas nécessaire d'avoir de méthodes pour cela. Il existe déjà std::dec, std::oct et std::hex.
Exemple:
On pourrait bien sur utiliser cette méthode pour mettre dans un std::ostringstream, et en récupérer le string.