c program to calculate factorial.

Question

3.00/5 (4 votes)

See more:

hello guys
I am running this program which calculate the factorial of a number
-----------------------------------------

C++

#include <stdlib.h>
#include <conio.h>

long fact(int);

int main()
{
  int n;
  long f;
     while(true){
  printf("Enter a number\n");
  scanf("%d", &n);

  if (n < 0)
    printf("Please enter a positive number.\n");
  else
  {
    f = fact(n);
    printf("%d! = %ld\n", n, f);
  }              
  }//end while
    getch();
  return 0;
}

long fact(int n)
{
  if (n == 0)
    return 1;
  else
    return(n * fact(n-1));
}

------------------------------------------
and when I run it I input the number 31
and I get the number: 738197504 which is not correct and when I input bigger number I get a negative result

I know that the "long" data type size is 4 bytes which can store bigger than that number

and when I enter the number 65267 the program crashs

I ran this program on different IDEs(Borlnd, Code::Blocks) and I got different results(on codeblocks it crashes when I input 65244)

I need to know why the long data type doesn't work correctly, it doesn't store the right number and what's the reason for the different results on different IDEs

hope that my English helped me to express my viewpoint correctly.
thank you very much

Posted 10-Oct-13 8:16am

Khaldoon Al-Talib

Updated 10-Oct-13 8:23am

ridoy

v3

Add a Solution

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Accepted Answer · 2013-10-10T08:39:00

Solution 1

Factorial values grow fast. Very, very fast:

n	n!
0	1
1	1
2	2
3	6
4	24
5	120
6	720
7	5040
8	40320
9	362880
10	3628800
11	39916800
12	479001600
13	6227020800
14	87178291200
15	1307674368000
16	20922789888000
17	355687428096000
18	6402373705728000
19	121645100408832000
20	2432902008176640000
25	1.5511210043E25
42	1.4050061178E51
50	3.0414093202E64
70	1.1978571670E100
100	9.3326215444E157
450	1.7333687331E1,000
1000	4.0238726008E2,567
3249	6.4123376883E10,000

(Source: Wiki[^]
And if you look at long - 4 bytes as you say - that's not a 64 bit number. 4 bytes is 4 * 8 == 32 bits, so the largest number it can store is 2,147,483,647...so your method "runs out of steam" at 12! and wraps back to a "random" number.

[edit]Wiki Table truncated and cleaned - OriginalGriff[/edit]

"thank you but why when I input bigger numbers than 12 I get wrong results??"

This all has to do with how computers store numbers. Lets just work with a smaller number of bits (or I have to lean on the "0" key for far too long( and assume that an int contaiuns just four bits.

Obviously, the largest number it can store is when each bit is '1' right? 1111b (or 0xF or 15 in decimal).

Wrong. If we did that, we would have nowhere to store negative numbers, because the "positiveness" or "negativeness" of a number needs a bit to store it.
Conventionally, computers use the highest, or left most bit to indicate negative numbers: any value with the "top bit" set is negative, and with it clear (or '0') the value is positive.
So the largest value we can store is 0111b (or 7 in hex and decimal) - the values range

0111b   7
0110b   6
0101b   5
0100b   4
0011b   3
0010b   2
0001b   1
0000b   0
1111b  -1
1110b  -2
1101b  -3
1100b  -4
1011b  -5
1010b  -6
1001b  -7
1000b  -8 or "negative zero" depending on the system.

So, when you add 2+3, your get 5:

 0010b   2
+0011b   3
=0101b   5

But what happens when you add 5 + 6?

 0101b   5
+0110b   6
=1011b  -5

Arrggh! Noooooooo! But that is what happens - the "extra" bit from the addition of 0101b and 0110b moves into the "top bit" so the number becomes negative. If you continue to add to this then you will "overflow" the "top bit" as well, and at that point the result start to become very unpredictable and will vary depending on the system you run on, the compiler you use, the compilation switches you set and a host of other (mostly rather dull) effects.

And don't forget, multiplication is (at it's most basic) just a lot of adding up! :laugh:

When you scale this up to 32 bits, you get the same problems the moment you try to exceed 2,147,483,647 in an integer: because it's value is
0111111111111111111111111111111111111111111111111111111111111111 in binary. Add one, and it goes negative and your problems begin...:laugh:

Posted 10-Oct-13 8:39am

OriginalGriff

Updated 10-Oct-13 9:26am

v3

Comments

Khaldoon Al-Talib 10-Oct-13 14:46pm

thank you for the info
but why when I input bigger number than 12 I get a result till the number 31 and after that I get a negative result
what about the crash??
different IDEs???
thank you very much

Ron Beyer 10-Oct-13 14:49pm

Because its called overflow, and in C and C++ where there isn't overflow checking, it sets the highest bit of the number, which is the sign bit. If you use an unsigned number (ulong) you'll get higher results and no negatives (factorials can't be negative anyway).

Andreas Gieriet 10-Oct-13 16:54pm

In the strict sense, the statement about the "sign bit" is not correct. If calculating in Two's Complement (what every sane digital gatged does today ;-)), the top bit tells if it is negative or positive, but you cannot simply clear the top bit to turn a negative number into a positive one.
Cheers
Andi

OriginalGriff 10-Oct-13 15:00pm

Because when it wraps, it wraps to a "random" number - which may or may not have the top bit of the value set. If it set, you get a negative number, if it isn't, you get a positive one. Depending on the compiler, compilation options, operating system, and so forth when the wrap happens it may or may not be detected - if it is, then the application crashes deliberately to notify you of the fact. In addition, on some systems, you are likely to run out of stack space to continue recursing well before you get to 64K as each time your method recurses, it will store 4 (or 8) bytes for the return address, plus the parameter value on the stack - and the stack is a very finite memory source (some systems only allow you 32KB by default!)

If you want to generate seriously large factorials, even using an actual 64 bit integer will not get you beyond 20! before that runs out of room as well. Even a double runs out somewhere just over 100!, though it will be significantly inaccurate well before that.

If you want to generate actual large factorials, then you will probably need to get rid of the recursion, and "brew your own" very large number handling code which can to addition and multiplication!

Khaldoon Al-Talib 10-Oct-13 14:57pm

thank you
but why when I input bigger numbers than 12 I get wrong results??
what about the crash I mean when I input a very big number I get the program crashed
why ?
and why on different IDEs the number differs (they are close anyway).

Ron Beyer 10-Oct-13 15:02pm

If you enter a very big number you are probably getting a stack overflow error. This happens because every time you recurse (call the same method within the method) the stack increases. The size of the stack isn't limitless and you are hitting the limit of the size of the stack.

As for the different results in different IDE's, it may be because they handle some of the integers different or are compiling against different libraries. For small numbers (5 for example) the number should be the same. You can only accurately compare "same-ness" for valid values, after they become invalid then the behavior is what us computer programmers like to call "undefined behavior".

OriginalGriff 10-Oct-13 15:26pm

Answer updated

Khaldoon Al-Talib 10-Oct-13 15:26pm

thank you very much guys
one last question :)
why when I input some value 65278 I get a crash is that logical value to get the crash or it must be much smaller than that
when I first thought about it I thought it will be about 100 to get the crsh..... my RAM is 2 GB.

Arpit Jain 10-Oct-13 15:33pm

I don't think so that it's a good idea to use recursion for such depth of function call. Stack overflow may occur. So the reason of crash may be the excessive function recursion.

OriginalGriff 10-Oct-13 15:41pm

It doesn't matter how much RAM you have - stacks are a "fixed size" for a reason.
If you think of a stack of coins, you add new ones at the top, but you can also only take them away from the top as well - if you try and take the bottom coin, the whole lot will fall down!

A Stack in computer terms is the same - you add and remove only from the top. And every time you call a function the "return address" is put on the top of the stack and the stack pointer (the next free location) is moved up one - this is called "pushing" onto a stack. When you exit the function, the stack pointer is moved down, and the return address is removed and execution continues from the point (this is called "popping" a stack)

It's pretty obvious that this has to be one contiguous piece of memory, and that it would be difficult and expensive in time to move it around - you would have to stop the program running, allocate a bigger space, copy all the items, then move the stack pointer and resume the program. So it doesn't happen. A stack is allocated a certain number of bytes (how many varies by system, compiler, compiler options - you get the idea) because each application (in fact each process, each thread) needs it's own stack - you can't mix the "Microsoft Word that edits your shopping list" stack with the "Chrome browser showing this page" stack because both of them would get confused and crash horribly!

So as a result you have to allocate a stack size at some point and it can't change.What happens if you get to the end of your stack and there is no space left? Horrible things...horrible, horrible things...
Think back the the pile of coins. At some point you will add one too many coins - and the whole lot falls over and you no longer have any idea of the order they were in.
When you run over a stack, the system may detect it, and crash your program for you, or it may run over a different application data and crash that, or a different application might run over your applications return addresses - ouch!

And recursion is a very, very good way to run out of stack space! :laugh:

This, by the way is a simplification: the stack is used for a lot more than just return addresses - but that makes the situation worse, not better, because you will exhaust your stack space even faster.

Khaldoon Al-Talib 10-Oct-13 16:01pm

awesome demo thank you
but that brings up another question, that's the last one I swear :)
if we assume that the stack size is 64K, how many recursive call can we make 100 recursive, 200.....65000 calls
how could I calculate that number of recursive calls the stack can bears before it overflows.

OriginalGriff 10-Oct-13 16:17pm

Ouch!
That's a lot, lot harder to answer than you think: "It varies" is about the best, for a pile of reasons.
The first is the simplest:
How big is a "return address"?
It depends on the system (and the compiler, and... You get the idea - just assume this lot when I say that in future!)
For a 32 bit system, it's 32 bits, or 4 bytes. In theory.
For a 64 bit system, it's 64 bits, or 8 bytes. Probably.
But... It doesn't have to be. It could be shorter, or longer... Why longer? Because some processors will only advance stacks in multiples of the actual system data fetch size - which could be 16 bytes.... This is called stack granularity. Hence the "in theory" bit :laugh:

So basically, you could assume 4 bytes per call, but then there is the parameter as well - that takes stack space too. And any local variables will also take space on the stack, and stack granularity affects that as well.

Confused yet? : laugh:

Khaldoon Al-Talib 10-Oct-13 16:24pm

thank you very much you helped me a lot, I appreciate that.

OriginalGriff 10-Oct-13 16:30pm

You're welcome!

Khaldoon Al-Talib 10-Oct-13 16:24pm

thank you very much guys

**Zoltán Zörgő** · Accepted Answer · 2013-10-10T08:52:00

Solution 2

If you want to get out a little bit more from it, try this:

C#

#include <stdlib.h>

unsigned long long fact(int);

int main()
{
  int n=31;
  unsigned long long f;
  f = fact(n);
  printf("%d! = %llu\n", n, f);
  return 0;
}

unsigned long long fact(int n)
{
  if (n == 1)
    return 1;
  else
    return(n * fact(n-1));
}

As you will see, this is is still not enough. 31!=2.6525285981219105863630848e+32, that means 33 decimal digits. If you want this in bits, calculate log2(31!). You will get 112.6 which means you need a 113 bit long (15 bytes) variable to hold such a value. Well, C has no such scalar type. As I know there is no language that has such a big numerical type as scalar type - that doesn't mean you can't deal with such objects (there is BigInteger in c# for example, but that is not a scalar type, it is a class). In C you could probably use this library: http://sourceforge.net/projects/bignlibacbignum/[^]

Posted 10-Oct-13 8:52am

Zoltán Zörgő

Comments

Khaldoon Al-Talib 10-Oct-13 15:03pm

thank you for the answer
but the goal of such a program is just to know which number will give me garbage and which number will crash the program
I need to know why after the number 12 I get a wrong result??
and why it crashes when I input a very big number
thank you

Zoltán Zörgő 10-Oct-13 15:23pm

It is not garbage. It is machine state, more precisely a portion of the result. But it is not determined in any form, it will depend on several things. You got your explanation already, read carefully the answers you got.

Why it crashes with 65267? Because 65267*65266 = 4259716022 which is larger than the value you can store in a signed long. Sou you fail at the first multiplication, and it can't go into recursion. That is why your program crashes.

Well, to know what is the largest number you can calculate, use following logic. You need the bits you have to hold the value: unsigned long long can hold a maximum of 2^64, signed long in your case will hold a maximum of 2^31. Factorial is the fastest function of all (in terms of O), it is even faster than x^x (after a specific x), but still this is a good limit. Calculate log2(x^x) = ln(x*ln(x))/ln(2). This is about how much bits you need to store x!. For more precise method, start here: http://www.johndcook.com/blog/2010/08/16/how-to-compute-log-factorial/ .

Khaldoon Al-Talib 10-Oct-13 15:44pm

ok you're right but the crash happens because of the many opened functions without close (which is more than 65000 opened function) until we finish all the recursion process, and this big number of opened functions will kill the memory before it finishes.
so for long data type:
12 is the last value to get a correct answer for it
and 65000 is big number to kill the memory (consume it up) because the big number of recursive functions.

Zoltán Zörgő 10-Oct-13 15:56pm

Wrong: your code is not starting from 1, it is starting from N down to 1. So if your input is 65267, there is only one recursion at all; it can't enter into the second one, because the interim result won't fit into unsigned long. By the way, you wouldn't consume up all the memory even with 65000 recursions. Well, you would probably in a DOS16 environment, but not under Linux or Windows.

Khaldoon Al-Talib 10-Oct-13 16:11pm

awesome hint, you are right it will not store even the interim value
but let's assume it stores the interim value why the program crash when I enter a big value such like 65000 and it gives me a message of "access violation 0x401160 write of address 0x30ffc"
does it refer to that fact that the memory or the stack has been consumed up????? that's exactly what I want to know

Zoltán Zörgő 10-Oct-13 16:18pm

No. This is compiler/implementation dependent, but you see this message because of an unhandled overflow in a non-general situation. In a recursion the heap and the stack are both used. The compiled code is trying to write to an address that is not allocated to it. Most likely it is messing up the IP or BP in the stack. You could probably set up compiler switches to enable overflow checking. If you want to see the exact cause use an assambly debugger, and look into it deeper. The Tubo Debugger bundled with Borland Turbo Pascal was an awesome tool to that days. But you will probably find more recent ones for your environment.

Khaldoon Al-Talib 10-Oct-13 16:27pm

thank you very much, I appreciate your help :)

Zoltán Zörgő 10-Oct-13 16:28pm

You are welcome.