What is the simplest way of implementing bigint in C?
You asked for the simplest way to do this. So, here you go:
#include <gmp.h>
#include <stdio.h>
int main(int argc, char** argv) {
mpz_t mynum;
mpz_init(mynum);
mpz_add_ui(mynum, 100);
int i;
for (i = 99; i > 1; i--) {
mpz_mul_si(mynum, mynum, (long)i);
}
mpz_out_str(stdout, 10, mynum);
return 0;
}
I tested this code and it gives the correct answer.
If you're willing to use a library implementation the standard one seems to be GMP
mpz_t out;
mpz_init(out);
mpz_fac_ui(out,100);
mpz_out_str(stdout,10,out);
should calculate 100! from looking at the docs.
If you're looking for a simple library, libtommath (from libtomcrypt) is probably what you want.
If you're looking to write a simple implementation yourself (either as a learning exercise or because you only need a very limited subset of bigint functionality and don't want to tack on a dependency to a large library, namespace pollution, etc.), then I might suggest the following for your problem:
Since you can bound the size of the result based on n
, simply pre-allocate an array of uint32_t
of the required size to hold the result. I'm guessing you'll want to print the result, so it makes sense to use a base that's a power of 10 (i.e. base 1000000000) rather than a power of 2. That is to say, each element of your array is allowed to hold a value between 0 and 999999999.
To multiply this number by a (normal, non-big) integer n
, do something like:
uint32_t carry=0;
for(i=0; i<len; i++) {
uint64_t tmp = n*(uint64_t)big[i] + carry;
big[i] = tmp % 1000000000;
carry = tmp / 1000000000;
}
if (carry) big[len++] = carry;
If you know n
will never be bigger than 100 (or some other small number) and want to avoid going into the 64-bit range (or if you're on a 64-bit platform and want to use uint64_t
for your bigint array), then make the base a smaller power of 10 so that the multiplication result will always fit in the type.
Now, printing the result is just something like:
printf("%lu", (long)big[len-1]);
for(i=len-1; i; i--) printf("%.9lu", (long)big[i-1]);
putchar('\n');
If you want to use a power of 2 as the base, rather than a power of 10, the multiplication becomes much faster:
uint32_t carry=0;
for(i=0; i<len; i++) {
uint64_t tmp = n*(uint64_t)big[i] + carry;
big[i] = tmp;
carry = tmp >> 32;
}
if (carry) big[len++] = carry;
However, printing your result in decimal will not be so pleasant... :-) Of course if you want the result in hex, then it's easy:
printf("%lx", (long)big[len-1]);
for(i=len-1; i; i--) printf("%.8lx", (long)big[i-1]);
putchar('\n');
Hope this helps! I'll leave implementing other things (like addition, multiplication of 2 bigints, etc) as an exercise for you. Just think back to how you learned to do base-10 addition, multiplication, division, etc. in grade school and teach the computer how to do that (but in base-10^9 or base-2^32 instead) and you should have no problem.