Results 1 to 12 of 12
 01172011, 12:08 AM #1Member
 Join Date
 Jan 2011
 Posts
 10
 Rep Power
 0
Understanding limitations of int datatype
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 forloop 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 datatype.
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; 01302011 at 11:14 PM.
 01172011, 03:33 AM #2
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.
 01172011, 08:44 AM #3Member
 Join Date
 Jan 2011
 Posts
 10
 Rep Power
 0
Sure, I can see that the last number before the onlyzeros 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; 01172011 at 08:53 AM. Reason: Had a thought...
 01172011, 09:24 AM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,401
 Blog Entries
 7
 Rep Power
 25
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,
JosBuild a wall around Donald Trump; I'll pay for it.
 01182011, 07:51 PM #5Member
 Join Date
 Jan 2011
 Posts
 10
 Rep Power
 0
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 reword that to be a little more clear?Last edited by JONCOM; 01182011 at 07:53 PM.
 01182011, 08:03 PM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,401
 Blog Entries
 7
 Rep Power
 25
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,
JosBuild a wall around Donald Trump; I'll pay for it.
 01182011, 08:29 PM #7Senior Member
 Join Date
 Nov 2010
 Posts
 210
 Rep Power
 7
n! is the mathematical notation of "n faculty"
 01182011, 08:41 PM #8
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,401
 Blog Entries
 7
 Rep Power
 25
 01182011, 10:27 PM #9
It seems Jos is losing his faculties ;)
 01182011, 10:31 PM #10
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.
 01182011, 11:01 PM #11
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
 01302011, 10:57 PM #12Member
 Join Date
 Jan 2011
 Posts
 10
 Rep Power
 0
Similar Threads

Help with LCDUI limitations!
By PeteDesigner in forum New To JavaReplies: 6Last Post: 11182010, 03:10 PM 
how to set NVarchar data type
By edi.gotieb in forum JDBCReplies: 9Last Post: 05192010, 01:13 PM 
Primitive data type and class
By Roselicious in forum New To JavaReplies: 3Last Post: 04192010, 03:27 PM 
Limitations unneceeasry
By ranjiths in forum Suggestions & FeedbackReplies: 1Last Post: 09282009, 04:23 PM 
sychronized data type
By java girl in forum Threads and SynchronizationReplies: 3Last Post: 02132009, 09:37 AM
Bookmarks