Member Avatar for prashantsharmazz

KNOW THE LOGIC BEHIND FACTORIAL PROGRAM And CALCULATE FACTORIAL OF VERY LARGE NUMBERS !

WHat is the most efficient way of calculating the factorial of the number ?

  • 2 Contributors
  • 2 Replies
  • 130 Views
  • 7 Hours Discussion Span
  • Latest Post Latest Post by prashantsharmazz

Dani AI

Generated

Building on 's comment: the simple examples you find online are fine for learning, but they hit limits fast. Built-in types overflow quickly (signed 32-bit overflows at 13!, 64-bit at 21+), recursion will blow the stack for large inputs, and naive digit-by-digit arrays become painfully slow as the number of digits grows. The practical choices are (a) exact result for moderately large n using a big-integer library, (b) faster exact algorithms for very large n, or (c) approximations (number of digits or floating-point) when exact digits are not required.

For exact factorials in C++, use a big-int type such as Boost.Multiprecision::cpp_int or a GMP/MPIR-backed wrapper and avoid recursion. A simple iterative approach is easiest to read and fine up to thousands of digits:

#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;

cpp_int factorial(unsigned n) {
    cpp_int r = 1;
    for (unsigned i = 2; i <= n; ++i) r *= i;
    return r;
}

For much larger n, use balanced (“binary splitting”) multiplication or a prime-exponent method (Legendre’s formula to compute exponent of each prime, then fast power-and-multiply). Binary splitting multiplies ranges [1..n] by recursively splitting; it keeps intermediate operand sizes balanced and is much faster in practice than naive left-to-right multiplication.

To estimate size, use Stirling’s formula for digit count:
digits = floor( nlog10(n/e) + 0.5log10(2pin) ) + 1.
That tells whether exact computation is feasible.

Practical tips: store digits in a large base (e.g., 1e9) to reduce limb count, strip factors of 10 during intermediate multiplies to limit growth, use FFT-based big-int libraries for huge results, and precompute factorials if you need many queries. For modular factorials or combinatorics, different algorithms (modular inverse, Lucas, prime-sieve exponents) are needed.

Recommended Answers

All 2 Replies

Member Avatar for tinstaafl

That web page is a pretty good start.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.