Sign in to follow this  
TheOddMan

Just a crazy fool who needs to know...

Recommended Posts

TheOddMan    100
This might seem like a weird question, but I just *have* to know. I wrote a short and sweet program to calculate factorials:
#include "stdafx.h"
#include <iostream>
using namespace std;

unsigned int Factorial( unsigned int in )
{
	if( 1 == in )
	{
		return 1;
	}

	return in + ( Factorial( in - 1 ) );
}

int _tmain(int argc, _TCHAR* argv[])
{
	unsigned int theX = 4, theFact;
	while( theX >= 0 )
	{
		cout << "Enter number:  ";
		cin >> theX;
		theFact = Factorial( theX );
		cout << "\n" << theX << "! is:  " <<  theFact << endl;
	}

	return 0;
}
When I run it the program can only handle values of up to 4795 as an imput value (4795! is 11498110 by the way). If I enter any higher number it shuts down. I've tried using different data types, but the same thing happens. My question is this: Why does this limitation exist? I know this is an odd question, but like I said, I *need* to know. [grin]

Share this post


Link to post
Share on other sites
SiCrane    11839
Well, one, 4795! is a lot bigger than 11498110.

Two, the factorial funciton is the culmutive multplication of successive integers, not the addition. ie.
in + ( Factorial( in - 1 ) )

should be
in * ( Factorial( in - 1 ) )


Three, I'm guessing you're getting a stack overflow, which is what happens when you recurse too deeply.

Share this post


Link to post
Share on other sites
Sneftel    1788
By my calculations, the actual value of 4795! is approximately 1015567. It is, in other words, rather large.

Share this post


Link to post
Share on other sites
Thygrrr    418
Quote:
Original post by Sneftel
By my calculations, the actual value of 4795! is approximately 1015567. It is, in other words, rather large.


Yup, rather.

The largest most 10-digit-calculators can display is 69!, which is 1.71122452 × 10^98, or...

171122452000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

:)

Share this post


Link to post
Share on other sites
silverphyre673    454
If you need to write the program so it can handle larger values, there are some math APIs out there that have perfect-precision data types that you could use. Of course, they would also almost certainly have a factorial function, which would probably be heavily optimized. If this is your own personal project, then just do what you need to =)

Share this post


Link to post
Share on other sites
etothex    728
There are much better ways of calculating factorials than recursion or even iteration through all the numbers. The factorial example is just used by programming teachers because it is a good way of learning recursive algorithms. :)

Share this post


Link to post
Share on other sites
TheOddMan    100
Yeah, I know there are probably a lot of much better optimisations out there. I was just messing around really and I saw this weird limit which seemed to have nothing to do with the size of an int, and it bugged me that I didn't know why. Of course a useful side-effect of this curiosity was learning that I knew *nothing* about factorials. ;)

By the way I rewrote it so it actually *does* do factorials. It's slightly worse than a calculator! Anything above 65! it pumps out a zero. That's using unsigned __int64 as the data type.

Share this post


Link to post
Share on other sites
erissian    727
Quote:
Original post by Sneftel
By my calculations, the actual value of 4795! is approximately 1015567. It is, in other words, rather large.


I can't believe it only took you half an hour to work that out! I'm only up to 1768! so far!

:)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this