Représentant 128 bits en C++

Question

Quelle est la meilleure façon de représenter un nombre de 128 bits en C++? Il doit se comporter comme de près pour les types numériques intégrés que possible (c'est à dire l'appui de tous les opérateurs arithmétiques, etc).

Je pensais à la construction d'une classe qui avait 2 64 bits ou 4 32 bits. Ou peut-être juste la création d'un bloc de 128 bits de la mémoire et de tout faire moi-même.

Est-il plus facile/plus façon standard, ou quelque chose que je suis moins susceptibles de le visser en place lors de la mise en œuvre moi-même? :)

Il serait bien aussi si il pourrait être étendu à 256 bits, 512 bits, etc...

Answer 1

J'ai fait un uint128 classe avant, vous pouvez le vérifier sur: http://www.codef00.com/code/uint128.h.

Elle est dépendante sur un coup de pouce pour fournir automatiquement toutes les variantes de mathématiques les opérateurs, de sorte qu'il doit soutenir tout un natif unsigned int type ne.

Il y a quelques petites extensions construites en tape comme de l'initialisation avec une chaîne comme ceci:

uint128_t x("12345678901234567890");

Il y a une commodité macro qui fonctionne de même pour ceux en C99 que vous pouvez utiliser comme ceci:

uint128_t x = U128_C(12345678901234567890);

Answer 2

C'est un peu un cas particulier, surtout depuis que vous n'avez pas spécifié de quelle plate-forme(s) que vous cherchez, mais avec GCC, vous pouvez utiliser ce qu'on appelle le mode(TI) pour obtenir (synthétisé) 128-bit opérations, par exemple:

   typedef unsigned int uint128_t __attribute__((mode(TI)));

   uint64_t x = 0xABCDEF01234568;
   uint64_t y = ~x;

   uint128_t result = ((uint128_t) x * y);

   printf("%016llX * %016llX -> ", x, y);

   uint64_t r1 = (result >> 64);
   uint64_t r2 = result;

   printf("%016llX %016llX\n", r1, r2);

Cela ne fonctionne que sur les processeurs 64 bits, cependant.

D'une façon ou d'une autre, vous êtes à la recherche à de multiples précision arithmétique pour résoudre ce problème. mode(TI) entraîne le compilateur pour générer les opérations pour vous, sinon, ils doivent être écrit explicitement.

Vous pouvez utiliser un bigint paquet; ceux en C++ je sais d'inclure le numéro de la théorie des paquets de LiDIA et NTL, et le type bigint colis utilisés pour le code de chiffrement en Crypto++ et Botan). Plus bien sûr, il est GnuMP, qui est la forme canonique de C bibliothèque MPI (et il a un wrapper C++, bien qu'il semblait mal documenté dernière fois que j'ai regardé). Toutes ces activités sont conçues pour être rapides, mais aussi probablement à l'écoute pour les plus grands (+de 1000 bits) de nombres, de sorte à 128 bits, vous pouvez avoir affaire avec une surcharge importante. (D'un autre côté, vous ne dites pas si ce qui compte ou pas). Et tous d'entre eux (contrairement à la bigint-rpc paquet, qui est GPL, sont soit BSD ou GPL) - vous ne savez pas si c'est important - mais il peut avoir son importance.

Vous pouvez également écrire une coutume uint128_t genre de type; en général, une telle classe serait de mettre en application les mêmes algorithmes que régulièrement MPI classe, tout codé en dur pour avoir seulement 2 ou 4 éléments. Si vous êtes curieux de savoir comment mettre en œuvre ces algorithmes, une bonne référence est le Chapitre 14 du Manuel de la Cryptographie Appliquée

Bien sûr, faire cela à la main est plus facile si vous n'avez pas réellement besoin de toutes les opérations arithmétiques (division et modulo, en particulier, sont plutôt difficiles). Par exemple, si vous avez juste besoin de garder une trace d'un compteur qui pourrait hypothétiquement dépassement de 64 bits, vous pouvez simplement représenté comme une paire de 64 bits de long longs et les faire porter par la main:

unsigned long long ctrs[2] = { 0 };

void increment() {
   ++ctrs[0];
   if(!ctrs[0]) // overflow
     ++ctrs[1];
}

Ce qui bien sûr va être beaucoup plus simple à traiter que d'un général MPI paquet ou une coutume uint128_t classe.

Answer 3

Rechercher dans d'autres bibliothèques qui ont été développés. Beaucoup de gens ont voulais faire avant de vous. :D

Essayez de type bigint C++

Answer 4

Ne pas réinventer la roue -- je suis certain que d'autres personnes ont déjà résolu ce problème, bien que je ne peux pas citer toutes les solutions sur le dessus de ma tête. GMP peut certainement résoudre votre problème, même si c'est exagéré de taille fixe entiers, et c'est aussi un peu lourd à utiliser (c'est une bibliothèque C, pas du C++).

Answer 5

Vous pouvez essayer de GMP