Как я могу добавить и вычесть 128-битные целые числа в C или C ++, если мой компилятор не поддерживает их? - PullRequest
Новая
       63

Как я могу добавить и вычесть 128-битные целые числа в C или C ++, если мой компилятор не поддерживает их?

23 голосов
/ 12 апреля 2009

Я пишу компрессор для длинного потока 128-битных чисел. Я хотел бы хранить числа как различия - сохраняя только разницу между числами, а не сами числа, потому что я могу упаковать различия в меньшее количество байтов, поскольку они меньше.

Однако для сжатия мне нужно вычесть эти 128-битные значения, а для декомпрессии мне нужно добавить эти значения. Максимальный целочисленный размер для моего компилятора составляет 64 бита.

У кого-нибудь есть идеи сделать это эффективно?

Ответы [ 7 ]

38 голосов
/ 12 апреля 2009

Если все, что вам нужно, это сложение и вычитание, и у вас уже есть 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;
};
16 голосов
/ 12 апреля 2009

Взгляните на 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
8 голосов
/ 25 апреля 2013

Повышение 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
8 голосов
/ 29 мая 2010

Случайно наткнувшись на этот относительно старый пост совершенно случайно, я подумал, что уместно уточнить предыдущую гипотезу Вольта в пользу неопытных читателей.

Во-первых, диапазон со знаком 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 must = 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 при переполнении]

Независимо от того, является ли представительная абстракция положительной, отрицательной или комбинацией того и другого, как подразумевается в знаковой арифметике с двойным дополнением, теперь у нас есть 2 n n - битовые комбинации, которые могут беспрепятственно обслуживать как положительные от 0 до 2 n -1, так и отрицательные от 0 до - (2 n ) - 1 диапазон как и когда требуется. Фактически, все современные процессоры используют именно такую ​​систему, чтобы реализовать общую схему ALU для операций сложения и вычитания. Когда ЦП встречает инструкцию вычитания i1 - i2, он внутренне выполняет операцию [дополнение + 1] на i2 и впоследствии обрабатывает операнды через схему сложения для вычисления i1 + [дополнение к i2] + 1. За исключением дополнительного XOR-закрытого флага переполнения переноса / знака, как неявное, так и сложное со знаком и без знака, неявно.

Если применить приведенную выше таблицу к последовательности ввода [-2 n -1 , 2 n -1 -1 , -2 n -1 ], как представлено в исходном ответе Вольте, теперь мы можем вычислить следующие 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 п * +1191 * -1 * * -1 тысяча сто девяносто-два

(2 n -1 -1) + (diff # 2) =
3 + (-7) = (-4) =
-2 * * п тысячу двести две -1

Вы, конечно, можете принять более философский подход к этой проблеме и предположить, почему для 2 n циклически-последовательных чисел потребуется более 2 n циклически-последовательные дифференциалы?

Taliadon.

3 голосов
/ 12 апреля 2009

Существует много литературы по математике с большим целым числом. Вы можете использовать одну из свободно доступных библиотек (см. Ссылки) или вы можете свернуть свою собственную. Хотя я должен предупредить вас, что для чего-то более сложного, чем сложение и вычитание (и сдвиги), вам нужно использовать нетривиальные алгоритмы.

Чтобы сложить и вычесть, вы можете создать класс / структуру, которая содержит два 64-битных целых числа. Вы можете использовать простую школьную математику для сложения и вычитания. По сути, делайте то, что вы делаете, с помощью карандаша и бумаги, чтобы сложить или вычесть, с тщательным вниманием относясь к заимствованиям / заимствованиям.

Поиск большого целого числа. Кстати, последние версии компиляторов VC ++, IntelC ++ и GCC имеют 128-битные целочисленные типы, хотя я не уверен, что они так легко доступны, как вы могли бы (они предназначены для использования с регистрами sse2 / xmms).

2 голосов
/ 12 апреля 2009

TomsFastMath немного похож на GMP (упомянутый выше), но является общественным достоянием и был разработан с нуля, чтобы быть чрезвычайно быстрым (он даже содержит оптимизации кода сборки для x86, x86-64 ARM, SSE2, PPC32 и AVR32).

0 голосов
/ 08 ноября 2013

Также стоит отметить: если цель состоит в том, чтобы просто улучшить сжатие потока чисел путем его предварительной обработки, тогда предварительно обработанный поток не должен быть сделан из точно арифметических различий. Вы можете использовать XOR (^) вместо + и -. Преимущество состоит в том, что 128-разрядный XOR точно такой же, как два независимых XOR в 64-разрядных частях, поэтому он прост и эффективен.

...