How Can We Calculate the Factorial of Arbitrarily Large Numbers Without External Libraries?

Determining the Factorial of Large Numbers

The computation of factorials poses a challenge when the results exceed the limits of native datatypes. This article presents a technique for calculating factorials of arbitrarily large integers, revealing all the digits in the solution.

Simulating Manual Calculation

In the absence of external libraries like GMP, we must mimic the process of manual factorial calculation using an array of integers. This array represents the large number, with each index holding a digit.

Factorial Calculation Algorithm

For a number n, the factorial is computed as follows:

1. Multiply each digit in the array by n.
2. Store the result in the same array, with proper carry handling.
3. Call the algorithm recursively with n-1 until reaching 1 or 0.

Example Implementation

The provided C code implements the above algorithm:

#include <iostream>
#include <cstring>

int max = 5000;

void display(int arr[]) {
  int ctr = 0;
  for (int i = 0; i < max; i++) {
    if (!ctr && arr[i]) ctr = 1;
    if (ctr) std::cout << arr[i];
  }
}

void factorial(int arr[], int n) {
  if (!n) return;
  int carry = 0;
  for (int i = max - 1; i >= 0; --i) {
    arr[i] = (arr[i] * n) + carry;
    carry = arr[i] / 10;
    arr[i] %= 10;
  }
  factorial(arr, n - 1);
}

int main() {
  int *arr = new int[max];
  std::memset(arr, 0, max * sizeof(int));
  arr[max - 1] = 1;
  int num;
  std::cout << "Enter the number: ";
  std::cin >> num;
  std::cout << "Factorial of " << num << " is :\n";
  factorial(arr, num);
  display(arr);
  delete[] arr;
  return 0;
}

The above is the detailed content of How Can We Calculate the Factorial of Arbitrarily Large Numbers Without External Libraries?. For more information, please follow other related articles on the PHP Chinese website!