10000 факториал в C 

#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!?

Ответы

Ответ 1

Проблема с ограничением вашего кластера цифр на три цифры заключается в том, что умножение трехзначного числа на значение выше 1000 может привести к переносу в цифру четыре.

Хотя это не создает непосредственной проблемы, ошибка будет накапливаться при переносе значения в цепочку вычислений. С более чем 5000 цифр в результате 2000! переполнение переполнения, несомненно, вызовет видимую ошибку в результате. Это происходит вокруг 1258-го шага вычисления 2000!.

Это не происходит с четырехзначными кластерами и 10 000, потому что единственное место, где перенос может "разливаться" в следующую цифру, - это вычисление самого последнего кластера, а long long имеет достаточно места для размещения этого без переполнение.