Представление 128-битных чисел в С++

Ответ 1

Посмотрите на другие разработанные библиотеки. Многие люди хотели сделать это перед вами.: D

Попробуйте bigint С++

Ответ 2

EDIT: когда я впервые написал этот boost::multiprecision::uint128_t это еще не все. Сохранение этого ответа по историческим причинам.

Раньше я делал класс uint128, вы можете проверить его на: http://www.codef00.com/code/uint128.h.

Это зависит от boost для автоматического предоставления всех вариантов математических операторов, поэтому он должен поддерживать все, что делает собственный тип unsigned int.

Есть некоторые незначительные расширения для встроенных типов, таких как инициализация строки следующим образом:

uint128_t x("12345678901234567890");

Существует удобный макрос, который работает аналогично тому, как в C99, который вы можете использовать следующим образом:

uint128_t x = U128_C(12345678901234567890);

Ответ 3

Это особый случай, особенно если вы не указали, какие платформы вы ищете, но с GCC вы можете использовать так называемый режим (TI) для получения (синтезированного) 128-битного операций, например:

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

Это работает только на 64-разрядных процессорах.

Так или иначе, вы смотрите на множественную арифметику точности, чтобы решить эту проблему. mode (TI) заставит компилятор генерировать операции для вас, в противном случае они должны быть написаны явно.

Вы можете использовать общий пакет bigint; в С++ Я знаю, что включают пакеты теории чисел LiDIA и NTL и пакеты bigint, используемые для криптографического кода в Crypto ++ и Botan). Плюс, конечно, есть GnuMP, который является канонической библиотекой C MPI (и у нее также есть обертка С++, хотя она показалась плохо документированной последней время я посмотрел на него). Все они рассчитаны на быструю работу, но, вероятно, также настроены на более крупные (1000+ бит) номера, поэтому на 128 бит вы можете иметь дело с большим количеством накладных расходов. (С другой стороны, вы не говорите, если это имеет значение или нет). И все они (в отличие от пакета bigint-cpp, который является GPL, являются либо BSD, либо LGPL) - не уверен, имеет ли это значение, но это может иметь большое значение.

Вы также можете написать собственный тип uint128_t; обычно такой класс будет реализовывать те же алгоритмы, что и обычный MPI-класс, просто жестко запрограммированный, чтобы иметь только 2 или 4 элемента. Если вам интересно, как реализовать такие алгоритмы, хорошая ссылка Глава 14 Справочника по прикладной криптографии

Конечно, делать это вручную проще, если вам действительно не нужны все арифметические операции (деление и модуляция, в частности, довольно сложная задача). Например, если вам просто нужно отслеживать счетчик, который может гипотетически переполнить 64 бита, вы могли бы просто представить его как пару длинных 64-битных длин и выполнить перенос вручную:

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

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

Что, конечно, будет намного проще иметь дело с общим пакетом MPI или с обычным классом uint128_t.

Ответ 4

Boost имеет типы данных в multiprecision для типов от 128 до 1024 бит.

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

Ответ 5

Не изобретайте колесо - я уверен, что другие люди уже решили эту проблему, хотя я не могу назвать какие-либо решения с головы. GMP может решить вашу проблему, хотя она переполняет целые числа фиксированного размера, а также немного громоздко использовать (это C библиотека, а не С++).

Ответ 6

Вы можете попробовать GMP

Ответ 7

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

__int128          a;
unsigned __int128 b;

Ответ 8

Вот библиотека, которую я нашел в google.

http://sourceforge.net/projects/cpp-bigint/

Ответ 9

Вам может быть лучше с целым классом с бесконечной точностью, а не с увеличением размера. Некоторые языки (такие как Common Lisp и IIRC Python) имеют их изначально. Я не уверен, что доступно для С++; последнее, что я посмотрел, не было версии Boost.

Ответ 10

Каирская графическая библиотека имеет два файла, реализующих портативную 128-битную целочисленную арифметику: cairo-wideint-private.h, cairo-wideint.c. Мы включили только эти два в наш проект, чтобы получить 128-бит.

Ответ 11

В Visual Studio С++ существует тип FLOAT128, который используется для представления 128-битных целых чисел. Он реализуется как:

#if defined(_M_IA64) && !defined(MIDL_PASS)
__declspec(align(16))
#endif
typedef struct _FLOAT128 {
    __int64 LowPart;
    __int64 HighPart;
} FLOAT128;

поэтому я не уверен, какие математические операции реализованы для него