Я пишу компрессор для длинного потока из 128-битных чисел. Я хотел бы сохранить числа как различия - сохраняя только разницу между числами, а не самими цифрами, потому что я могу упаковать различия в меньшем количестве байтов, потому что они меньше.
Однако для сжатия мне нужно вычесть эти 128-битные значения, и для декомпрессии мне нужно добавить эти значения. Максимальный размер для моего компилятора - 64 бита.
У кого-нибудь есть идеи для этого эффективно?
Если все, что вам нужно, это сложение и вычитание, и вы уже имеете свои 128-битные значения в двоичной форме, библиотека может быть удобной, но не является абсолютно необходимой. Эта математика тривиальна для себя.
Я не знаю, что ваш компилятор использует для 64-битных типов, поэтому я буду использовать INT64 и UINT64 для 64-разрядных целых чисел с подписью и без знака.
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;
};
Взгляните на GMP.
#include <stdio.h>
#include <gmp.h>
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;
}
Выходной сигнал
x = 10011101110001011010110110101000001010110111000010110101100111011111000000100000000000000000000000000000000
y = 11111111
z = 10011101110001011010110110101000001010110111000010110101100111011111000000011111111111111111111111100000001
x = 235613266501267026547370040000000000
y = 377
z = 235613266501267026547370037777777401
x = 100000000000000000000000000000000
y = 255
z = 99999999999999999999999999999745
x = 4ee2d6d415b85acef8100000000
y = ff
z = 4ee2d6d415b85acef80ffffff01
Наткнувшись на эту относительно старую должность полностью случайно, я подумал, что уместно подробно остановиться на предыдущей гипотезе Вольта на благо неопытных читателей.
Во-первых, подписанный диапазон 128-битного числа равен -2 127 до 2 127 -1, а не -2 127 до 2 127 как изначально было предусмотрено.
Во-вторых, из-за цикличности конечной арифметики наибольший требуемый дифференциал между двумя 128-битными числами равен -2 127 до 2 127 -1, который имеет Хранение предпосылки 128 бит, а не 129. Хотя (2 127 -1) - (-2 127) = 2 128 -1, что явно больше нашего максимального 2 127 -1 положительного целого числа, арифметическое переполнение всегда гарантирует, что ближайшее расстояние между любыми двумя числами n всегда будет находиться в диапазоне от 0 до 2 n -1 и, следовательно, неявно -2 n -1 до 2 nя > 1 -1.
Чтобы уточнить, давайте сначала рассмотрим, как гипотетический 3-битный процессор будет реализовывать двоичное добавление. В качестве примера рассмотрим следующую таблицу, которая отображает абсолютный диапазон без знака 3-битного целого.
0 = 000b
1 = 001b
2 = 010b
3 = 011b
4 = 100b
5 = 101b
6 = 110b
7 = 111b --- > [Возвращается к 000b при переполнении]
Из приведенной выше таблицы легко видно, что:
001b (1) + 010b (2) = 011b (3)
Также очевидно, что добавление любого из этих чисел с его числовым дополнением всегда дает 2 n -1:
010b (2) + 101b ([дополнение 2] = 5) = 111b (7) = (2 3 -1)
Из-за циклического переполнения, которое возникает, когда добавление двух чисел n -битов приводит к результату ( n +1) -биту, из этого следует, что добавление любое из этих чисел с его числовым дополнением + 1 всегда будет давать 0:
010b (2) + 110b ([дополнение 2] + 1) = 000b (0)
Таким образом, мы можем сказать, что [дополнение к n] + 1 = - n, так что n + [дополнение к n] + 1 = n + (- n) = 0. Кроме того, если теперь мы знаем, что n + [дополнение из n] + 1 = 0, то n + [дополнение к n - x] + 1 должно = n - (n - x) = x.
Применив это к нашей исходной 3-битной таблице, получим:
0 = 000b = [дополнение 0] + 1 = 0
1 = 001b = [дополнение 7] + 1 = -7
2 = 010b = [дополнение к 6] + 1 = -6
3 = 011b = [дополнение к 5] + 1 = -5
4 = 100b = [дополнение к 4] + 1 = -4
5 = 101b = [дополнение 3] + 1 = -3
6 = 110b = [дополнение 2] + 1 = -2
7 = 111b = [дополнение 1] + 1 = -1 --- > [Возврат к 000b при переполнении]
Является ли репрезентативная абстракция положительной, отрицательной или комбинацией обоих, как подразумевается с подписанной арифметикой twos-complement, теперь мы имеем 2 n n -битные шаблоны, которые могут без проблем обслуживать как положительные 0 до 2 n -1, так и отрицательные 0 до - (2 n) - 1 диапазон по мере необходимости. Фактически, все современные процессоры используют именно такую систему для реализации общих схем ALU для операций сложения и вычитания. Когда ЦПУ встречает команду вычитания i1 - i2, она внутренне выполняет операцию [дополнение + 1] на i2 и затем обрабатывает операнды через схему сложения, чтобы вычислить i1 + [дополнение к i2] + 1. За исключением дополнительного флага переполнения/знака XOR-gated, как подписанного, так и неподписанного сложения и вычитания импликации, являются неявными.
Если применить приведенную выше таблицу к входной последовательности [-2 n -1 2 n -1 -1, -2 n -1], как представлено в оригинальном ответе Volte, теперь мы можем вычислить следующие n-битовые дифференциалы:
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
Начиная с нашего семени -2 n -1 мы теперь можем воспроизвести исходную входную последовательность, последовательно применяя каждый из указанных выше дифференциалов:
(- 2 n -1) + (diff # 1) =
(-4) + 7 = 3 =
2 <я > пя > 1 1
(2 n -1 -1) + (diff # 2) =
3 + (-7) = (-4) =
-2 <я > пя > 1
Возможно, вы, конечно, захотите принять более философский подход к этой проблеме и догадаться, почему для циклических последовательностей 2 n потребуется более 2 n циклически-последовательные дифференциалы?
Taliadon.
Boost 1.53 теперь включает в себя многоточие:
#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
// 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;
}
Вывод:
./a.out
c: 340282366920938463463374607431768211456
Существует много литературы по большой целочисленной математике. Вы можете использовать одну из доступных библиотек (см. Ссылки), или вы можете использовать ее самостоятельно. Хотя я должен вас предупредить, для чего-то более сложного, чем сложение и вычитание (и сдвиги), вам нужно будет использовать нетривиальные алгоритмы.
Чтобы добавить и вычесть, вы можете создать класс/структуру, которая содержит два 64-битных целых числа. Вы можете использовать простую математику школы для сложения и вычитания. В основном, делайте то, что вы делаете с карандашом и бумагой для добавления или вычитания, с тщательным учетом переноса/заимствования.
Найдите большое целое число. Btw последние версии компиляторов VС++, IntelС++ и GCC имеют 128-битные целые типы, хотя я не уверен, что они так же легко доступны, как вам может понравиться (они предназначены для использования с регистрами sse2/xmms).
TomsFastMath немного похож на GMP (упомянутый выше), но является общедоступным, и был разработан с нуля, чтобы быть (он даже содержит оптимизацию кода сборки для x86, x86-64, ARM, SSE2, PPC32 и AVR32).
Можете ли вы гарантировать, что различия будут меньше? В этом отношении, можете ли вы гарантировать, что различия на самом деле не будут больше? Например, если вы просто сохраняете числа в виде 128-битных чисел (подписанных или других), вам нужен диапазон 2 ^ 128 (либо от -2 ^ 127 до 2 ^ 127, либо от 0 до 2 ^ 128), но если вы храните различия, вам понадобится диапазон 2 ^ 129 для хранения всех потенциальных различий. Рассмотрим последовательность [-2 ^ 127, 2 ^ 127, -2 ^ 127], которая переводится в последовательность разностей [2 ^ 128, -2 ^ 128] из начальной точки -2 ^ 127. 128-битный тип данных не может содержать оба этих номера, на самом деле вам потребуется 129 бит на разницу, чтобы удерживать весь диапазон.
С другой стороны, если вы знаете, что различия между двумя числами всегда будут вписываться в меньший тип данных, я вторые соображения, чтобы посмотреть на GMP.
Также стоит отметить: если целью является просто улучшить сжатие потока чисел путем предварительной обработки, то препроцессорный поток не обязательно должен быть сделан из точно арифметических различий. Вы можете использовать XOR (^) вместо + и -. Преимущество состоит в том, что 128-битный XOR точно такой же, как два независимых XOR в 64-битных частях, поэтому он является простым и эффективным.