Representing 128-bit numbers in C++

Question

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

I was thinking of building a class that had 2 64 bit or 4 32 bit numbers. Or possibly just creating a 128 bit block of memory and doing everything myself.

Is there some easier/more standard way, or something that I'm less likely to screw up when implementing it myself? :)

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

Answer 1

Don't reinvent the wheel -- I'm positive other people have already solved this problem, although I can't name any solutions off the top of my head. GMP can surely solve your problem, although it's overkill for fixed-size integers, and it's also a little cumbersome to use (it's a C library, not C++).

Answer 2

Here is a library I found on google.

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

Answer 3

You may want to try GMP

Answer 4

Look into other libraries that have been developed. Lots of people have wanted to do this before you. :D

Try bigint C++

Answer 5

You might be better off with an infinite-precision integer class, rather than a sequence of increasing size. Some languages (like Common Lisp and IIRC Python) have them natively. I'm not sure offhand what's available for C++; last I looked there wasn't a Boost version.

Answer 6

In Visual Studio C++ there is a type FLOAT128 that 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 about what math operations are implemented for it

Answer 7

I've made a uint128 class before, you can check it out at: http://www.codef00.com/code/uint128.h.

It is dependent on boost for automatically providing all of the variants of the math operators, so it should support everything a native unsigned integer type does.

There are some minor extensions to built in types such as initializing it with a string like this:

uint128_t x("12345678901234567890");

There is a convenience macro which works similary to the ones in C99 which you can use like this:

uint128_t x = U128_C(12345678901234567890);

Answer 8

This is somewhat of a special case, especially since you didn't specify what platform(s) you're looking for, but with GCC you can use what is called mode(TI) to get (synthesized) 128-bit operations, for instance:

   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, though.

One way or another, you're looking at multiple precision arithmetic to solve this. mode(TI) will cause the compiler to generate the operations for you, otherwise they have to be written explicitly.

You can use a general bigint package; ones in C++ I know of include the number theory packages LiDIA and NTL, and the 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 does have a C++ wrapper as well, though it seemed poorly documented last time I looked at it). All of these are designed to be fast, but are also probably tuned for larger (1000+ bit) numbers, so at 128 bits you may be dealing with a lot of overhead. (On the other hand you don't say if that matters or not). And all of them (unlike the bigint-cpp package, which is GPL, are either BSD or LGPL) - not sure if it matters - but it might matter a lot.

You could also write a custom uint128_t kind of type; typically such a class would implement much the same algorithms as a regular MPI class, just hardcoded to have only 2 or 4 elements. If you are curious how to implement such algorithms, a good reference is Chapter 14 of the Handbook of Applied Cryptography

Of course doing this by hand is easier if you don't actually need all the arithmetic operations (division and modulo, in particular, are rather tricky). For instance, if you just need to keep track of a counter which might hypothetically overflow 64 bits, you could just represented it as a pair of 64 bit long longs and do the carry by hand:

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

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

Which of course is going to be a lot simpler to deal with than a general MPI package or a custom uint128_t class.