What is the simplest way of implementing bigint in C?

user_269106 0
Viewed 42256

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.

bigint c
5 Answers

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.

user_187656270
Related