Are there any solid large integer implementations in C?

Question

I am working on a project where I need to crunch large integers (like 3^361) with absolute precision and as much speed as possible. C is the fastest language I am familiar with, so I am trying to code my solution in that language.

The problem is that I have not been able to find a good implementation of any data types for representing limitless integers in C other than Python's source code. It is taking me time to go through the code and determine what I need.

I would much rather use someone else's tested code with a full set of functionality (addition, subtraction, multiplication, division, modulation, exponentiation, equality checking... even bitwise operation would be sweet) than spending the weeks it would take me to even begin to get my own version up to par. While it would be a great learning experience, it is not the focus of my problem, and I'd rather get to the part that interests me :)

Answer 1

http://gmplib.org/

Answer 2

Gnu MP provides a bignum library.

Answer 3

A couple of people have already mentioned GMP. I would only add that at least the last time I looked, it was pretty well restricted to working with gcc.

If you want to use other compilers, are couple you might consider are NTL and MIRACL. I've tested MIRACL a bit, and it seems to work reasonably well. I've used NTL quite a bit more, and while large integers are more of a sideline for it, it still does them quite nicely. It doesn't claim to be as fast as GMP (and, in fact, can use GMP to do basic operations), but when I've done some minimal benchmarking between the two I haven't found a lot of significant differences (though that was long enough ago that I doubt it's valid anymore either).

Answer 4

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

Answer 5

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

Answer 6

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

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

Answer 7

libtommath, from libtomcrypt, is probably the smallest, simplest, and fastest. (Funny how those 3 superlatives almost always come together...) If you can't find an upstream you can get the source from the dropbear ssh source tree.