Fastest 128 bit integer library

Question

I am working on a CPU-heavy numerical computation app. Without going into many details, it's a computational math research project that involves computing a certain function f(x) for large integer x.

Right now everything is implemented in C++ in x64 mode, using native 64-bit ints. That limits me to x<2^64~1.8*10^19. I want to go further, to do that, I need a library that does 128-bit arithmetic. And it has to be very fast. In particular, integer divisions should be fast. Otherwise I'll be sitting here waiting for the results till Thanksgiving. And I'd rather not reinvent the wheel.

I found a list of ~20 big integer libraries on Wikipedia, but most of those seem to be targeted towards arbitrary-precision numbers, which is overkill for my task, and I don't need extra costs associated with that.

Does anyone know what library can operate on 128 bit integers fastest?

Answer 1

You didn't mention your platform / portability requirements. If you are willing to use gcc or clang, on 64 bit platforms they have a builtin 128 bit types that come for free, __uint128_t and __int128_t. Maybe other platforms have similar type extensions.

In any case it should be possible to find the corresponding generic code in the gcc sources that assembles two integers of width N to synthesize one integer of width 2N. This would probably be a good starting point to make a standalone library for that purpose.

Answer 2

This might not be for everyone, but what I would do is pick the highest-performance arbitrary integer library with source code and otherwise suitable for the job, and hack it to be for fixed integer sizes. Change some variable "nbits" to 128 hard-coded. It probably allocates memory at runtime, not knowing the number of bytes until then. Change it to use struct with data in-place, saving a pointer dereferencing every time data is read. Unroll certain critical loops by hand. Hard-code anything else that might be critical. Then the compiler will probaby have an easier time optimizing things. Of course, much of this will be assembly, using fancy SIMD with whatever the technology is in use this week.

It would be fun! But then, as a programmer I started off with machine code and very low level stuff.

But for those not as crazy as I am, perhaps one of the available libraries uses templates or has some means of generating code custom to some size. And, some compilers have a "long long" integer type which might be suitable.

Answer 3

gcc on x86-64 has 128-bit long long. Use that.

Answer 4

The ttmath library does what you want.