Hi All
Can somebody give me a simple c++ program to findout n factorial, this n is any int , say 200! ,something like that.
Thanks in Adv
Printable View
Hi All
Can somebody give me a simple c++ program to findout n factorial, this n is any int , say 200! ,something like that.
Thanks in Adv
Everybody here are always willing to help, but first, you need to try. Tell us what you have done and the problem you encountered. Providing sample code would help us narrowing down the problem.:)
For your information: 200! is something about 7.88 *10^374 -- a number that does not fit well in built in integral type variables. So the main point of such a program is the definition of an integral type of arbitrary length, and of course the definition of the arithmetic operations for such a type.
Yup, nice homework, indeed...:cool:
i'm sure there is a faster, more mathematical way to do it but don't you simply loop? For today's computers, 200 iterations of simple math isn't going to slow it down much, if only done a few times ;)
Code:ULONGLONG factorial( short n )
{
ULONGLONG result = 1L;
for( short i = 1;i <= n;i++ )
result *= i;
return result;
}
Is the data type you used similar to LONGLONG type definition ?
How do you know about that type ? Oh, I mean because I have not seen it before or found it out in my textbook...
May I ask for that ?
Thank you...
Regards,
Nina
its a vc/windows datatype (like DWORD, you can tell because it is uppercase) for a unsigned 64bit integer. There is also unsigned __int64 which I believe is also vc specific.
Regards,
I was just thinking... an infinite length integer class would be cool... most 64bit+ classes work by storing in two or more 32bit variables. So, using similar logic it must be possible to build a similar class with a dynamic array of 32bit variables.
There are many arbitrary precision integer arithmetic class libraries available. I have used them alot in numerics, and yeas, they are very cool! ;)
I know people have already talked about integer ranges being too small, but the double data type is also too small to hold the value of 200! (The max double value is 1.7976931348623158e+308). Anyway, if you don't need all 375 digits of precision, then what may be better is to calculate the logarithm (or log10() ) of the factorial. Of coarse this doesn't give you exactly what you want, but it is something you don't need a custom library for.
- Kevin
For arbitrary long integers try to Google for NTL.
if you ask me, recursion is the way to go on this.
i just wrote this on the spot and it works but you might want to add some more error checking (dont let your user give you a negative value or else uh oh!)
int Factorial(int a)
{
if(a == 1) return 1;
else
{
return (a * Factorial(a-1));
}
}
It is well-known that the recursive approach to calculating a factorial is orders of magnitude slower than an iterative approach. Also, do you really think the call stack is going to stand up to potentially hundreds of calls sitting on it?
I feel cold not cool, my sister :);)Quote:
Originally posted by galathaea
There are many arbitrary precision integer arithmetic class libraries available. I have used them alot in numerics, and yeas, they are very cool! ;)
Anyway i think Micheal Williamson's method is pretty good...
you're entirely right. sorry for trying to help or adding some input.
i didn't say DONT USE ANY OTHER METHOD, USE THIS! i simply offered another possibility.
uhmm but that int--return type might be a problem in this case...:)
No denying that it is also the best way to solve such kind of problem though..:)
You said:Quote:
Originally posted by filthy_mcnasty
you're entirely right. sorry for trying to help or adding some input.
i didn't say DONT USE ANY OTHER METHOD, USE THIS! i simply offered another possibility.
That looks to me like a recommendation.Quote:
Originally posted by filthy_mcnasty
if you ask me, recursion is the way to go on this.
I just did a test and found that my solution works upto 65!, so the trick for numbers larger would be your own "sciencetific notation" system :) For example, you could make your result a double and multiply be single digit numbers only.
I just tried a double version of the same function and it works for numbers upto 177!. I didn't realize that double was so much bigger :)
I changed the short to unsigned as previously suggested so that the user can't try an negative factorial.Code:double factorial( unsigned short n )
{
double result = 1.0f;
for( short i = 1;i <= n;i++ )
result *= i;
return result;
}
It doesn't work for 0 factorial (the fix is easy, of course).Quote:
Originally posted by mwilliamson
I changed the short to unsigned as previously suggested so that the user can't try an negative factorial.
Also, google for "Stirling's formula". This gives an approximation of n! for large values of n.
Regards,
Paul McKenzie
yes, a recommendation. that doesn't mean i said "this is the best, dont use anything else". an IDEA.
There is no zero factorial... I know my code will return 1 for 0!, and thats what my calculator returns, so I don't see a problem.Quote:
Originally posted by Paul McKenzie
It doesn't work for 0 factorial (the fix is easy, of course).
Also, google for "Stirling's formula". This gives an approximation of n! for large values of n.
Regards,
Paul McKenzie
OK, I see that 1 is returned if the loop isn't entered.
BTW, there is a 0! and it is by definition, 1.
Regards,
Paul McKenzie
In fact the factorial is defined for all complex numbers except the negative integers
If you want to keep being technical on the definition of a factorial, it really isn't defined for all complex numbers, as it is not defined for real numbers that are not nonnegative integers (for example, 3.5! is not defined). :)
3.5! = (sqrt(PI)/16)(105)
I never heard about a complex factorial.Quote:
Originally posted by souldog
In fact the factorial is defined for all complex numbers except the negative integers
Can you provide a definition? for example (a+bi)! with b!=0?
Yeah, I learned this in my mathematical statistics class. The factorial of an integer is just a generalization of the Gamma function, and Gamma(0.5) == sqrt(pi).Quote:
Originally posted by souldog
3.5! = (sqrt(PI)/16)(105)
Regards,
Paul McKenzie
I thought he was full of s*, too (no offense, man), so I googled and found,
http://mathworld.wolfram.com/Factorial.html
Check out (7).
AAAIAIAIAGH!!! INTEGRALS SCARY!!!! AIGH!!
Peace,
Bassman
Yes. The factorial isn't as trivial as it sounds. It has its roots in the Gamma function, and that is what souldog was pointing out.Quote:
Originally posted by Bassman
I thought he was full of s*, too (no offense, man), so I googled and found,
Regards,
Paul McKenzie
Some Stuff About Factorial
oops you had already found the same link I did
Quote:
Originally posted by Bassman
I thought he was full of s*, too (no offense, man), so I googled and found,
http://mathworld.wolfram.com/Factorial.html
Check out (7).
AAAIAIAIAGH!!! INTEGRALS SCARY!!!! AIGH!!
Peace,
Bassman
Well I am always full of s* :D :D
I had to teach this stuff at one point to a bunch of engineering students who kept asking "why do we have to learn this". Lots of fun
Really the gamma function is a definite integral. But one thing is the factorial of a number and other thing the Gamma function of a number. And yes, for positive integers they are almost the same.
Gamma(x+1)=x!
?
The factorial of any complex number except for negative integers
IS defined. I for one do not argue with definitions. Instead I try to understand why they are useful.
Let me tell you that extensions of the familiar real valued functions with real domian into the complex plane is very useful.
Another example is the complex exponential which is the most important function in the universe.;)
I will not argue about this. I think this has gone off topic.Quote:
Originally posted by souldog
?
The factorial of any complex number except for negative integers
IS defined. I for one do not argue with definitions
(Taking the piss) What's there to argue about?
n! is defined as Gamma(n + 1) for all complex numbers > 0. For positive integers, n! is also defined as n * n-1 * n-2 * ... * 3 * 2.
And BTW, you were the one who asked for a definition from souldog, and now that you've got it, you're unhappy and the thread is 'off-topic'? Sheesh dude.
Peace,
Bassman
(a little grumpy today)
I didn't mean this as an arguement. I was simply trying to point out the correct way to approach mathematics.Quote:
Originally posted by Doctor Luz
I will not argue about this. I think this has gone off topic.
Not, I'm not unhappy.Quote:
Originally posted by Bassman
(Taking the piss) What's there to argue about?
n! is defined as Gamma(n + 1) for all complex numbers > 0. For positive integers, n! is also defined as n * n-1 * n-2 * ... * 3 * 2.
And BTW, you were the one who asked for a definition from souldog, and now that you've got it, you're unhappy and the thread is 'off-topic'? Sheesh dude.
Peace,
Bassman
(a little grumpy today)
OK, I wanted to say that the original question is about n! with integers, then there is no need to discuss in this thread about the "extended" factorial function. Only that!Quote:
Originally posted by souldog
I didn't mean this as an arguement. I was simply trying to point out the correct way to approach mathematics.
Doctor Luz said:
... and later ...Quote:
I never heard about a complex factorial.
Can you provide a definition? for example (a+bi)! with b!=0?
(flip/flop)Quote:
OK, I wanted to say that the original question is about n! with integers, then there is no need to discuss in this thread about the "extended" factorial function. Only that!
...
Bassman
(both grumpy and picky now)
Guys, what about letting this thread die in peace, without flamewar, hummm? Please?
Yeah, sorry, my fault - I shouldn't be such a boob. Like I said, I'm grumpy today. Stupid COM objects...
:)
Peace,
Bassman