Click here to Skip to main content
15,936,802 members
Please Sign up or sign in to vote.
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
Updated 10-Oct-13 8:23am
v3

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:
 
Share this answer
 
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).
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/[^]
 
Share this answer
 
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

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



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900