¿Cómo puedo agregar y restar enteros de 128 bits en C o C ++ si mi comstackdor no los admite?

Estoy escribiendo un compresor para una gran cantidad de números de 128 bits. Me gustaría almacenar los números como diferencias, almacenando solo la diferencia entre los números en lugar de los números en sí, porque puedo empacar las diferencias en menos bytes porque son más pequeños.

Sin embargo, para la compresión, entonces necesito restar estos valores de 128 bits, y para la descompresión necesito agregar estos valores. El tamaño entero máximo para mi comstackdor es de 64 bits de ancho.

Alguien tiene alguna idea para hacer esto de manera eficiente?

Si todo lo que necesitas es sum y resta, y ya tienes tus valores de 128 bits en forma binaria, una biblioteca puede ser útil pero no es estrictamente necesaria. Esta matemática es trivial de hacer tú mismo.

No sé qué usa tu comstackdor para los tipos de 64 bits, así que usaré INT64 y UINT64 para cantidades enteras de 64 bits con signo y sin signo.

class Int128 { public: ... Int128 operator+(const Int128 & rhs) { Int128 sum; sum.high = high + rhs.high; sum.low = low + rhs.low; // check for overflow of low 64 bits, add carry to high if (sum.low < low) ++sum.high; return sum; } Int128 operator-(const Int128 & rhs) { Int128 difference; difference.high = high - rhs.high; difference.low = low - rhs.low; // check for underflow of low 64 bits, subtract carry to high if (difference.low > low) --difference.high; return difference; } private: INT64 high; UINT64 low; }; 

Eche un vistazo a GMP .

 #include  #include  int main (int argc, char** argv) { mpz_t x, y, z; char *xs, *ys, *zs; int i; int base[4] = {2, 8, 10, 16}; /* setting the value of x in base 10 */ mpz_init_set_str(x, "100000000000000000000000000000000", 10); /* setting the value of y in base 16 */ mpz_init_set_str(y, "FF", 16); /* just initalizing the result variable */ mpz_init(z); mpz_sub(z, x, y); for (i = 0; i < 4; i++) { xs = mpz_get_str(NULL, base[i], x); ys = mpz_get_str(NULL, base[i], y); zs = mpz_get_str(NULL, base[i], z); /* print all three in base 10 */ printf("x = %s\ny = %s\nz = %s\n\n", xs, ys, zs); free(xs); free(ys); free(zs); } return 0; } 

El resultado es

 x = 10011101110001011010110110101000001010110111000010110101100111011111000000100000000000000000000000000000000 y = 11111111 z = 10011101110001011010110110101000001010110111000010110101100111011111000000011111111111111111111111100000001 x = 235613266501267026547370040000000000 y = 377 z = 235613266501267026547370037777777401 x = 100000000000000000000000000000000 y = 255 z = 99999999999999999999999999999745 x = 4ee2d6d415b85acef8100000000 y = ff z = 4ee2d6d415b85acef80ffffff01 

Habiendo tropezado con este post relativamente antiguo por completo por accidente, pensé que era pertinente elaborar sobre la conjetura anterior de Volte para el beneficio de los lectores inexpertos.

En primer lugar, el rango con signo de un número de 128 bits es -2 127 a 2 127 -1 y no -2 127 a 2 127 como se estipuló originalmente.

En segundo lugar, debido a la naturaleza cíclica de la aritmética finita, el mayor diferencial requerido entre dos números de 128 bits es -2 127 a 2 127 -1, que tiene un prerrequisito de almacenamiento de 128 bits, no 129. Aunque (2 127 -1) – (-2 127 ) = 2 128 -1 que es claramente mayor que nuestro máximo 2 127 -1 entero positivo, el desbordamiento aritmético siempre asegura que la distancia más cercana entre dos números nbit siempre cae dentro del rango de 0 a 2 n – 1 y así implícitamente -2 n -1 a 2 n -1 -1.

Para aclarar, examinemos primero cómo un hipotético procesador de 3 bits implementaría una adición binaria. Como ejemplo, considere la siguiente tabla que representa el rango absoluto sin signo de un entero de 3 bits.

0 = 000b
1 = 001b
2 = 010b
3 = 011b
4 = 100b
5 = 101b
6 = 110b
7 = 111b —> [Regresa a 000b en desbordamiento]

De la tabla anterior, es evidente que:

001b (1) + 010b (2) = 011b (3)

También es evidente que agregar cualquiera de estos números con su complemento numérico siempre produce 2 n -1:

010b (2) + 101b ([complemento de 2] = 5) = 111b (7) = (2 3 -1)

Debido al desbordamiento cíclico que se produce cuando la sum de dos n- bits resulta en un resultado de ( n +1) -bit, por lo tanto, la sum de cualquiera de estos números con su complemento numérico + 1 siempre arrojará 0:

010b (2) + 110b ([complemento de 2] + 1) = 000b (0)

Por lo tanto, podemos decir que [complemento de n ] + 1 = – n , de modo que n + [complemento de n ] + 1 = n + (- n ) = 0. Además, si ahora sabemos que n + [complemento de n ] + 1 = 0, luego n + [complemento de nx ] + 1 debe = n – ( nx ) = x .

Aplicando esto a nuestra tabla original de 3 bits rinde:

0 = 000b = [complemento de 0] + 1 = 0
1 = 001b = [complemento de 7] + 1 = -7
2 = 010b = [complemento de 6] + 1 = -6
3 = 011b = [complemento de 5] + 1 = -5
4 = 100b = [complemento de 4] + 1 = -4
5 = 101b = [complemento de 3] + 1 = -3
6 = 110b = [complemento de 2] + 1 = -2
7 = 111b = [complemento de 1] + 1 = -1 —> [regresa a 000b en desbordamiento]

Ya sea que la abstracción representacional sea positiva, negativa o una combinación de ambas implicada con la aritmética de dos signos complementados, ahora tenemos 2 n n patrones de bits que pueden servir tanto 0 como 2 n -1 como negativos de 0 a – 2 n ) -1 varía según sea necesario. De hecho, todos los procesadores modernos emplean exactamente un sistema de este tipo para implementar circuitos de ALU comunes para operaciones de sum y resta. Cuando una CPU encuentra una instrucción de resta i1 - i2 , realiza internamente una operación [complemento + 1] en i2 y posteriormente procesa los operandos a través de la circuitería de sum para calcular i1 + [complemento de i2 ] + 1. Con la excepción de una bandera adicional de desbordamiento de portado / señal XOR-portado, tanto la sum firmada como la no firmada, y por implicación la resta, están implícitas.

Si aplicamos la tabla anterior a la secuencia de entrada [-2 n -1 , 2 n -1 -1, -2 n -1 ] tal como se presenta en la respuesta original de Volte, ahora podemos calcular los siguientes diferenciales de n bits:

diff # 1:
(2 n -1 -1) – (-2 n -1 ) =
3 – (-4) = 3 + 4 =
(-1) = 7 = 111b

diff # 2:
(-2 n -1 ) – (2 n -1 -1) =
(-4) – 3 = (-4) + (5) =
(-7) = 1 = 001b

Comenzando con nuestra semilla -2 n -1 , ahora podemos reproducir la secuencia de entrada original aplicando secuencialmente cada uno de los diferenciales anteriores:

(-2 n -1 ) + (diff # 1) =
(-4) + 7 = 3 =
2 n -1 -1

(2 n -1 -1) + (diff # 2) =
3 + (-7) = (-4) =
-2 n -1

Por supuesto, puede desear adoptar un enfoque más filosófico de este problema y conjeturas sobre por qué 2 n números secuencialmente cíclicos requerirían más de 2 n diferenciales cíclicamente secuenciales?

Taliadon.

Boost 1.53 ahora incluye multiprecision:

 #include  #include  // Requires Boost 1.53 or higher // build: g++ text.cpp int main() { namespace mp = boost::multiprecision; mp::uint128_t a = 4294967296; mp::uint256_t b(0); mp::uint512_t c(0); b = a * a; c = b * b; std::cout << "c: " << c << "\n"; return 0; } 

Salida:

 ./a.out c: 340282366920938463463374607431768211456 

Hay mucha literatura sobre matemáticas enteras grandes. Puede utilizar una de las bibliotecas disponibles gratuitamente (ver enlaces) o puede hacer las suyas propias. Aunque debo advertirte, para algo más complicado que la sum y la resta (y los cambios), necesitarás usar algoritmos no triviales.

Para sumr y restar, puede crear una clase / estructura que contenga dos enteros de 64 bits. Puedes usar matemática escolar simple para hacer la sum y la resta. Básicamente, haga lo que hace con un lápiz y papel para sumr o restar, con una consideración cuidadosa de carry / borrows.

Busque un número entero grande. Por cierto, las versiones recientes de los comstackdores VC ++, IntelC ++ y GCC tienen tipos enteros de 128 bits, aunque no estoy seguro de que sean tan fácilmente accesibles como pueda desear (están destinados a ser utilizados con registros sse2 / xmms).

TomsFastMath es un poco como GMP (mencionado anteriormente), pero es de dominio público, y fue diseñado desde cero para ser extremadamente rápido (incluso contiene optimizaciones de código ensamblador para x86, x86-64, ARM, SSE2, PPC32 y AVR32) .

También vale la pena señalar: si el objective es simplemente mejorar la compresión de una secuencia de números preprocesándola, entonces la secuencia preprocesada no tiene que estar hecha de diferencias aritméticas exactas. Puede usar XOR ( ^ ) en lugar de + y - . La ventaja es que un XOR de 128 bits es exactamente lo mismo que dos XOR independientes en las partes de 64 bits, por lo que es simple y eficiente.

    Intereting Posts