How does python represent such large integers?

Question

In C, C++, and Java, an integer has a certain range. One thing I realized in Python is that I can calculate really large integers such as pow(2, 100). The same equivalent code, in C, pow(2, 100) would clearly cause an overflow since in 32-bit architecture, the unsigned integer type ranges from 0 to 2^32-1. How is it possible for Python to calculate these large numbers?

Answer 1

Basically, big numbers in Python are stored in arrays of 'digits'. That's quoted, right, because each 'digit' could actually be quite a big number on its own. )

You can check the details of implementation in longintrepr.h and longobject.c:

There are two different sets of parameters: one set for 30-bit digits, stored in an unsigned 32-bit integer type, and one set for 15-bit digits with each digit stored in an unsigned short. The value of PYLONG_BITS_IN_DIGIT, defined either at configure time or in pyport.h, is used to decide which digit size to use.

/* Long integer representation.
    The absolute value of a number is equal to
    SUM(for i=0 through abs(ob_size)-1) ob_digit[i] * 2**(SHIFT*i)
    Negative numbers are represented with ob_size < 0; 
      zero is represented by ob_size == 0.

    In a normalized number, ob_digit[abs(ob_size)-1] (the most significant
      digit) is never zero.  Also, in all cases, for all valid i,
        0 <= ob_digit[i] <= MASK.

    The allocation function takes care of allocating extra memory
    so that ob_digit[0] ... ob_digit[abs(ob_size)-1] are actually available.

*/

struct _longobject {
   PyObject_VAR_HEAD
   digit ob_digit[1];
};

Answer 2

How is it possible for Python to calculate these large numbers?

How is it possible for you to calculate these large numbers if you only have the 10 digits 0-9? Well, you use more than one digit!

Bignum arithmetic works the same way, except the individual "digits" are not 0-9 but 0-4294967296 or 0-18446744073709551616.