Reprezentacja 128-bitowych liczb w C ++

EDIT:

kiedy pierwszy raz to napisałem

boost::multiprecision::uint128_t

http://www.boost.org/doc/libs/ ... .html
jeszcze nie. Zachowanie tej odpowiedzi ze względów historycznych.
Zrobiłem już wcześniej klasę uint128, możesz to sprawdzić pod adresem:

http://www.codef00.com/code/uint128.h
http://www.codef00.com/code/uint128.h
.
Zależy od funkcji boost, aby automatycznie udostępniać wszystkie warianty operatorów matematycznych, więc musi obsługiwać wszystko, co robi natywny typ

unsigned int

.
Istnieje kilka drobnych rozszerzeń typów wbudowanych, na przykład inicjowanie ich za pomocą następującego ciągu:

uint128_t x("12345678901234567890");

Jest poręczne makro, które działa podobnie do tych w C99, którego możesz użyć w następujący sposób:

uint128_t x = U128_C(12345678901234567890);

Jest to nieco szczególny przypadek, zwłaszcza że nie określiłeś, której platformy (platform) szukasz, ale w GCC możesz użyć tak zwanego trybu (TI), aby uzyskać (zsyntetyzowane) operacje 128-bitowe, na przykład:

typedef unsigned int uint128_t __attribute__((mode(TI))); uint64_t x = 0xABCDEF01234568;

 uint64_t y = ~x; uint128_t result = ((uint128_t) x * y); printf("6llX * 6llX -> ", x, y); uint64_t r1 = (result >> 64);

 uint64_t r2 = resu< printf("6llX 6llX\n", r1, r2);

Jednak działa to tylko na procesorach 64-bitowych.
W każdym razie, aby rozwiązać ten problem, patrzysz na arytmetykę wielokrotnej precyzji. mode (TI) zmusi kompilator do wygenerowania operacji za Ciebie, w przeciwnym razie muszą one zostać zapisane jawnie.
Możesz użyć ogólnego pakietu bigint; te, które znam w C ++, obejmują pakiety teorii liczb

LiDIA
http://www.cdc.informatik.tu-d ... iDIA/
i

NTL
http://www.shoup.net/ntl/
a także pakiety bigint używane do kryptografii w Crypto ++ i Botan). plus, oczywiście, jest GnuMP, będący kanoniczną biblioteką MPI w C (i ma też opakowanie C ++, chociaż ostatnim razem wydawało mi się, że jest słabo udokumentowany). Wszystkie są zaprojektowane do szybkiego działania, ale prawdopodobnie są również skonfigurowane dla dużych (ponad 1000 bitowych) liczb, więc przy 128 bitach możesz mieć do czynienia z dużym narzutem. (Z drugiej strony nie mówisz, czy to ma znaczenie, czy nie). I wszystkie z nich (w przeciwieństwie do pakietu bigint-cpp, którym jest GPL, są BSD lub LGPL) - nie jestem pewien, czy to ma znaczenie, ale może to zrobić dużą różnicę.
Możesz także napisać niestandardowy typ, taki jak uint128_t; zwykle taka klasa implementuje prawie te same algorytmy, co normalna klasa MPI, tylko zakodowana na stałe tak, aby miała tylko 2 lub 4 elementy. Jeśli zastanawiasz się, jak zaimplementować takie algorytmy, dobrym odniesieniem jest

Rozdział 14 Przewodnika po kryptografii stosowanej
http://www.cacr.math.uwaterloo ... 4.pdf
Oczywiście zrobienie tego ręcznie jest łatwiejsze, jeśli tak naprawdę nie potrzebujesz wszystkich operacji arytmetycznych (w szczególności dzielenie i moduł są dość skomplikowane). Na przykład, jeśli chcesz tylko śledzić licznik, który hipotetycznie może przepełnić się 64-bitowymi bitami, możesz po prostu wyobrazić sobie go jako parę 64-bitowych długich i wykonać transfer ręcznie:

unsigned long long ctrs[2] = { 0 };void increment() {

 ++ctrs[0];

 if(!ctrs[0])// overflow

 ++ctrs[1];

}

Z czym oczywiście będzie znacznie łatwiej sobie poradzić niż z ogólnym pakietem MPI lub niestandardową klasą uint128_t.

Spójrz na inne biblioteki, które zostały opracowane. Wiele osób chciało to zrobić przed tobą .: D
Próbować

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

Boost posiada typy danych w bibliotece

multiprecision

dla typów od 128 do 1024 bitów.

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

GCC

obsługuje
https://gcc.gnu.org/onlinedocs ... .html
128-bitowy typ liczby całkowitej dla procesorów, które go obsługują. Możesz uzyskać do niego dostęp za pomocą:

__int128 a;

unsigned __int128 b;

Aktualizacja 02020-02-10: zgodnie z

to
https://quuxplusone.github.io/ ... ral/: GCC, Clang i Intel ICC obsługują wbudowany typ _ _ int128.

Możesz spróbować

GMP
http://www.gmplib.org/

Nie wymyślaj koła na nowo - jestem pewien, że inni ludzie już rozwiązali ten problem, chociaż nie mogę na początek wymienić żadnych rozwiązań.

GMP
http://gmplib.org/
może z pewnością rozwiązać twój problem, chociaż jest to przesada w przypadku liczb całkowitych o stałym rozmiarze, a także nieco kłopotliwe w użyciu (jest to biblioteka C, a nie C ++).

Lepiej byłoby użyć klasy liczb całkowitych o nieskończonej precyzji, zamiast rosnącej sekwencji. Niektóre języki (takie jak Common Lisp i IIRC Python) mają je natywnie. Nie jestem pewien, co jest dostępne dla C ++; kiedy ostatnio patrzyłem, nie było tam wersji Boost.

Oto biblioteka, którą znalazłem w Google.
http://sourceforge.net/projects/cpp-bigint
http://sourceforge.net/projects/cpp-bigint/
/

Biblioteka grafik Cairo zawiera dwa pliki, które implementują przenośną 128-bitową arytmetykę liczb całkowitych: cairo-wideint-private.h, cairo-wideint.c. W naszym projekcie uwzględniamy tylko te dwa elementy, aby uzyskać 128-bitowy.

Visual Studio C ++ ma typ FLOAT128, który jest używany do reprezentowania 128-bitowych liczb całkowitych. Jest realizowany w następujący sposób:

#if defined(_M_IA64) && !defined(MIDL_PASS)

__declspec(align(16))

#endif

typedef struct _FLOAT128 {

 __int64 LowPart;

 __int64 HighPart;

} FLOAT128;

więc nie jestem pewien, jakie operacje matematyczne są dla niego zaimplementowane