Thread: (Double) Factorial function efficiency

  1. #1
    Registered User
    Join Date
    Oct 2011

    Question (Double) Factorial function efficiency

    My question is, if I'm using double factorial in my program, should I :
    1. implement function just for the double factorial (actually, two functions for odd and even numbers)
    2. just implement simple recursive function for factorial
    3. implement factorial the other way than recusive

    note that I am using only ()!! and there are formulas for converting ()!! into ()!, so it wouldn't be very difficult.

    also, what is very important, which function will have the best efficiency?

    Thank you :-)
    [COLOR=#fafafa !important]


  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    The edge of the known universe
    Using a simple loop to calculate factorial will never be worse than any recursive implementation.

    Factorial grows so quickly that it's feasible to cache all the answers in an array as you calculate them.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Jun 2005
    Quote Originally Posted by Salem View Post
    Factorial grows so quickly that it's feasible to cache all the answers in an array as you calculate them.
    Indeed. 22! is too big to be stored in a 64 bit unsigned type. Only 21 results to be computed, and that's assuming your compiler supports a 64 bit unsigned type (relatively few systems support larger types than that natively).

    I agree with you a loop is the best way to do it .... if you actually must do it.

    In general, it is a rare real-world program that genuinely needs to compute factorial of a large integer. Most times when I see people asking how to compute a factorial, it is because of a lack of thought. For example, computing x^n/n! (where ^ represents power, for sake of discussion here) requires neither the computation of x^n nor n! as intermediate steps. The computation of n! overflows quite quickly, and the computation of x^n will overflow fairly quickly if x > 1 or underflow if x < 1. Computing them as intermediate steps is a really bad idea. With a little thought it is possible to compute the end result with a much smaller risk of overflow or underflow. For example;
    //  compute  x^n/n!
    for (i = 1; i <= n; ++i)
          result *= x;
          result /= i;
    avoids computing a power of x directly, avoids computing a factorial, and successfully computes x^n/n! for much larger values of x or n. The risks of overflow or underflow are not eliminated, but they are reduced.

    So my view is that the original question is, more than likely, the wrong question due to lack of thought.

    If your program genuinely needs to compute factorials of largish values (and, as noted above, relatively few programs truly do in the real world) then you will need to use some unbounded integral representation. There are libraries for such things around.
    Last edited by grumpy; 10-11-2011 at 02:53 AM.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help using factorial function...
    By wco5002 in forum C++ Programming
    Replies: 19
    Last Post: 11-10-2007, 07:42 AM
  2. function efficiency
    By shuo in forum C++ Programming
    Replies: 4
    Last Post: 07-03-2007, 09:56 PM
  3. String to Double function
    By jaro in forum C Programming
    Replies: 4
    Last Post: 05-27-2006, 11:10 AM
  4. Factorial function ?
    By koolguysj in forum C Programming
    Replies: 11
    Last Post: 04-01-2005, 11:28 PM
  5. recursive factorial function
    By brianptodd in forum C++ Programming
    Replies: 6
    Last Post: 05-08-2003, 12:56 AM

Tags for this Thread