What is the simplest way of implementing bigint in C?

Question

I am trying to calculate 100! (that is, the factorial of 100).

I am looking for the simplest way to accomplish this using C. I have read around but have not found a concrete answer.

If you must know, I program in Xcode in Mac os X.

Klansman

there you go: 933[100 digits removed]00000 :-) – Pawnbroker

@Anders: This website is Stack Overflow, not Comment Overflow! :-O – Aloes

lol, I know I can get the value from like wolframalpha. However, I am learning C and wanted to know how this could be done. – Klansman

Duplicate of "BigInt" in C? – Molluscoid

Answer 1

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.

Starrstarred

One comment on the 64-bit types on 32-bit targets: on any sane hardware, a 32x32 multiply inherently generates a 64-bit result, so there is nothing inefficient about casting to a type larger than the system word size. The compiler will generate the correct 32x32->64 multiply instruction if it exists. And at least on i386, 64/32->32 division (when the upper 32 bits are less than the divisor) is an inherent feature of the 32-bit divide instruction, and does not require emulation in software by the compiler. On less intelligent 32-bit targets you might want to use 16-bit units though.. – Starrstarred

Doing a library call instead of inlining the whole operation on every instance, which the compiler in my experience always does with 64-bit builtin-operations on a 32-bit platform, may bloat the code size; though the inlined operation will most probably be faster. This is an issue I've encountered many times on 32-bit embedded ARM-platforms. – Arching

Answer 2

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.

Liu

Answer 3

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.

Olimpiaolin

There's one in Scott's answer. – Jowett

Answer 4

You can also use OpenSSL bn; it is already installed in Mac OS X.

Devoted

The link you provided is dead – Freesia

@Caltrop, see openssl.org/docs/man1.0.2/man3/bn.html but OpenSSL bn no longer comes installed in Mac OS X. – Devoted

Answer 5

You can print factorial 1000 in C with just 30 lines of code, <stdio.h> and char type :

#include <stdio.h>
#define B_SIZE 3000 // number of buffered digits

struct buffer {
    size_t index;
    char data[B_SIZE];
};

void init_buffer(struct buffer *buffer, int n) {
    for (buffer->index = B_SIZE; n; buffer->data[--buffer->index] = (char) (n % 10), n /= 10);
}

void print_buffer(const struct buffer *buffer) {
    for (size_t i = buffer->index; i < B_SIZE; ++i) putchar('0' + buffer->data[i]);
}

void natural_mul_buffer(struct buffer *buffer, const int n) {
    int a, b = 0;
    for (size_t i = (B_SIZE - 1); i >= buffer->index; --i) {
        a = n * buffer->data[i] + b;
        buffer->data[i] = (char) (a % 10);
        b = a / 10;
    }
    for (; b; buffer->data[--buffer->index] = (char) (b % 10), b /= 10);
}

int main() {
    struct buffer number_1 = {0};
    init_buffer(&number_1, 1);
    for (int i = 2; i <= 100; ++i)
        natural_mul_buffer(&number_1, i);
    print_buffer(&number_1);
}

You will find faster but the “little” factorial(10000) is here computed ≈ instantly.

You can put it into a fact.c file then compile + execute :

gcc -O3 -std=c99 -Wall -pedantic fact.c ; ./a.out ;

If you want to execute some base conversion there is a solution, see also Fibonacci(10000), Thank You.

Neocene

It would be readable in 40 lines of code... – Scarlatti