Representation of 128-bit numbers in C ++

Question

What is the best way to represent a 128 bit number in C ++? It should behave as close as possible to the built-in numeric types (i.e., support all arithmetic operators, etc.).

I was thinking of creating a class that has 2 64-bit or 4 32-bit numbers. Or maybe just create a 128-bit memory block and do it all yourself.

Is there a simpler / more standard way, or something that I would be less likely to spoil when implementing it? :)

It would be nice if it could be expanded to 256-bit, 512-bit, etc.

Answer 1

Look at other developed libraries. Many people like to do this in front of you .: D

Try bigint c ++

Answer 2

EDIT: when I first wrote this boost::multiprecision::uint128_t that was not all. Keeping this answer for historical reasons.

---

I used to make the uint128 class, you can check it at: http://www.codef00.com/code/uint128.h .

It depends on boost to automatically provide all variants of mathematical operators, so it should support everything that makes its own type unsigned int .

There are some minor extensions to built-in types, such as initializing a string as follows:

 uint128_t x("12345678901234567890"); 

There is a convenient macro that works the same way as in C99, which you can use as follows:

 uint128_t x = U128_C(12345678901234567890); 

Answer 3

This is a special case, especially if you have not indicated which platforms you are looking for, but with GCC you can use the so-called mode (TI) to receive (synthesized) 128-bit operations, for example:

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

This only works on 64-bit processors.

One way or another, you are looking at multiple arithmetic of accuracy to solve this problem. mode (TI) will force the compiler to generate operations for you, otherwise they must be written explicitly.

You can use the generic bigint package; in C ++ I know that include LiDIA and NTL number theory packages and bigint packages used for cryptographic code in Crypto ++ and Botan ). Plus, of course, there is GnuMP , which is the canonical C MPI library (and it also has a C ++ wrapper, although it seemed poorly documented the last time I looked at it). All of them are designed for quick operation, but they are also probably configured for larger (1000+ bits) numbers, so for 128 bits you can deal with a lot of overhead. (On the other hand, you don’t say if it matters or not). And all of them (unlike the bigint-cpp package, which is the GPL, are either BSD or LGPL) - not sure if this matters, but it can make a big difference.

You can also write your own type uint128_t; usually, such a class will implement the same algorithms as a regular MPI class, just hard-coded to have only 2 or 4 elements. If you're curious about how to implement such algorithms, a good reference is Chapter 14 of the Applied Cryptography Reference

Of course, doing it manually is easier if you really don't need all the arithmetic operations (division and modulation, in particular, a rather difficult task). For example, if you just need to keep track of a counter that can hypothetically overflow 64 bits, you could simply imagine it as a pair of long 64-bit lengths and perform the manual transfer:

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

Which, of course, will be much easier to deal with the common MPI package or with the regular uint128_t class.

Answer 4

Boost has multiprecision data types for types from 128 to 1024 bits.

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

Answer 5

Do not reinvent the wheel - I am sure that other people have already solved this problem, although I can’t name any solutions from the head. GMP can solve your problem, although it overflows integers of a fixed size, and is also a bit cumbersome to use (this is a C library, not C ++).

Answer 6

You can try GMP

Answer 7

GCC supports a 128-bit integer type for processors that support it. You can access it using:

 __int128 a; unsigned __int128 b; 

Answer 8

Here is the library I found on google.

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

Answer 9

You may be better off with an entire class with infinite precision, rather than increasing size. Some languages ​​(such as Common Lisp and IIRC Python) have them natively. I'm not sure what is available for C ++; The last thing I looked at was not the Boost version.

Answer 10

The Cairo graphics library has two files that implement portable 128-bit integer arithmetic: cairo-wideint-private.h, cairo-wideint.c. We only included these two in our project to get 128-bit.

Answer 11

In Visual Studio C ++, there is a type FLOAT128, which is used to represent 128-bit integers. It is implemented as:

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

so I'm not sure what math operations are implemented for him