CODEWITHSUNDEEP
calgorithmmaxfactorialunsigned-long-long-int
Eifel
Eifel

Reputation: 53

How to determine the maximum value for which a program can calculate factorial using unsigned long long?

How to write a proper algorithm in C that determines the maximum value for which the program can calculate factorial using unsigned long long int?

My example does not work properly. Using Linux/64bit and GCC, it gives me 65 iterations.

#include <stdio.h>

int main() {
    unsigned long long int num, i;
    unsigned long long int factorial = 1;
    num = 1;
    for (i = 1; i <= num; i++) {
        factorial = factorial * i;
        num++;
        if (factorial <= 0) {
           printf("\nMaximum number is: %d\n", i - 1);
           break;
        }
    }
}

Upvotes: 4

Views: 838

Answers (1)

chqrlie
chqrlie

Reputation: 144989

Your program does not work properly because:

  • factorial is always >= 0 because it has an unsigned type. The only reason the program stops is factorial eventually becomes 0 once you multiply enough times by 2 or a multiple of 2.
  • you cannot reliably detect overflow by testing the resulting value: unsigned arithmetics are performed modulo 2 to the power of the number of value bits, so you could compare the result with the previous factorial and break if it is smaller. Note however that signed arithmetic overflow actually has undefined behavior, so testing that the result becomes negative is always wrong.

A more reliable approach is checking for overflow before performing the multiplication:

#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

Upvotes: 5

Related Questions