Python’s Bignum Integer Type

The majority of programming languages provide several integer types which cover different ranges of values. The idea is that you only need to use the amount of storage appropriate for the range. For example, a 1-byte integer can only store -127 to +128 and if you try to store anything outside of this range you generate an error or the value is truncated to fit into the range. Python doesn’t implement integers in this way. Instead it supports a “bignum” integer type which can work with arbitrarily large numbers, which simply take as much memory as needed to store the value. Although you might expect this method of implementing an unlimited range of integers to be too inefficient, Python makes it work well enough.

If you want faster integers then you can use libraries such as NumPy, which provides fixed-size integers.

The promise of unlimited-precision integers is one that is intoxicating for programmers used to other languages where integer overflow is a constant worry, or should be. In most languages and expression such as:

myVar = 2**200

that is 2²⁰⁰, would result in an error message, but in Python you can follow it by:

print(myVar)

and see:

1606938044258990275541962092341162602522202993782792835301376

As long as you restrict yourself to integer types you can forget the problems of overflow or generally running out of digits. Computations are performed accurately and there is no loss of digits. Of course, you cannot represent fractions unless you use fixed-point representation where you regard everything as multiplied by a large power of 10. This can be done, but it isn’t as easy as it first appears and generally it isn’t worth it.

Bignum arithmetic is so easy to use that you can more or less ignore problems of overflow. For example, in most other language the task of computing the factorial (n! = n*n-1*n-2...*1) produces an overflow at around n = 13.

If you try this using Python you can see values that are much larger:

f = 1
k = 1
while(True):
    k=k+1
    f=f*k
    print(f,k)

which produces:

2 2
6 3
24 4
120 5
720 6
5040 7
40320 8
362880 9
3628800 10
39916800 11
479001600 12
6227020800 13
87178291200 14
1307674368000 15
20922789888000 16
355687428096000 17
6402373705728000 18
121645100408832000 19
2432902008176640000 20
51090942171709440000 21
1124000727777607680000 22
25852016738884976640000 23
620448401733239439360000 24
15511210043330985984000000 25

and so on up to very large values.

Bignum Expressions

Most of the time when you write an arithmetic expression that involves only bignums the result is another bignum. This includes the usual arithmetic operators and functions +.-.*, but not division /. If you divide two integers then the result is a float and hence usually a loss of precision. For example:

myVar = 2**200
print (myVar)
myVar = myVar/2
print (myVar*2)

prints:

1606938044258990275541962092341162602522202993782792835301376
1.6069380442589903e+60

which isn’t bad for the number of digits the float represents. You can, of course, also try to create a value that is too big for a float.

For example, if you change the first line to:

myVar = 2**2000

you will see:

As soon as you convert an integer to a float you have to start thinking about overflow and precision problems. If you want to perform division but don’t want to convert to float then you can use the integer division operator // which performs truncating division. i.e. any fractional part is ignored. You can apply // to any numeric type including float and in this case the result is a float and a//b returns the most general type of a and b. That is, if a is an int and b is a float the result is a float. If a and b are both int then the result is int. For example:

myVar=2**200+1
print (myVar)
myVar=myVar//2
print (myVar*2)

prints

1606938044258990275541962092341162602522202993782792835301377
1606938044258990275541962092341162602522202993782792835301376

and you can see the results differ in the last digit because the original is an odd number and the result has to be even. Notice that // always rounds towards minus infinity. For example, 1//2 (exactly 0.5) is 0 and -1/2 (exactly -0.5) is -1. The reason for this is due to the way negative numbers are represented and in both cases it corresponds to truncating any fractional part in the exact result.

The other less common arithmetic operators also work with bignums:

For example:

myVar=2**200+1
print (divmod(myVar,12345678901234567890))

prints

1606938044258990275541962092341162602522202993782792835301377
(130161982756436057245270848995428623856352, 6540610052683564097)

Bit Manipulation

The ability to do high precision integer calculations as standard in Python opens up many possibilities, but it also presents some interesting problems for programmers more used to fixed-precision integers. As well as representing numbers, integers are often used to represent bit patterns that are used to work directly with hardware or as part of low-level algorithms. For example, the integer 5 has the single byte representation 00000101 and in other languages you would simply select an integer data type that was one byte in size and set it to the value 5 to make use of this bit pattern. But in Python integers aren’t set to occupy a fixed amount of storage and so you can’t just assume that myVar = 5 will give you a single byte suitable for use as a bit pattern. Instead you have to use the to_bytes method which converts the number to an array of bytes that you can then use as a bit pattern, more of this in Chapter 12.