c - C 中的 10000 阶乘

Question

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

struct node;
typedef struct node* PtrToNode;

struct node {
  long long n;
  PtrToNode next;
};

PtrToNode factorial(int n, PtrToNode init);
void multiply(long long n, PtrToNode init, long long carry);

int main() {
  int n;
  while (1) {
    scanf("%d", &n);
    if (n > 0) {
      break;
    } else if (n == 0){
      printf("1\n");
      return 0;
    } else {
      printf("Retry.\n");
    }
  }
  PtrToNode init = malloc(sizeof(struct node));
  init->n = 1;
  init->next = NULL;
  PtrToNode head = factorial(n, init);
  PtrToNode tail = reverse(head);
  PtrToNode backup = tail;
  printf("%lld", tail->n);
  tail = tail->next;
  while(tail != NULL) {
    printf("%04lld", tail->n);
    tail = tail->next;
  }
  PtrToNode t;
  while (backup != NULL) {
    t = backup;
    backup = backup->next;
    free(t);
  }
}


PtrToNode factorial(int n, PtrToNode init) {
  for (int i = 1; i <= n; i++)
    multiply(i, init, 0);
  return init;
}

void multiply(long long n, PtrToNode init, long long carry) {
  long long temp = n * init->n + carry;
  init->n = temp % 10000;
  carry = temp / 10000;
  if (init->next != NULL) {
    multiply(n, init->next, carry);
  } else if (carry > 0) {
    init->next = malloc(sizeof(struct node));
    init->next->n = carry;
    init->next->next = NULL;
  } else {
    return;
  }
}

这是我计算10000阶乘的函数，对比网上资料我算出了正确答案。但是，当我将 n 的范围限制为 [0.999] 时，我什至无法计算 2000 阶乘。为什么当我将n'范围转换为[0, 9999]时，它可以计算出2000!甚至 10000!？

Answer 1

将数字簇限制为三位数的问题在于，将三位数乘以大于 1,000 的值可能会产生进位到四位数。

虽然这不会立即产生问题，但随着您将值沿计算链向上传递，错误会累积。 2000的结果有5000多位!进位溢出肯定会在结果中产生一个可见的错误。这发生在计算 2000! 的第 1258 步左右。

这不会发生在四位数的簇和 10,000 上，因为进位可以“溢出”到下一个数字的唯一地方是最后一个簇的计算，并且 long long 有很多足够的空间来容纳它而不会溢出。