10000 factorial in C

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;
  }
}

This is my function to calculate 10000 factorial, and I have calculated the correct answer compared to online data. But, when I limit the n's range to [0.999], I can't even calculate 2000 factorial. Why when I transform the n' range to [0, 9999], then it can calculate 2000! even 10000!?

Your question almost makes sense, but not quite. "limit the n to [0.999]" and "transform the n to [0,9999]" are confusing. — Teepeemm, Sep 23 '15 at 14:48
1) Do not cast the result of `malloc` in C. 2) Do not write `type* ptr`, but `type *ptr`. This is no difference for the compiler, but it visually binds `*` to the type, not the name as it is fo rhte compiler (try `int* ip, i`: `i` is not a pointer as `int*` imlies to the reader). 3) Do not `typedef` a pointer! This hides the semantics and makes your code more complicated to read/understand. Only `typedef` normal types and use pointers explicitly. 4) you should use unsigned types. They have a well defined overflow behaviour. — too honest for this site, Sep 23 '15 at 14:52
What does happen when the program limiting `n` to `[0,999]` tries to calculate `2000!`? does it crash, or give a wrong answer? In what way is the answer wrong? Maybe post a complete (including whatever calls `factorial()`) program that shows the problem. — Michael Burr, Sep 23 '15 at 15:11
If n is [0,999] then it will give a wrong answer to 2000. Thanks very much for your suggestion for my code style for Olaf. — tian tong, Sep 23 '15 at 15:15
[Don't cast the result of `malloc` in C](http://stackoverflow.com/q/605845/995714) — phuclv, Sep 23 '15 at 15:53
This reminds me the time when I tried to compute factorial of one million (1 000 000!). I used different approach but I was able to get result in several hours using server at my work. Result is 5 565 709 digits long and ends with 249 998 zeros.Check it out [here](https://www.dropbox.com/s/9uj86x7y9qrhsmx/factorial%201%20000%20000.txt?dl=0) — icl7126, Sep 23 '15 at 18:03

Sergey Kalinichenko · Accepted Answer · 2015-09-23T15:33:59.490

10

The problem with limiting your digit cluster to three digits is that multiplying a three-digit number by a value above 1,000 may produces a carry into digit number four.

Although this does not create an immediate problem, the error will accumulate as you carry the value up the computation chain. With more than 5,000 digits in the result of 2000! the carry overflow would certainly produce a visible error in the result. This happens around 1258-th step of the computation of 2000!.

This does not happen with four-digit clusters and 10,000 because the only place where the carry could "spill" into the next digit is the computation of the very last cluster, and long long has plenty of space to accommodate this without an overflow.

edited Sep 23 '15 at 15:33

answered Sep 23 '15 at 14:56

Sergey Kalinichenko

714,442
84
1,110
1,523

The OP's question indicates that calculating `10000!` using 4 digit clusters in the node works, but that the code doesn't work when using 3 digit clusters in the node for even `2000!`, which has something less than 6000 digits. – Michael Burr Sep 23 '15 at 15:04
@MichaelBurr Ah, I read the thread of comments now, and I see what he's talking about. Will edit. – Sergey Kalinichenko Sep 23 '15 at 15:17

10000 factorial in C

1 Answers1