Handling numbers in C larger than ULONG_MAX

Question

Say I had a factorial program in C. At one point, it will eventually calculate a value bigger than ULONG_MAX as defined in <limits.h>. I have a few questions about this:

How do I check whether the calculated value has overflowed due to being larger than ULONG_MAX?
Do I restrict the user input so that they can't calculate n! where n! > ULONG_MAX?
Is it possible for C to handle larger numbers?

1. https://stackoverflow.com/questions/1815367/catch-and-compute-overflow-during-multiplication-of-two-large-integers — PiRocks, Feb 08 '21 at 21:44
As an answer to question #3, [here](https://en.wikipedia.org/wiki/List_of_arbitrary-precision_arithmetic_software) is a list of software libraries which support [arbitrary-precision arithmetic](https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic). — Andreas Wenzel, Feb 08 '21 at 21:45
2. If you know `ULONG_MAX` you can figure out the n which causes overflow(won't be very big). If `ULONG_MAX` could be any arbitrary number you need to do fairly fancy math, https://mathoverflow.net/questions/12828/inverse-gamma-function can help with that. To avoid the fancy math precompute for all likely values of `ULONG_MAX` — PiRocks, Feb 08 '21 at 21:48

chqrlie · Answer 1 · 2021-02-08T23:56:06.033

Here is a small program to determine the maximum number whose factorial fits in an unsigned long long:

#include <limits.h>
#include <stdio.h>

int main(void) {
    unsigned long long int i, factorial;
    for (i = factorial = 1; factorial <= ULLONG_MAX / i; i++) {
        factorial = factorial * i;
    }
    printf("\nMaximum number is: %llu! = %llu\n", i - 1, factorial);
    return 0;
}

Output: Maximum number is: 20! = 2432902008176640000

To go beyond that, you can use larger integer types if available on your system:

#include <stdio.h>

char *int128toa(char *dest, __uint128_t n) {
    int i = 0, j = 0;
    do {
        dest[i++] = '0' + (n % 10);
    } while (n /= 10);
    dest[i] = '\0';
    while (i --> j) {
        char c = dest[i];
        dest[i] = dest[j];
        dest[j++] = c;
    }
    return dest;
}

int main(void) {
    char buf1[sizeof(__uint128_t) * 4];
    char buf2[sizeof(__uint128_t) * 4];
    __uint128_t i, factorial, uint128_max = ~(__uint128_t)0;
    for (i = factorial = 1; factorial <= uint128_max / i; i++) {
        factorial = factorial * i;
    }
    printf("\nMaximum number is: %s! = %s\n",
           int128toa(buf1, i - 1), int128toa(buf2, factorial));
    return 0;
}

Output: Maximum number is: 34! = 295232799039604140847618609643520000000

That's still a pretty small number. Factorials grow exponentially.

For larger numbers, you would use a bignum package where numbers are represented in allocated arrays limited in size only by available memory. A widely available one is the GNU multiprecision package gmp.h.

Here is a simplistic program to compute larger factorial stored as strings:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *strrev(char *s) {
    size_t j = 0, i = strlen(s);
    while (i --> j) {
        char c = s[i];
        s[i] = s[j];
        s[j++] = c;
    }
    return s;
}

char *mulstr(char *s, int n) {
    size_t i = 0;
    int carry = 0;
    while (s[i]) {
        carry += n * (s[i] - '0');
        s[i++] = '0' + carry % 10;
        carry /= 10;
    }
    while (carry) {
        s = realloc(s, i + 2);
        s[i++] = '0' + carry % 10;
        carry /= 10;
    }
    s[i] = '\0';
    return s;
}

char *factorial(int n) {
    char *f = strdup("1");
    for (int i = 2; i <= n; i++) {
        f = mulstr(f, i);
    }
    return f;
}

int main() {
    int n = 100;
    char *p = factorial(n);
    printf("%d! = %s\n", n, strrev(p));
    free(p);
    return 0;
}

Output:

100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Handling numbers in C larger than ULONG_MAX

1 Answers1

Linked