0

Consider problem of calculating factorial of a number. When result is bigger than 2^32 then we will get overflow error. How can we design a program to calculate factorial of big numbers?

EDIT: assume we are using C++ language.

EDIT2: it is a duplicate question of this one

Community
  • 1
  • 1
ashim
  • 24,380
  • 29
  • 72
  • 96
  • 1
    possible duplicate of [Calculating factorial of large numbers in C](http://stackoverflow.com/questions/1384160/calculating-factorial-of-large-numbers-in-c). Though you don't mention C directly, the mention of 32-bit ints indicates you'r using something similar enough for the answers there to apply. – Jerry Coffin Jan 26 '13 at 23:29

8 Answers8

2

As a question with just algorithm tagged. Your 2^32 is not an issue because an algorithm can never have an Overflow error. Implementations of an algorithm can and do have overflow errors. So what language are you using?

Most languages have a BigNumber or BigInteger that can be used.

Here's a C++ BigInteger library: https://mattmccutchen.net/bigint/

I suggest that you google for: c++ biginteger

Richard Schneider
  • 34,944
  • 9
  • 57
  • 73
1

If you can live with approximate values, consider using the Stirling approximation and compute it in double precision.

If you want exact values, you'll need arbitrary-precision arithmetic and a lot of computation time...

Memming
  • 1,731
  • 13
  • 25
1

Doing this requires you to take one of a few approaches, but basically boils down to:

  1. splitting your number across multiple variables (stored in an array) and
  2. managing your operations across the array.

That way each int/element in the array has a positional magnitude and can be strung together in the end to make your whole number.

A good example here in C: http://www.go4expert.com/forums/c-program-calculate-factorial-t25352/

Matthew
  • 9,851
  • 4
  • 46
  • 77
1

Test this script:

import gmpy as gm 
print gm.fac(3000)

For very big number is difficult to stock or print result.

sanguinarius
  • 21
  • 4
1

For some purposes, such as working out the number of combinations, it is sufficient to compute the logarithm of the factorial, because you will be dividing factorials by factorials and the final result is of a more reasonable size - you just subtract logarithms before taking the exponential of the result.

You can compute the logarithm of the factorial by adding logarithms, or by using the http://en.wikipedia.org/wiki/Gamma_function, which is often available in mathematical libraries (there are good ways to approximate this).

mcdowella
  • 19,301
  • 2
  • 19
  • 25
0

First invent a way to store and use big numbers. Common way is to interpret array of integers as digits of a big number. Then add basic operations to your system, such as multiplication. Then multiply.

Or use already made solutions. Google for: c++ big integer library

Dialecticus
  • 16,400
  • 7
  • 43
  • 103
0

You can use BigInteger for finding factorial of a Big numbers probably greater than 65 as the range of data type long ends at 65! and it starts returning 0 after that. Please refer to below Java code. Hope it would help:

import java.math.BigInteger;

public class factorial {

public factorial() {
        // TODO Auto-generated constructor stub
    }
    public static void main(String args[])
    {
        factorial f = new factorial();


        System.out.println(f.fact(100));
    }
    public BigInteger fact(int num)
    {
        BigInteger sum = BigInteger.valueOf(1);

        for(int i = num ; i>= 2; i --)
        {
            sum = sum.multiply(BigInteger.valueOf(i));
        }
        return sum;

    }
}
Brian Tompsett - 汤莱恩
  • 5,753
  • 72
  • 57
  • 129
Madhumita Sehgal
  • 1
0

If you want to improve the range of your measurement, you can use logarithms. Logarithms will convert your multiplication to additions making it much smaller to store.

factorial(n) => n * factorial(n-1) 
log(factorial(n)) => log(n) * log(factorial(n-1))

5! = 5*4*3*2*1 = 120
log(5!) = log(5) + log(4) + log(3) + log(2) + log(1) = 2.0791812460476247

In this example, I used base 10 logarithms, but any base works.

10^2.0791812460476247

Or 10^0.0791812460476247*10^2 or 1.2*10^2

Implementation example in javascript

Alexis Paques
  • 1,885
  • 15
  • 29