Problems with representing numbers on computers, part 1
notnotrebecca recently pointed out to me that online calculators incorrectly calculate 111111111*111111111. It should be 12345678987654321 (any time you multiply a string of ones by itself you get a nice symmetrical answer like that), except that the online calculators she tried consistently gave 12345678987654320 instead. (Note the zero on the end.)
Here's what I found out.
Online calculators are often implemented in the JavaScript programming language. JavaScript stores all numbers as double precision floating point numbers, according to the IEEE-754 specification. The problem is, in double precision floating point numbers, 12345678987654320 and 12345678987654321 can't be distinguished from each other. "Say what?", I hear you ask. Well, it's like this.
The question is, how do you represent the infinite collection of all numbers on a computer? A computer doesn't have infinite memory.
For integers (that is, numbers without a decimal point, e.g. 12742), you can simply say you'll allow numbers within a certain range, and this what computers do.
A quick primer on binary: The numbers we're most familiar with are in base 10. That means that each place represents the number of ones, the number of tens, the number of hundreds, and so on. (Note how it gets multiplied by ten with each place.) 732 means 7 hundreds, 3 tens, and 2 ones, i.e. 700 + 30 + 2 = 732. Binary on the other hand is base 2, so each place represents the number of ones, the number of twos, the number of fours, the number of eights, etc. (Note how it gets multiplied by two with each place.) So 1101 in binary means 1 eight, 1 four, 0 twos, and 1 one, i.e. 8 + 4 + 1 = 13.
Typically, an integer will be stored in a computer in 32 bits or 64 bits of memory. How large a number does that let you store? An analogy back to base 10 will help. If I'm only allowed to store numbers having five or less places in base 10, then I could store 10202 but not 110202 (because that uses six places). Essentially, I can only store numbers less than or equal to 10^6 - 1 (that means 10*10*10*10*10*10 - 1 = 99999). Similarly, if I had five bits in binary, I could store numbers less than or equal to 2^6 - 1 (meaning 2*2*2*2*2*2 - 1 = 63). 63 in binary looks like 11111, taking up all five bits.
But, we want to be able to store negative numbers as well, so what we do is use one of the bits to say whether the number is positive or negative. This one bit is called the "sign bit". By convention, if the sign bit is 0 the number is positive, and if it's 1 the number is negative. So if we had 32 bits to start with, we could use 1 for the sign bit and 31 of them to store the number and thus could have numbers as large as 2^32 - 1 = 4294967295 and as small as -4294967295. With 64 bits, we can store numbers as large as 2^64 - 1 = 18446744073709551615 and as small as -18446744073709551615. For most purposes, this is enough.
(Actually, this isn't exactly how integers are stored. One problem is that we have two representations of the number zero, positive zero and negative zero. Because you could set all the bits except the sign bit to 0, and then have the sign bit set to either 1 or 0, we get two different ways of representing the number zero. For this and other reasons, numbers are usually stored in a form called two's complement -- but that's another topic.)
See part two for the continuation of this, and the explanation of why 12345678987654320 and 12345678987654321 can't be distinguished from each other.
Here's what I found out.
Online calculators are often implemented in the JavaScript programming language. JavaScript stores all numbers as double precision floating point numbers, according to the IEEE-754 specification. The problem is, in double precision floating point numbers, 12345678987654320 and 12345678987654321 can't be distinguished from each other. "Say what?", I hear you ask. Well, it's like this.
The question is, how do you represent the infinite collection of all numbers on a computer? A computer doesn't have infinite memory.
For integers (that is, numbers without a decimal point, e.g. 12742), you can simply say you'll allow numbers within a certain range, and this what computers do.
A quick primer on binary: The numbers we're most familiar with are in base 10. That means that each place represents the number of ones, the number of tens, the number of hundreds, and so on. (Note how it gets multiplied by ten with each place.) 732 means 7 hundreds, 3 tens, and 2 ones, i.e. 700 + 30 + 2 = 732. Binary on the other hand is base 2, so each place represents the number of ones, the number of twos, the number of fours, the number of eights, etc. (Note how it gets multiplied by two with each place.) So 1101 in binary means 1 eight, 1 four, 0 twos, and 1 one, i.e. 8 + 4 + 1 = 13.
Typically, an integer will be stored in a computer in 32 bits or 64 bits of memory. How large a number does that let you store? An analogy back to base 10 will help. If I'm only allowed to store numbers having five or less places in base 10, then I could store 10202 but not 110202 (because that uses six places). Essentially, I can only store numbers less than or equal to 10^6 - 1 (that means 10*10*10*10*10*10 - 1 = 99999). Similarly, if I had five bits in binary, I could store numbers less than or equal to 2^6 - 1 (meaning 2*2*2*2*2*2 - 1 = 63). 63 in binary looks like 11111, taking up all five bits.
But, we want to be able to store negative numbers as well, so what we do is use one of the bits to say whether the number is positive or negative. This one bit is called the "sign bit". By convention, if the sign bit is 0 the number is positive, and if it's 1 the number is negative. So if we had 32 bits to start with, we could use 1 for the sign bit and 31 of them to store the number and thus could have numbers as large as 2^32 - 1 = 4294967295 and as small as -4294967295. With 64 bits, we can store numbers as large as 2^64 - 1 = 18446744073709551615 and as small as -18446744073709551615. For most purposes, this is enough.
(Actually, this isn't exactly how integers are stored. One problem is that we have two representations of the number zero, positive zero and negative zero. Because you could set all the bits except the sign bit to 0, and then have the sign bit set to either 1 or 0, we get two different ways of representing the number zero. For this and other reasons, numbers are usually stored in a form called two's complement -- but that's another topic.)
See part two for the continuation of this, and the explanation of why 12345678987654320 and 12345678987654321 can't be distinguished from each other.