Results 1 to 12 of 12
  1. #1
    JONCOM is offline Member
    Join Date
    Jan 2011
    Posts
    10
    Rep Power
    0

    Question Understanding limitations of int data-type

    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

    Java Code:
    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()

    Java Code:
    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 :)
    Last edited by JONCOM; 01-30-2011 at 10:14 PM.

  2. #2
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default

    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.

  3. #3
    JONCOM is offline Member
    Join Date
    Jan 2011
    Posts
    10
    Rep Power
    0

    Default

    Quote Originally Posted by Junky View Post
    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?
    Last edited by JONCOM; 01-17-2011 at 07:53 AM. Reason: Had a thought...

  4. #4
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,368
    Blog Entries
    7
    Rep Power
    20

    Default

    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
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    JONCOM is offline Member
    Join Date
    Jan 2011
    Posts
    10
    Rep Power
    0

    Default

    Quote Originally Posted by JosAH View Post
    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:
    Java Code:
    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?
    Last edited by JONCOM; 01-18-2011 at 06:53 PM.

  6. #6
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,368
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by JONCOM View Post
    I'm a little thrown by your shorthand. Could you please tell me what the exclamation in your code does here:
    Java Code:
    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
    cenosillicaphobia: the fear for an empty beer glass

  7. #7
    Iron Lion is offline Senior Member
    Join Date
    Nov 2010
    Posts
    210
    Rep Power
    4

    Default

    n! is the mathematical notation of "n faculty"
    That's "factorial".

  8. #8
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,368
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Iron Lion View Post
    That's "factorial".
    Oops, true, all true; I knew that but nevertheless my fingers thought otherwise; thanks for correcting me.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  9. #9
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default

    It seems Jos is losing his faculties ;)

  10. #10
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default

    Quote Originally Posted by JONCOM View Post
    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.

  11. #11
    j2me64's Avatar
    j2me64 is offline Senior Member
    Join Date
    Sep 2009
    Location
    Zurich, Switzerland
    Posts
    962
    Rep Power
    5

    Default

    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

  12. #12
    JONCOM is offline Member
    Join Date
    Jan 2011
    Posts
    10
    Rep Power
    0

Similar Threads

  1. Help with LCDUI limitations!
    By PeteDesigner in forum New To Java
    Replies: 6
    Last Post: 11-18-2010, 02:10 PM
  2. how to set NVarchar data type
    By edi.gotieb in forum JDBC
    Replies: 9
    Last Post: 05-19-2010, 01:13 PM
  3. Primitive data type and class
    By Roselicious in forum New To Java
    Replies: 3
    Last Post: 04-19-2010, 03:27 PM
  4. Limitations unneceeasry
    By ranjiths in forum Suggestions & Feedback
    Replies: 1
    Last Post: 09-28-2009, 04:23 PM
  5. sychronized data type
    By java girl in forum Threads and Synchronization
    Replies: 3
    Last Post: 02-13-2009, 08:37 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •