在C中处理大于ULONG_MAX的数字

Question

假设我在c中有一个阶乘程序，在某一点上，它最终将计算一个大于<limits.h>中定义的ULONG_MAX的值。我有几个问题:

1. 如何查看计算值是否因大于ULONG_MAX而溢出

2. 我是否限制用户输入，使他们不能计算n! > ULONG_MAX的n!?

3. C有可能处理更大的数字吗?

Answer 1

下面是一个小程序，用于确定其阶乘适合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! = %llun", i - 1, factorial);
return 0;
}

输出:Maximum number is: 20! = 2432902008176640000

更进一步，如果您的系统可用，您可以使用更大的整数类型:

#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] = '';
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! = %sn",
int128toa(buf1, i - 1), int128toa(buf2, factorial));
return 0;
}

输出:Maximum number is: 34! = 295232799039604140847618609643520000000

这仍然是一个相当小的数字。阶乘呈指数增长

对于较大的数字，您可以使用bignum包，其中数字在分配的数组中表示，仅受可用内存的大小限制。一个广泛使用的是GNU多精度包gmp.h.

下面是一个简单的程序，用于计算存储为字符串的较大阶乘:

#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] = '';
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! = %sn", n, strrev(p));
free(p);
return 0;
}

输出:

<>前100 !div = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000