Are there integer large integer implementations in C?

Question

I am working on a project where I need to crunch large integers (e.g. 3 ^ 361) with absolute accuracy and maximum speed. C is the fastest language I am familiar with, so I'm trying to code my solution in that language.

The problem is that I could not find a good implementation of any data types to represent unlimited integers in C other than the Python source code. It takes me a while to go through the code and determine what I need.

I would rather use someone else's verified code with a full set of functions (addition, subtraction, multiplication, division, modulation, exponentiality, equality checking ... even a bitwise operation would be sweet) than spend the weeks that I need, I even started getting its version to face value. Although this would be a great learning experience, this is not the main focus of my problem, and I would prefer to get the part that interests me :)

Answer 1

Gnu MP provides the bignum library.

Answer 2

A couple of people have already mentioned GMP. I would add that at least the last time I watched it was rather limited to work with gcc.

If you want to use other compilers, a couple you can consider are NTL and MIRACL . I tested MIRACL a bit and it seems to work quite well. I used NTL a bit more, and although large integers are for him the most part, it still does them pretty well. It does not pretend to be as fast as GMP (and, in fact, can use GMP to perform basic operations), but when I did a minimal benchmarking between them, I did not find many significant differences (although it was a long time ago, and I doubt that this is true).

Answer 3

The OpenSSL library also provides a robust BigNum implementation ( <openssl/bn.h> ).

Answer 4

I use MAPM , which is a portable library of arbitrary precision (integer and floating point).

Answer 5

If you want ANSI Standard C, get the code in the Dave Hanson C Interfaces and Implementations . Very clear and well designed.

If the gcc and gcc extensions are fine, then, as others have pointed out, the Gnu Multiprecision Library (GMP) is well thought out and widely used.

Answer 6

libtommath, of libtomcrypt, is arguably the smallest, easiest and fastest. (Funny how these three excellence almost always come together ...) If you cannot find the upstream, you can get the source code from the ssh dropbear source tree.