Factorial calculation

[guest]

how can we calculate 73! through a C program ?

[Tim]

73! = 73 * 72!
72! = 72 * 71!
...
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!
0! = 1

It shouldn't be too hard to write a C program to do the above. This is pretty easy for a homework problem.

[guest]

What type of variable should i use to hold the result.

[BI lazy]

May I give you a Hint? Use recursion.

Hmm... I suggest long. (will a normal 32 bit integer hold 73! ? dunno)

[Schol-R-LEA]

Ask yourself:

Is it a simple data type or a complex one?

• If it is a simple type, is it a character, a number, or true/false value?
  • If it is a character, then it's type [tt]char[/tt].
  • If it is a number, is it a decimal fraction or an exact whole number?
    • If it is a whole number, then is it less than 32767, or more than 214743647?
      • If you know it is less than 32767, then you can use [tt]short int[/tt], [tt]int[/tt], or [tt]long int[/tt].
      • If you know it is less than 214743647, then you can use [tt]int[/tt] or [tt]long int[/tt].
      • If it might be more than 214743647, then you would need to use [tt]long int[/tt], or a floating-point type.
        
        Also, if you know it will never be negative, you can add the keyword [tt]unsigned[/tt] in front of the type. This has the added effect of doubling the size that the number can be (65535 for [tt]unsigned short int[/tt], 4294967295 for [tt]unsigned int[/tt]).
    • If it might be a fraction, then you would need to use [tt]float[/tt] or [tt]double[/tt].
  • If it is a true/false value, it would be [tt]int[/tt].
• If it is a complex type, you would use a [tt]struct[/tt], which you would then define the parts of using simpler types.

I know that this doesn't answer the question directly, but it should show you how to figure out what type it should be. HTH.

[Schol-R-LEA]

To explain BI Lazy's comment, recursion is where a function is defined in terms of itself; to implement it, you would have to use the terminal cases (those cases which give a known constant) to test whether to make the next call. To do this, use the definition of factorial to your advantage:

0! == 0 - terminal case
1! == 1 - terminal case
n! == n * (n - 1)! - non-terminal case, repeats until you reach n == 1

So when n == 6, n! is
6 * 5!
6 * (5 * 4!)
6 * (5 * (4 * 3!))
6 * (5 * (4 * (3 * 2!)))
6 * (5 * (4 * (3 * (2 * 1!))))
6 * (5 * (4 * (3 * (2 * (1))))) /* terminal case, so the function returns */
6 * (5 * (4 * (3 * (2))))
6 * (5 * (4 * (6)))
6 * (5 * (24))
6 * 120
720

This should also give you some idea of how fast factorials increase; clearly, 73! will be a huge number, probably too large even for an [tt]unsigned long[/tt]. Keep in mind that you can use a float or a double to hold an int (though not always an exact value), but not the reverse, and that the largest number type in most versions of C is [tt]double[/tt] (though newer compilers may have a [tt]long double[/tt] type that's even larger).

HTH.

[BI lazy]

Good explanation. One uses recursion with kinda implicitness, especially after having coded several Directory crawling and Binary Tree and Window Tree (gui managing stuff) data structures - well, and graph isomorphism - they are recursive structures, so why not accessing them in a recursive manner?

Good exercise on this matter is: How many *different* combinations are possible in a given set of elements say {1,2,3,4}. The factorial function alongside some element switching tricks will give a good answer . Hint: for each exchanged element, you have to do all the previous changes too (*gg* this one 's been hard for me to grasp for I am far away from being a theorist).

For further explanation on that kind of stuff, check out Sedgewick: "Algorithms in C" (or so). That's a good one with loads of interesting algorithms and nifty tricks.

[sonneveld]

You might be better off writing it in non-recursive format though because you'll just be eating up stack for no reason at all.

I find recursive solutions are good for problems where you would create a stack anyway (like going through a tree) since you're effectively putting stuff on the stack anyway by calling a new function and creating a bunch of new local variables.

Reminds me of one guy trying to write USB drivers for the linux kernel. He had a function that tried to allocate aligned memory. It worked by trying to allocate some and, if it wasn't properly aligned, the function called *itself* to try again. Essentially it was just eating up stack until it managed to allocate memory that was correctly aligned.

- Nick

[BI lazy]

Right you are.

Recursion where Recursion is due, one could say.

Some problems are better solved the iterative way.

But for a homework - just to impress the teacher *gg* - I'd do the factorial thing with recursion *hehe*. Later, in business live, one recognizes soon enough, where to use what.

[Schol-R-LEA]

IIUC, it has been proven that for any computable iterative algorithm, there is an equivalent computable recursive algorithm, and vis versa. In general, iterative algorithms are more efficient in space than recursive ones, but many recursive functions are more efficient in time. Also, if you are using a compiler that optimizes tail calls, then tail recursion is exactly as efficient as iteration (technically, what TCO does is replace the call with a jump, effectively converting it to an iterative algorithm). Hey, I'm a Schemer, you should have seen this coming...

There are a lot of problems where a recursive algorithm is far simpler than the equivalent iterative one; classic examples of this are the Fibonacci function, Ackerman's function, the returned-change problem, and numeric print functions. OTOH, it is unusual for a problem to be substantially easier as an iterative algorithm than a recursive one.

The factorial function is roughly the same difficulty either way, which is why it is often used to demonstrate the difference between the two approaches. If the teacher is any good, they'll probably want you to try it both ways, for this very reason.

For more flavor, you might want to look at the recent exponentiaion function thread, and in particular compare the iterative solutions with the recursive ones later in the thread; the recursive version is slightly simpler, but uses more memory.

[CESS.tk]

0! == 0 - terminal case
1! == 1 - terminal case
n! == n * (n - 1)! - non-terminal case, repeats until you reach n == 1

I'm afraid 0! == 1.

It's true that a for-loop is a better choice then recursion in this case. (As a general rule, only use recursion when it devides the problem in 2 or more more or less equal parts, resulting in log(n) time, in this case the problem is devided in a constant part and a n-1 part, making it no faster - and reality even slower - then a for-loop)

The big problem with factorial calculation however is the rapid growing numbers. I don't know how programs like Maple solve this, but I'm pretty sure it's by deviding the problem into smaller parts and pasting the results together. I tried my hand at a first optimization in the following Java-code (don't know C, sorry), it cuts of some of the 0's at the end of the result:

Code: Select all

public static String faculty (int n) {
    int nrOfZeros = 0;
    long resultWithoutZeros = 1;
    for (int i = n; i > 1; i--)
        if (i % 5 == 0) {
           nrOfZeros++;
           resultWithoutZeros *= (i * --i) / 10;
       }
       else
           resultWithoutZeros *= i;
    String result = "" + resultWithoutZeros;
    for (int i = 0; i < nrOfZeros; i++)
       result += "0";
    return result;
}

But I'm afraid this is far from satisfying. I ran this version against a non-optimized version. The non-optimized one returns correct values op to 20! The optimized version above can evaluate anything up to 23!
(Both might work better in C, if C-longs are bigger than Java-longs)

I'm afraid I can't help you with 73!, except for that the answer is 4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000000, and that it contains 106 digits.

[Schol-R-LEA]

0! == 0 - terminal case
1! == 1 - terminal case
n! == n * (n - 1)! - non-terminal case, repeats until you reach n == 1

I'm afraid 0! == 1.

Oops. You're right.
[me=Schol-R-LEA]kicks self for carelessness. [/me]

It's true that a for-loop is a better choice then recursion in this case. (As a general rule, only use recursion when it devides the problem in 2 or more more or less equal parts, resulting in log(n) time, in this case the problem is devided in a constant part and a n-1 part, making it no faster - and reality even slower - then a for-loop)

Just so; however, the recursive version is slightly easier to write and understand, and is often used as an example of recursion in general.

[John]

Code: Select all

void main()
{
   double ans=1.0;
   int i,no;
   printf("Enter no: "); scanf("%d",&no);
   for(i=1;i<=no;i++)
      ans*= (double)i;
   printf("\nfact= %.20e",ans);
}

A double should be enogh for this.

[Tim]

A double should be enogh for this.

Depends how much accuracy you want. Where I come from, a double is 64 bits in total. It can represent the number 73!, but not to enough significant figures to represent it completely accurately. An int wouldn't lose accuracy, but you would be limited by the maximum. A 64-bit integer overflows between 20! and 21!, so the highest number a 64-bit double can represent accurately is somewhat smaller than 20!.

[Pype.Clicker]

1. modern C compilers support "tail-recursion" optimisation: you write recursive functions and the compiler makes loops.
2. 73! is likely to require a LargeNumbers library support. Some exists for C, but langages like LISP or Scheme have it built-in ... so if you're just interrested in the final result ...