-1
\$\begingroup\$

I just wrote this simple code, but I have a problem. I get the factorial for small numbers, but if I enter number like 45 or above, I get 0 as the factorial. Why is that? Check and let me know what you think:

import java.util.*;

public class Testing1 {
public static void main (String args[]){
    Scanner sc=new Scanner(System.in);
    long fact=1,sum=0,numIn;
    System.out.print("Enter the number : ");
    numIn=sc.nextLong();
    for(int i=1;i<=numIn;fact*=i++);
    for(int i=1;i<=numIn;sum+=i++);
        System.out.println("factorial of "+numIn+" = "+fact);
        System.out.println("Summation of numbers till "+numIn+" = "+sum);

    }
}
\$\endgroup\$

closed as off-topic by Simon Forsberg, amon, rolfl, Jamal Dec 6 '13 at 18:27

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question must contain working code for us to review it here. For questions regarding specific problems encountered while coding, try Stack Overflow. After getting your code to work, you may edit this question seeking a review of your working code." – Simon Forsberg, amon, rolfl, Jamal
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ You don't need a loop to calculate the sum of the first n numbers. \$\endgroup\$ – ChrisWue Dec 6 '13 at 18:18
  • \$\begingroup\$ This Code works.I just wanted someone to clarify why it doesnt give the proper answer for big integers.So i dont see a point for you to hold it here. \$\endgroup\$ – Razor1692 Dec 6 '13 at 18:30
  • \$\begingroup\$ I know that it work within given bounds. I was just pointing out that you don't need a loop to calculate the sum of the first n numbers. You can calculate that in O(1) while the loop is O(n) \$\endgroup\$ – ChrisWue Dec 7 '13 at 0:10
4
\$\begingroup\$

45! is a very large number. Your fact is a long, but long is not large enough to hold the value...

44!            = 2673996885588443136
Long.MAX_VALUE = 9223372036854775807

Multiplying 44! by 45 will overflow the long.... which is exactly what you see:

45!            = -8797348664486920192

So, you do not get '0' as you suggest, but -8797348664486920192

NOTE: You should be aware that 20! is actually the last valid number before overflow happens on a long. It is just co-incidence that 44! is positive .... and 45! is not.


EDIT

You ask why 100! == 0?

It is a 'co-incidence' --- (NOTE: A really, really mysterious one, needs more investigation):

factorial of 64 = -9223372036854775808
Summation of numbers till 64 = 2080
factorial of 65 = -9223372036854775808
                  (9223372036854775807)
Summation of numbers till 65 = 2145
factorial of 66 = 0
Summation of numbers till 66 = 2211

64! is exactly Long.MIN_VALUE.... (coincidence?????) 65! is also Long.MIN_VALUE 66! is 0.

After that, anything times 0 is 0,.

EDIT2:

OK, the reason for this, is that any time you multiple a value by 2, it is the same as a bitwise left-shift.... for example, 0b00000001 (1) multiplied by 2 is 0b00000010.

With this factorial, any time you multiple by an even number it is a bit-shift (because all even numbers are a multiple of 2). Also, because any time you multiply one value by an even number the result will always be even. (3*2 is 6, etc!). So, after you have 2! (1 * 2) the factorial result will always be even... (only 1! is odd) and thus every successive loop in the factorial is a bit-shift to the left.

After 64! only the highest-bit is set in your long value..... and then, multiplying by 65 (because it is an odd number) is the same result.... finally, multiplying by 66 (an even number), is another shift, which shifts all the bits out of the long value and you are left with just zero 0.

You can see this using the following adaption of your code:

public static void main (String args[]){
    for (int numIn = 0;  numIn < 101; numIn++) {
        long fact=1;
        for(int i=1;i<=numIn;fact*=i++);
        System.out.println("factorial of "+numIn+" = "+ Long.toHexString(fact));
    }
}
factorial of 53 = b6da000000000000
factorial of 54 = 91fc000000000000
factorial of 55 = 5d24000000000000
factorial of 56 = 5fe0000000000000
factorial of 57 = 58e0000000000000
factorial of 58 = 22c0000000000000
factorial of 59 = 240000000000000
factorial of 60 = 8700000000000000
factorial of 61 = 2b00000000000000
factorial of 62 = 6a00000000000000
factorial of 63 = 1600000000000000
factorial of 64 = 8000000000000000
factorial of 65 = 8000000000000000
factorial of 66 = 0
factorial of 67 = 0
factorial of 68 = 0
\$\endgroup\$
  • \$\begingroup\$ Okay.I understand it.But can you tell me why do i get 0 as the factorial if i put a number like 100? \$\endgroup\$ – Razor1692 Dec 6 '13 at 16:33
  • \$\begingroup\$ @Razor1692 - updated my answer. \$\endgroup\$ – rolfl Dec 6 '13 at 16:41
  • \$\begingroup\$ @Razor1692 - updated again, with the reaso. Thanks for the diversion. \$\endgroup\$ – rolfl Dec 6 '13 at 16:58
  • \$\begingroup\$ I will go through this and try to understand it properly.if i come across any confusion i will ask you again.Thank you \$\endgroup\$ – Razor1692 Dec 6 '13 at 17:07
  • \$\begingroup\$ @Razor1692 To solve your problem, you should use either double or BigInteger. \$\endgroup\$ – Simon Forsberg Dec 6 '13 at 17:27

Not the answer you're looking for? Browse other questions tagged or ask your own question.