Understanding limitations of int data-type

[JONCOM]

In a nutshell...

I am trying to find a solution for a question given to me in my programming course in college.

Given a small program, I am asked to explain why for values 34 and higher, is the returned output always 0?

There are some strange logical errors that appear before this occurs, however they can be explained by int being a capable of only 32 bits and therefor cannot store a value greater than (positive/negative) 2147483648.

So, first of all...

Here is the program

public class Bonus01
{
    // uses a for-loop to multiply together the first n integers    
    public static int multFor(int n)
    {
        int retval = 1;
        for(int i=1; i<=n; i++)
            retval *= i;  // equivalent to retval = retval * i
        return retval;
    }
    
    // calls multFor for a range of integers from 1 to maxn
    public static void callMultFor(int maxn)
    {
        for(int i=0; i<= maxn; i++) {
            int currval = multFor(i);
            System.out.println("multFor(" + i + ") = " + currval);
        }
    }
    
    public static void main()
    {
        callMultFor(36);
    }

}

Output of main()

multFor(0) = 1
multFor(1) = 1
multFor(2) = 2
multFor(3) = 6
multFor(4) = 24
multFor(5) = 120
multFor(6) = 720
multFor(7) = 5040
multFor(8) = 40320
multFor(9) = 362880
multFor(10) = 3628800
multFor(11) = 39916800
multFor(12) = 479001600
multFor(13) = 1932053504
multFor(14) = 1278945280
multFor(15) = 2004310016
multFor(16) = 2004189184
multFor(17) = -288522240
multFor(18) = -898433024
multFor(19) = 109641728
multFor(20) = -2102132736
multFor(21) = -1195114496
multFor(22) = -522715136
multFor(23) = 862453760
multFor(24) = -775946240
multFor(25) = 2076180480
multFor(26) = -1853882368
multFor(27) = 1484783616
multFor(28) = -1375731712
multFor(29) = -1241513984
multFor(30) = 1409286144
multFor(31) = 738197504
multFor(32) = -2147483648
multFor(33) = -2147483648
multFor(34) = 0
multFor(35) = 0
multFor(36) = 0

Making sense of this strange output...

A couple points provided in the question:

• Multiplying the value returned from multFor(13) by 14 appears to decrease the result;
• Multiplying the value from multFor(15) by 16 barely changes the result;
• Starting at multFor(17), we start to see negative numbers, despite the fact that we are only multiplying positive numbers together.

The above can be attributed to the limitations of the 32 bit sized int data-type.

What I cannot explain at this point

Why the output is 0 starting at multFor(34) and on... Please help!

I would love for anybody to shed some light on this phenomenon.

Thanks :)

[Junky]

The answer lies in the binary representations of the numbers. If you notice the last number you get (before getting zeros) is Integer.MIN_VALUE which is 1 followed by 31 zeros. Think about that and what will happen when you multiply it by any number.

[JONCOM]

The answer lies in the binary representations of the numbers. If you notice the last number you get (before getting zeros) is Integer.MIN_VALUE which is 1 followed by 31 zeros. Think about that and what will happen when you multiply it by any number.

Sure, I can see that the last number before the only-zeros is indeed Integer.MIN_VALUE, but I am not sure why it is this number (I would have expected it to reach its minimum, or rather maximum, a lot sooner).

And I'm not sure what relationship this has with int's binary representation either.

Obviously I'm still not getting something...


[edit]

If for example, you have a number represented by 32 bits like so: 11111111111111111111111111111111

And you were to increase that number by a value of 1, you would require 33 bits represented as: 100000000000000000000000000000000

In the case of an int, you can't bump up to 33 bits and so that 1 is truncated, and you are left with: 00000000000000000000000000000000

I'm kinda guessing here. Am I close at all?

[JosAH]

Don't think too much of it: your method is computing n! == 1*2*3* ... *n in integer format. Ints can only store 32 bits (as you already know) so you're actually computing n! % M where M == 2**32 (2 raised to the power 32). Try to do the same and use BigIntegers instead.

kind regards,

Jos

[JONCOM]

Don't think too much of it: your method is computing n! == 1*2*3* ... *n in integer format. Ints can only store 32 bits (as you already know) so you're actually computing n! % M where M == 2**32 (2 raised to the power 32). Try to do the same and use BigIntegers instead.

kind regards,

Jos

I'm a little thrown by your shorthand. Could you please tell me what the exclamation in your code does here:

n! == 1*2*3* ... *n

Thanks.

By the way, I was discussing this with a friend, who asked another friend about this. My friend was told, "Basically, this happens because the system runs out of memory for the datatype."

Is that right? And could someone maybe re-word that to be a little more clear?

[JosAH]

I'm a little thrown by your shorthand. Could you please tell me what the exclamation in your code does here:

n! == 1*2*3* ... *n

Thanks.

By the way, I was discussing this with a friend, who asked another friend about this. My friend was told, "Basically, this happens because the system runs out of memory for the datatype."

Is that right? And could someone maybe re-word that to be a little more clear?

n! is the mathematical notation of "n faculty" and it is 1*2*3 ... *n and 0! == 1 by definition. Your program was calculating n! "n faculty" for increasing values of n using ints. Ints can only store 32 bits so they'll overflow (as you have noticed). You were effectively calculating n! modulo 2**32 (2 raised to the power 32). Your friend is wrong, there is no memory overflow but the ints had overflow, i.e. you wanted to store a number in an int that was too large to be stored in an int.

kind regards,

Jos

[Iron Lion]

n! is the mathematical notation of "n faculty"

That's "factorial".

[JosAH]

That's "factorial".

Oops, true, all true; I knew that but nevertheless my fingers thought otherwise; thanks for correcting me.

kind regards,

Jos

[Junky]

It seems Jos is losing his faculties ;)

[Junky]

By the way, I was discussing this with a friend, who asked another friend about this. My friend was told, "Basically, this happens because the system runs out of memory for the datatype."

Depends upon what they mean by "out of memory".

What you wrote earlier is spot on. At a certain point a number gets so large or small that the right hand 32 bits are all zeros and when you try to stuff that number into a 32 bit int all the left hand bits are truncated and all you have left are the 32 zero bits. Then if you try to multiply that by any number obviously the result is zero. Basic math.

[j2me64]

here are the result if the code above use BigInteger

multFor(0) = 1
multFor(1) = 1
multFor(2) = 2
multFor(3) = 6
multFor(4) = 24
multFor(5) = 120
multFor(6) = 720
multFor(7) = 5040
multFor(8) = 40320
multFor(9) = 362880
multFor(10) = 3628800
multFor(11) = 39916800
multFor(12) = 479001600
multFor(13) = 6227020800
multFor(14) = 87178291200
multFor(15) = 1307674368000
multFor(16) = 20922789888000
multFor(17) = 355687428096000
multFor(18) = 6402373705728000
multFor(19) = 121645100408832000
multFor(20) = 2432902008176640000
multFor(21) = 51090942171709440000
multFor(22) = 1124000727777607680000
multFor(23) = 25852016738884976640000
multFor(24) = 620448401733239439360000
multFor(25) = 15511210043330985984000000
multFor(26) = 403291461126605635584000000
multFor(27) = 10888869450418352160768000000
multFor(28) = 304888344611713860501504000000
multFor(29) = 8841761993739701954543616000000
multFor(30) = 265252859812191058636308480000000
multFor(31) = 8222838654177922817725562880000000
multFor(32) = 263130836933693530167218012160000000
multFor(33) = 8683317618811886495518194401280000000
multFor(34) = 295232799039604140847618609643520000000
multFor(35) = 10333147966386144929666651337523200000000
multFor(36) = 371993326789901217467999448150835200000000

[JONCOM]

Thank you for the responses.