递归阶乘函数程序为C中的大量输入返回0

Question

我编写了程序，使用递归进行阶乘计算，如课堂上所教。我观察到：大于 65 的数的阶乘始终给出 0 的输出。

//program to recursively calculate the value of factorial for a given integer!

#include <stdio.h>
#include <stdint.h>

unsigned long rfacta(uint32_t n){
    if(n>0)
        return rfacta(n-1)*n;
    else
        return 1;
}

unsigned long rfactd(uint32_t n){
    if(n>0)
        return n*rfactd(n-1);
    else
        return 1;
}

int main(void){
    uint32_t number, methd;
    unsigned long fctorial;
    printf(" Enter 0 for call-time recursion\n Enter 1 for return-time recursion\n Enter 2 to print the table of passible factorials on this system\n\n");
    scanf("%d",&methd);
    switch(methd){
    case 0:
        printf("Compute factorial for number = ? \n");
        scanf("%d",&number);
        fctorial = rfacta(number);
        printf("Factorial(%d) = %lu\n",number,fctorial);
    break;

    case 1:
        printf("Compute factorial for number = ? \n");
        scanf("%d",&number);
        fctorial = rfactd(number);
        printf("Factorial(%d) = %lu\n",number,fctorial);
    break;

    case 2:
      for(int i=0;rfacta(i)!=0;i++){
        printf("Factorial(%d) = %lu\n",i,rfacta(i));
      }
      break;

    default:
      printf("Incorrect entry! \n");
      break; 
    }
    return 0;
}

输出截图附件：阶乘返回0的递归程序

题：

正如我们在输出[附截图图像]中看到的那样，共有三个区域：

区域 1：在该区域中，阶乘的输出是正确的。这样做的原因是，

log2(20!) ~= 62, [这里 logm(n) 表示以 m 为基数的 n 的对数] 即假设是 64 位机器，那么在单个地址上可以正确表示的最大阶乘数是 20！，并且之后发生内存溢出，因为 log2(21!) ~= 65。因此，64 位地址无法表示如此大的数字。

区域 2：在该区域中，阶乘的值不为零但不正确。这样做的原因，如上所述，是因为阶乘值整数太大，无法用单个 64 位地址表示。因此，我们看到的函数输出实际上是随机的 64 位长无符号整数。

区域 3：对于 Factorial(n > 65)，factorial(n)=0。

我无法理解为什么 n>65，n！= 0 由程序返回？

据我所知，区域 2 必须继续而不是停止。但是它一直在我在 n=65 上尝试过我的代码的所有机器上停止让我感到困惑。预先感谢您的帮助。

Answer 1

如果你以十六进制打印值，发生的事情变得更加明显：

Factorial(0) = 0000000000000001
Factorial(1) = 0000000000000001
Factorial(2) = 0000000000000002
Factorial(3) = 0000000000000006
Factorial(4) = 0000000000000018
Factorial(5) = 0000000000000078
Factorial(6) = 00000000000002d0
Factorial(7) = 00000000000013b0
Factorial(8) = 0000000000009d80
Factorial(9) = 0000000000058980
Factorial(10) = 0000000000375f00
Factorial(11) = 0000000002611500
Factorial(12) = 000000001c8cfc00
Factorial(13) = 000000017328cc00
Factorial(14) = 000000144c3b2800
Factorial(15) = 0000013077775800
Factorial(16) = 0000130777758000
Factorial(17) = 0001437eeecd8000
Factorial(18) = 0016beecca730000
Factorial(19) = 01b02b9306890000
Factorial(20) = 21c3677c82b40000
Factorial(21) = c5077d36b8c40000
Factorial(22) = eea4c2b3e0d80000
Factorial(23) = 70cd7e2933680000
Factorial(24) = 9343d3dcd1c00000
Factorial(25) = 619fb0907bc00000
Factorial(26) = ea37eeac91800000
Factorial(27) = b3e62c3358800000
Factorial(28) = ad2cd59dae000000
Factorial(29) = 9e1432dcb6000000
Factorial(30) = 865df5dd54000000
Factorial(31) = 4560c5cd2c000000
Factorial(32) = ac18b9a580000000
Factorial(33) = 2f2fee5580000000
Factorial(34) = 445da75b00000000
Factorial(35) = 58cde17100000000
Factorial(36) = 7cf3b3e400000000
Factorial(37) = 0f38fff400000000
Factorial(38) = 4275fe3800000000
Factorial(39) = 1ff9ba8800000000
Factorial(40) = ff05254000000000
Factorial(41) = d7d2f74000000000
Factorial(42) = 689c908000000000
Factorial(43) = 924c458000000000
Factorial(44) = 251bf20000000000
Factorial(45) = 85e98a0000000000
Factorial(46) = 0ff6cc0000000000
Factorial(47) = ee4f740000000000
Factorial(48) = aee5c00000000000
Factorial(49) = 79f9c00000000000
Factorial(50) = d2c7800000000000
Factorial(51) = fdbe800000000000
Factorial(52) = 8ab2000000000000
Factorial(53) = b6da000000000000
Factorial(54) = 91fc000000000000
Factorial(55) = 5d24000000000000
Factorial(56) = 5fe0000000000000
Factorial(57) = 58e0000000000000
Factorial(58) = 22c0000000000000
Factorial(59) = 0240000000000000
Factorial(60) = 8700000000000000
Factorial(61) = 2b00000000000000
Factorial(62) = 6a00000000000000
Factorial(63) = 1600000000000000
Factorial(64) = 8000000000000000
Factorial(65) = 8000000000000000

随着您继续乘以包含 2 作为因子的值，尾随零的数量继续增加。当您乘以 66 时，所有非零位都已向左推出，因此剩下 0。

此外，值来自 21! 到 65！实际上不是随机值，而是结果的低位 64 位。无符号整数算术以模 2 ^bitlen执行，其中“bitlen”是所讨论类型的位长度，在这种情况下为 64。

Answer 2

只要您乘以二进制补码和换行（C 标准不保证，但似乎发生在您的程序中），计算结果就是完整的数学结果（无换行）模 2 ⁶⁴。

对于n > 65，n！是 2 ⁶⁴的倍数（从 1 到 66 的因数包括 64 或更多的二），因此模 2 ⁶⁴的值为零：

• 当您乘以 2 时，将提供 2 的一个因数。
• 当您乘以 4 时，会提供两个因子。
• 当您乘以 6 时，将提供一个因子。
• 当您乘以 8 时，将提供三个因子。
• n中 2 的因数的总数！是n /2 + n /4 + n /8 + ...，使用整数算术（即截断除法，所以 3/2 = 1）并继续直到该项达到零。对于 66!，这是 66/2 + 66/4 + 66/8 + 66/16 + 66/32 + 66/64 = 33 + 16 + 8 + 4 + 2 + 1 = 64。