Big Integer Problem While Dealing With Factorials

Question

The following code has a problem that I can't solve:

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

int factorial(long long int x) {
    long long int temp;
    temp = x - 1;

    for (; temp > 0; temp--) {
        x = x * temp;
    }
    return x;
}

int main() {
    long long int x, fact;

    while (1) {
        printf("Please enter the number that you want to learn factoriel...\n(To quit press ctrl+c)\n");
        scanf("%lld", &x);

        if (x == EOF) {
            break;
        }

        if (x >= 0) {
            fact = factorial(x);
            printf("Factorial of %lld is %lld\n", x, fact);
        } else {
            fact = 0;
            printf("Factorial of %lld is %lld\n", x, fact);
        }
    }

    printf("The Program has successfully terminated...\n");
    return 0;
}

First of all, it works until 17 but at 17 it gives me a negative bunch of numbers as a result and a couple numbers later it gives me 0 as a result

How do I fix this?

You have reached the limit of the built-in type. It can't hold that big numbers. If you search the net it's quite easy to find libs that supports "bigger" numbers - actually libs with no limitations. Alternatively you can write your own special type - for instance by keeping the result in array of 1000 `long long unsigned` - or better in a variable length array of `long long unsigned`. — Support Ukraine, Apr 15 '20 at 13:26
You can get a little further if you change the return type of `factorial` from `int` to `long long`. It doesn't help to calculate the factorial using `long long` internally if you convert it to an ordinary `int` before returning it, as you do now. You can also add a tiny bit of range (which may or may not help) by using `unsigned long long` instead of (signed) `long long`. — Tom Karzes, Apr 15 '20 at 13:30
@TomKarzes i tried it but it didnt make that much difference, thx for advice... — Dasty Dustleg, Apr 15 '20 at 13:35
17! is 355687428096000 . The upper bound of a 64 bit signed long long int is 9223372036854775808. I wonder what data types your compiler is using? — nicomp, Apr 15 '20 at 13:37
@DastyDustleg If the return type is `int`, then you might as well use `int` in place of `long long` everywhere. It makes no sense to mix them as you do now. The `int` is the weakest link in the chain. Using `long long` or `unsigned long long` will get you a little further, but factorial grows exponentially so you will run into a limit quickly even it you do. — Tom Karzes, Apr 15 '20 at 13:37
@nicomp i dont know what data types my copiler using but, i am using gcc in ubuntu — Dasty Dustleg, Apr 15 '20 at 13:40
Are you trying to calculate some property of the factorial this way? I'm wondering how you'll use a higher-precision result, and if there's another way to achieve your goal that doesn't require the added precision. For example, I've seen problems that ask things like "How many trailing zeros does a factorial have?", in which case you can get the answer without actually calculating the factorial. — Tom Karzes, Apr 15 '20 at 13:41
@TomKarzes i tried to change the type of factorial function to long long and now it works until 40 , is there any idea to improve this? :) — Dasty Dustleg, Apr 15 '20 at 13:46
@DastyDustleg for what purpose do you want to calculate factorial for numers that large? If just want to know their factorial use wolfram alpha. — Ackdari, Apr 15 '20 at 13:51
I doubt your result for 40 factorial is correct. If your `long long` is 64 bits, then you won't get close to 40 factorial. You're probably just getting some garbage value, possibly the low-order bits of the result. — Tom Karzes, Apr 15 '20 at 13:55
The easiest way to get extended precision integer results is to use a language that has builtin support for it, for example something like Python. If you really want to do it in C, then you will need to use an extended precision integer arithmetic package, or write your own (which I'm guessing you won't be able to do). — Tom Karzes, Apr 15 '20 at 13:58
@TomKarzes yes youre right i am not be able to do :) ,Thx for help ,but i will try to write :)) — Dasty Dustleg, Apr 15 '20 at 14:02
@DastyDustleg if you want to write it your own you might want to check out the [BitInteger](https://github.com/dotnet/runtime/blob/2eef5a3dc0f9afeb07a1aada1c5312fc013b7871/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs#L2020) implementation of the .net-core runtime — Ackdari, Apr 15 '20 at 14:18
otherwise I would suggest using one of [these](https://en.wikipedia.org/wiki/List_of_arbitrary-precision_arithmetic_software) libs — Ackdari, Apr 15 '20 at 14:19

Jose · Accepted Answer · 2020-04-15T14:12:09.717

The problem is that you are overflowing the variable, it means that sizeof(variable) bytes have been reserved to store the number, however the number needs more bytes than the reserved ones.

A uint32_t gives you a range of 0 to 2^32=4,294,967,296 so you won't be able to (properly) store the number 5000000000, same with any other integer type.

There are some choices:

Use unsigned instead of signed (if only positive numbers are needed) to extend the range
Use a larger data type (again, to increase the range)
Split the number into an array (using array to store big numbers)
Use arbitrary precision https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic#Libraries (Arbitrary-precision arithmetic Explanation)
Scale your numbers (if the next addition is going to be bigger than 2^bits, apply a factor)

The price is that excepts the first (and depending on the situation, the second) one, all the options increase the CPU consumption.

Big Integer Problem While Dealing With Factorials

1 Answers1