Representar números de 128 bits en C++

¿Cuál es la mejor manera de representar un número de 128 bits en C++? Debe comportarse lo más cerca posible de los tipos numéricos incorporados (es decir, admitir todos los operadores aritméticos, etc.).

Estaba pensando en construir una clase que tuviera 2 números de 64 bits o 4 números de 32 bits. O posiblemente simplemente creando un bloque de memoria de 128 bits y haciéndolo todo yo mismo.

¿Hay alguna manera más fácil/más estándar, o algo que sea menos probable que arruine cuando lo implemente yo mismo? 🙂

También sería bueno si pudiera extenderse a 256 bits, 512 bits, etc.

EDITAR: cuando escribí esto por primera vez boost::multiprecision::uint128_t no era una cosa todavía. Manteniendo esta respuesta por razones históricas.

He hecho una clase uint128 antes, puedes verla en: http://www.codef00.com/code/uint128.h.

Depende de boost para proporcionar automáticamente todas las variantes de los operadores matemáticos, por lo que debería admitir todo lo que sea nativo. unsigned int el tipo lo hace.

Hay algunas extensiones menores para los tipos incorporados, como inicializarlos con una cadena como esta:

uint128_t x("12345678901234567890");

Hay una macro de conveniencia que funciona de manera similar a las de C99 que puede usar así:

uint128_t x = U128_C(12345678901234567890);

Este es un caso algo especial, especialmente porque no especificó qué plataforma (s) está buscando, pero con GCC puede usar lo que se llama modo (TI) para obtener operaciones (sintetizadas) de 128 bits, para ejemplo:

   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);

Sin embargo, esto solo funciona en procesadores de 64 bits.

De una forma u otra, estás buscando aritmética de precisión múltiple para resolver esto. mode(TI) hará que el compilador genere las operaciones por usted, de lo contrario, deben escribirse explícitamente.

Puede usar un paquete bigint general; los que están en C++ que conozco incluyen los paquetes de teoría de números LiDIA y NTLy los paquetes bigint utilizados para el código criptográfico en Cripto++ y botan). Además, por supuesto, hay GNUMP, que es la biblioteca canónica de C MPI (y también tiene un envoltorio de C++, aunque parecía estar mal documentado la última vez que lo miré). Todos estos están diseñados para ser rápidos, pero probablemente también estén ajustados para números más grandes (más de 1000 bits), por lo que a 128 bits puede estar lidiando con una gran cantidad de gastos generales. (Por otro lado, no dices si eso importa o no). Y todos ellos (a diferencia del paquete bigint-cpp, que es GPL, son BSD o LGPL), no estoy seguro de si importa, pero podría importar mucho.

También puede escribir un tipo de tipo uint128_t personalizado; por lo general, dicha clase implementaría los mismos algoritmos que una clase MPI normal, simplemente codificada para tener solo 2 o 4 elementos. Si tiene curiosidad sobre cómo implementar tales algoritmos, una buena referencia es Capítulo 14 del Manual de Criptografía Aplicada

Por supuesto, hacer esto a mano es más fácil si no necesita todas las operaciones aritméticas (la división y el módulo, en particular, son bastante complicados). Por ejemplo, si solo necesita realizar un seguimiento de un contador que hipotéticamente podría desbordar 64 bits, podría representarlo como un par de largos de 64 bits y realizar el acarreo a mano:

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

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

Lo que, por supuesto, será mucho más sencillo de manejar que un paquete MPI general o una clase uint128_t personalizada.

Busque en otras bibliotecas que se han desarrollado. Mucha gente ha querido hacer esto antes que tú. 😀

Tratar bigint C++

Boost tiene tipos de datos en multiprecision biblioteca para tipos que van desde 128 a 1024 bits.

#include <boost/multiprecision/cpp_int.hpp>

using namespace boost::multiprecision;

int128_t mySignedInt128 = -1;
uint128_t myUnsignedInt128 = 2;
int256_t mySignedInt256 = -3;
uint256_t myUnsignedInt256 = 4;
int512_t mySignedInt512 = -5;
uint512_t myUnsignedInt512 = 6;
int1024_t mySignedInt1024 = -7;
uint1024_t myUnsignedInt1024 = 8;

CCG apoya un tipo entero de 128 bits para los procesadores que lo admiten. Puedes acceder usando:

__int128          a;
unsigned __int128 b;

02020-02-10 Actualización: según esta: GCC, Clang e Intel ICC admiten un tipo __int128 integrado.

No reinvente la rueda: estoy seguro de que otras personas ya han resuelto este problema, aunque no puedo nombrar ninguna solución que se me ocurra. BPF seguramente puede resolver su problema, aunque es excesivo para números enteros de tamaño fijo, y también es un poco engorroso de usar (es una biblioteca C, no C ++).

Es posible que desee probar BPF