How well can a computer count?

My 2-year-old son knows how to count up to 10; after that he starts to “improvise,” so I can say he knows how to count up to 10.

With computers it is similar: if you repeatedly add 1 to a number, eventually the PC will make a mistake. Yes, the computer can make mistakes; in fact, there is an entire field dedicated to bounding errors in PC calculations, called numerical error.

To understand how a computer can make mistakes, first we have to distinguish how it understands numbers. There are 2 ways: integers and floats, decimals or floating-point numbers. Like all data on a PC, both are stored as sequences of bits, 0 or 1, and they differ in how the bits are interpreted.

For the first case, integers, it is quite simple, but it will help us understand float types.

Integer

Integers come in different sizes depending on the number of bits used to store them. For example, a 4-bit integer would write numbers as follows:

0=0000
1=0001
2=0010
3=0011
4=0100
5=0101
6=0110
7=0111

With 4 bits, we can count only up to 7 because the last bit is used to denote the sign of the number, positive or negative. Thus, negative numbers would be written as follows:

-1=1000
-2=1001
-3=1010
-4=1011
-5=1100
-6=1101
-7=1110
-8=1111

In general, we can say that for an integer with n bits, we can represent numbers up to 2^{n-1}-1 for the positive case and 2^{n-1} for the negative case.

PC integers can have different sizes, generally 32, 64, or 128 bits, where the maximum sizes are the following:

32 bit: 2^{31}-1 = 2,147,483,647
64 bit: 2^{63}-1 = 9,223,372,036,854,775,807
128 bit: 2^{127}-1 = 170,141,183,460,469,231,731,687,303,715,884,105,727

Now, what happens when we exceed this number? Well, it depends on the programming language.

Python

Python 3.x is a special case: it handles integers in another way, so it has no limit. This makes it considerably slower, but it can calculate them as long as it wants, at least that is what I got in my results.

>>> n = (2**1000)
>>> print(n)
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
>>> type(n)
<class 'int'>

The above is quite convenient, but it makes it slow. That is why Python has the NumPy library, which works the way the CPU works natively, obtaining faster calculations. The first interesting thing is that when a 32-bit integer exceeds its maximum size, it becomes a 64-bit one.

>>> n = np.int32(2**31-1)
>>> print(n)
2147483647
>>> type(n)
<class 'numpy.int32'>
>>> print(n+1)
2147483648
>>> type(n + 1)
<class 'numpy.int64'>

If we force n+1 to be 32-bit, the counter starts from the most negative number that can be represented:

>>> np.int32(n + 1)
-2147483648

The above happens because in binary 2147483647 = 011111111111111111111111111111111, so when adding 1, the result is 1000000000000000000000000000000, which is -2147483648.

On the other hand, the largest int in NumPy is 64-bit. What will it do if it cannot increase its size? Will it switch to another integer type with greater capacity or start from the negative side?

>>> n = np.int64(2**63-1)
>>> print(n)
9223372036854775807
>>> type(n)
<class 'numpy.int64'>
>>> print(n+1)
-9223372036854775808
>>> type(n + 1)
<class 'numpy.int64'>

Clearly, it starts from the negative side because the largest integer implemented in NumPy is the 64-bit one.

R

In R, integers are 32-bit by default. There are libraries for working with 64-bit integers, but they are not native. We can see that R will warn us that the maximum was exceeded, so we can be calm knowing there will be no strange behavior.

> n = 2147483647L
> n+1L
[1] NA
Warning message:
In n + 1L : NAs produced by integer overflow

Julia

Julia makes the same mistake as Python, without warning that it will make an error.

julia> n = Int32(2147483647)
2147483647

julia> n + Int32(1)
-2147483648

Finally, Julia can handle integers of up to 128 bits, allowing them to count up to: 170,141,183,460,469,231,731,687,303,715,884,105,727; after that, it will return to the negative side.

Floats or floating point

In general, the PC uses floats instead of integers, but the previous explanation helps us understand this case.

Here things get a bit more complex. Imagine you have a very, very long number. It does not make much sense to use all the digits; only the last ones will be significant or relevant. That is why scientific notation exists, where, for example, 123,456,789,012,345,678,901,234,567,890 is written as 1.23456 * 10^{29}, discarding the non-significant numbers. The PC does the same thing to store float-type numbers, but in binary.

In general, the PC uses 64-bit floats called doubles, but for this exercise we will use 32-bit floats, or singles. In a 32-bit float, out of the 32 bits, 24 are used to write the significant digits, while the remaining 8 are used for the exponent in scientific notation.

Theoretically, the largest number that a 32-bit float can store is on the order of 2^{2^{7}-1} = 2^{127} \sim 10^{38}, but the question is not what the largest number is; it is how far the PC can count.

When we count, we add 1 to a number until we no longer know how to calculate the next number. At what point, when adding 1 to a float, will it return an incorrect result?

Let’s answer the question using Julia, which has excellent data type handling. To do this, we will count from 0 using a 64-bit integer and a 32-bit float. When they produce different results in some addition, it means the float made a mistake, so it cannot count any further.

This happens because adding 1 to a very large number ends up being insignificant.

julia> float = Float32(0)
0.0f0

julia> int = Int64(0)
0

julia> while int == float
           float = float + 1
           int = int + 1
       end

julia> Int64(float)
16777216

julia> int
16777217

Exactly at 16,777,216, when adding 1, the 1 is so insignificant that the result of the sum will be the same previous number, so it will stop counting and get stuck at: 16,777,216.

In Python it is the same story, but it takes a loooong time:

>>> i = np.int64(0)
>>> f = np.float32(0)
>>> while i == f:
...   i = i + np.int64(1)
...   f = f + np.float32(1)
... 
>>> print(i)
16777217
>>> print(f)
16777216.0

This number, 16,777,216, corresponds to 2^24, where 24 is precisely the number of bits used to store the significant digits.

It does not look like such a large number, but the PC actually uses double-precision floats, that is, 64-bit floats, which use 12 bits for the exponent and 56 for the significant digits. So, extrapolating this experiment, the largest number would be $$ 2^52$$ = 4,503,599,627,370,495

What will happen in Excel when adding 1 to that number?

Well, we can see that Excel made a mistake, so be careful if you start counting wheat grains to obtain the chess license, because with Excel you will not be able to count the number of grains you will need. If you did not understand the joke, you can watch this video: https://www.youtube.com/watch?v=ziWYaYjJ8zk

Regards, I hope you liked it.