|
Post by Yarn Goddess on May 8, 2012 15:53:34 GMT -5
I asked Mr. Goddess to write up something that would definitively explain the entire 32-bit integer problem. He has his degrees in mathematics and has been a senior engineering programmer for about 30 years, so he's well-qualified to explain such things. He's also good at teaching. I hope that this helps you all understand the problem and what happens when the whole thing kicks in and numbers turn to negative.
|
|
|
Post by Yarn Goddess on May 8, 2012 15:53:54 GMT -5
So, I understand there's a little confusion regarding how numbers work within the guts of a computer program. Let's see if we can't clear it up a little bit. First, let's talk about unsigned integers -- these are just whole numbers starting from zero (0, 1, 2, ... ). Forget for now about 32/64 bits, and all of that. Imagine you have a car with an old style odometer. When the car is first manufactured it reads "00000". After the first mile it reads "00001". Eventually, if your car was good enough, it would make it up to "99999". Drive one more mile, and all of the numbers would roll-over to "00000". What!!?! The car thinks that it's brand new again? How can this be? This makes no sense at all!! Of course, both you (and the car) know that it's not brand new, and that you've just reached a limitation on the odometer's capabilities. Your odometer is a five (decimal) digit integer. You reached the largest number that it can store in five digits when you drove 99,999 miles, and when you drove that extra mile, it handled the overflow by going back to zero. In the car's case this is how the mechanism is designed. Your computer isn't much different. When an unsigned integer is filled with its largest number, adding one more causes all of the digits to get reset to zero. Without getting into the ugly details, this is just how the arithmetic on unsigned integers works. Signed integers aren't a whole lot different. They just act a little different when we reach our largest/smallest numbers. As interesting as unsigned integers are, we need signed integers in order to count negative numbers (overdrawn checking accounts, for instance). In order to represent signed numbers, we reserve the highest digit in the number to represent the sign. If it's zero, it's a positive number. If it's one, it's a negative number. And since this is a computer, and computers use binary instead of our human-centric decimal system, we only have 0's and 1's to choose from. Let's skip back to the odometer example for a quick second: What if we were to say that the highest digit on the odometer would be used for a sign bit. If it's zero, it's a positive number, if it isn't zero, then that means it's a negative number. So we're driving along, and the odometer reads "09999" ... and then we drive a few more miles ... now it reads "10002". According to our system, we've now driven a negative number of miles. Since that makes absolutely no sense, what does it mean? What it means is that we exceeded the maximum allowable positive integer for our signed odometer. That's all. It's no different with the numbers in MyTown2. The program is using a 32 (binary) digit value to store some information. For some reason, they decided to interpret these 32 digits as a signed integer, so we've reserved the largest digit to represent our sign. Once we exceed our maximum positive integer, the number "turns negative" just like it did when the odometer changed from "099,999" to "100,002". When you reach just over 2 billion, you've used up 31 of the binary digits (the 32nd digit is used for the sign). Adding one more effectively sets the sign bit and you now interpret those bits as a negative number. So, why? Why all of these confusing rules on how integers work in a computer? It's because it makes a lot of things that programmers do very, very easy. It means we can simplify circuits on the chips so that we can make them extremely small. Programmers and hardware designers are constantly looking to make things as simple as possible because it gives us the speed/size to do things which used to be impossible before. The problem isn't with the computer, binary arithmetic, or being limited to 32 bits. The problem is with the programmer of the program. They didn't anticipate that anyone would ever get enough coins, cash, pop, etc., to ever get near a billion let alone a few billion. They didn't handle the case in software where adding one more coin to a too huge pile of coins would cause the whole thing to tumble down (and be interpreted wrongly as a negative number). Finally, some fun numbers. Numbers are fun, aren't they? Maximum positive number for a 32 bit signed integer: 2,147,483,647 Looks weird, but in binary it looks like: 01111111 11111111 11111111 11111111 See? The sign bit is clear and the rest of the numbers are at their maximum value. Maximum positive number for a 32 bit UNsigned integer: 4,294,967,295 Here it is in binary: 11111111 11111111 11111111 11111111 (Side note for the nerds: yes, I purposely avoided discussing two's complement arithmetic. I think we can get the gist of what's happening without worrying about that stuff) Hope this helps some, Mark
|
|
|
Post by Moose Town on May 8, 2012 15:59:42 GMT -5
Not that I understood anything written there ^^, but can I exalt Mark? Hmmmn... no? Okay, I'll exalt YG then. But Mark, that was for you. I just reread that whole thing twice.... so I will pretend I understood it. I'm sure Mr. Goddess explained it really well --- just too much for my little brain to handle (especially after lunch!). :-) Thanks, Mr. Goddess.
|
|
|
Post by Snibull on May 8, 2012 16:10:57 GMT -5
Ok, I **edit: think I understood everything I just read (I only had to take one programming class in college but that was a while ago). Thank you very much Mr. Goddess for taking the time to write it up and I'll give YG a well deserved exalt for having you do this. Not to complicate things, but just after I read it, I went to MT2. I'm looking for a business in New Orleans and went to explore. First town that popped up had negative numbers that counted backwards until they stopped at their "correct" values. I took a screen shot. This has happened several times before (different towns, places, etc) but just thought it to be ironic it happened just now! Any explanation-it's not bothering me as I know it's just a glitch.
|
|
|
Post by Yarn Goddess on May 8, 2012 16:31:24 GMT -5
Without actually seeing it myself, I can only guess. But it appears to be doing pretty much what I explained above. The part that I "nerded" out above is what explains that particular behavior. The way that two's complement arithmetic works (without going into the gory details) is this: When you exceed the maximum positive value, you roll over to the largest negative value, and so on back up to zero. For example, let's say our maximum was something like 3 (rather than 2 billion). Starting at zero and adding one at a time, we'd go in the cycle: 0, 1, 2, 3, -3, -2, -1, 0, 1, 2, 3, etc., and so on. Since those numbers are so small (well under 16,000) I'd hazard a guess and say that they were only using 16 bit values for those. Who knows. You can only really find out by disassembling the program, but I have no time or desire to do such a thing. Short version: yeah, it's a glitch. (Obviously, that was Mark. I should make him get his own account so he doesn't keep having to use mine. But I (and he) thank you very much for the exalts.
|
|
|
Post by cmeister23 on May 8, 2012 16:38:10 GMT -5
Wow thanks Mark! The analogy makes sense. Thanks for the explanation!!
|
|
|
Post by Snibull on May 8, 2012 16:41:47 GMT -5
The 32-bit vs 16-bit does explain it because in your initial explanation my mind was only thinking of those (ridiculously) high pop businesses and not this little town I came across!
And YG: you deserve the exalts!
|
|
|
Post by 3cats1dog on May 8, 2012 19:36:43 GMT -5
Thanks Mr. Yarn Goddess for taking the time to explain this to us. I exalted your wonderful wife.
Hudson25
|
|
|
Post by kechibam on May 8, 2012 19:40:20 GMT -5
wow thanks for the explanation, mark! the odometer example made a lot sense. i was wondering why every single one of his businesses had "2147483647". thanks for explaining...felt like i was at a college math lecture there ;D
+1
|
|
|
Post by Marville on May 8, 2012 20:55:44 GMT -5
WOW not only is this forum fun! BUT we actually learn things - that was most informative and I thank you for the explanation and making it understandable for the non math nerds like me
|
|
|
Post by followthesun on May 8, 2012 23:28:00 GMT -5
Now, I want an explanation on the popularity "monster" and all the variables that affect the calculations. Thanks Mark, appreciate the simple, odometer example to explain the sign bit. Explain the floating point numbers next please...
|
|
|
Post by cletsky27 on May 8, 2012 23:47:44 GMT -5
thank you for sharing the knowledge mr. goddess. now i fully understand the 32 bit integers and why some businesses are in the negative. +1 YG.
|
|
|
Post by Mark on May 9, 2012 1:36:53 GMT -5
Now, I want an explanation on the popularity "monster" and all the variables that affect the calculations. :) Thanks Mark, appreciate the simple, odometer example to explain the sign bit. Explain the floating point numbers next please... I have no idea how the popularity monster works (or even what it is). However, I'd like to encourage you to figure it out on your own. The key to figuring out is knowing that all programs work using a fixed recipe (even "random" elements apply that randomness in predictable ways). The next key is to come up with a hypothesis on how it works, and let one variable change leaving all of the others constant. If you predicted the behavior correctly, then keep that and let something else vary keeping all else constant. For example, I hear Pam screaming about some popularity thing plummeting. It seems to be related to the amount of time between two actions taken in the game (click & accept or somesuch) and to the difference between the yesterday-popularity and current popularity. Using the exact same timing (even if it's not to your benefit in the game) measure the yest/current difference and see how that affects the plummet. Science! (guess, measure, evaluate, test, rinse, repeat, accept) As for floating point... well, that's a whole ball of wax... Programs use floating point to approximate real numbers (e.g. fractions and other numbers between the integers). When we write a number like 1,000,000,000 or 0.000000001, we use the zeros for place holders because it makes it convenient for doing arithmetic and to give us a hint as to the size of the number. If computers did the same thing, they'd need a large amount of space to cover all of the real numbers of interest. For example, a 32-bit floating point represents numbers as large as 1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000. It'd take well over 200 bits just to store one number... most of which we really don't care about. For example, if I told you that there are one gazillion atoms in your room, it doesn't add much information to say that there are one gazillion and three atoms in your room. So, instead the computer just keeps the most important numbers (those on the left side of the number) along with a multiplier. So for the three example numbers above, we'd just store: 1 times 10^9, 1 time 10^-9, and 1 times 10^63 (where 10^9 means multiplying 10 against itself nine times and 10^-9 means multiplying 10 against itself nine times then dividing that into 1 ... so one-tenth is 10^-1). The good thing about floating point numbers is that they do very well at representing a large range of values. They also handle growing too large and too small well. If we just kept adding 1 to a floating point number, once we exceed what it can represent, it just says "Infinity". The bad thing about floating point numbers is how limited they are in what they can represent. For example, using floating point numbers, you can't store one-tenth (remember, computers use base two, so there's no way to represent 1/10 using powers of two just like we can't write out 1/3 in decimal form exactly). They also can't represent every real number. Instead, they can get pretty close, but the larger the values are, the more "space" there is between the numbers. Generally this is OK, but it leads to all sorts of problems when doing scientific or financial computing. It's for these reasons why banks store your balance as integers (the integer representing the number of pennies or tenths of a penny in your account): exact representation. The reason that they're called floating point is because no matter what the number is, we write it with the dot just after the first number. (In fact, because we always do that, we don't even have to store that first number ... it's always 1 in base-2). So ten is 1.0 x 10^1 and one hundred is 1.0 x 10^2 and one thousand is 1.0 x 10^3. In fixed point systems, the dot stays put and we put in placeholder zeros (10.0, 100.0, 1000.0). That's probably enough for now :)
|
|
|
Post by followthesun on May 9, 2012 2:18:21 GMT -5
Mark, thanks for the explanation! As mentioned prior, looks like this is a forum where we actually learnt math, science and programming logic. You are a great teacher. Many thanks!
|
|
|
Post by ///M3 on May 9, 2012 12:12:22 GMT -5
Props to Mark for trying his best to help people understand Programming, which is no easy feat.
Reminds me of every Programmer's favorite joke:
There are 10 types of people in this world; those who understand binary and those who don't! ;D
|
|