Bigint (bigbit) library

Question

I'm looking for a c++ class/library that provides 1024 bit and bigger integers and bit operations like: - bit shifting, - bitwise OR/AND, - position first zero bit

speed is crucial, so it would have to be implemented with some SIMD assembly.

Answer 1

There are several, including GMP, but for speed, the best is likely TTmath. TTmath's design decision to use templated fixed lengths at compiletime lets it be quite fast.

Answer 2

try gmp library. It is a C library. Beginning with GMP 4.0 a C++ wrapper is bundled with the release.

Answer 3

Just consider the big integer multiplication, the TTmath Library use Karatsuba algorithm, which has time complexity $O(n^{1.585})$. The fastest algorithm is $O(n log n log log n)$, using FFT.