How do languages ​​like Python overcome C?

Question

Performing some random experiments with factorial programs in C, Python, and Scheme. I came across this fact:

In C, using the data type "unsigned long long", the largest factorial I can print is 65. This is "9223372036854775808", which is 19 digits, as indicated.

In Python, I can find the factorial of a number equal to 999, which consists of a large number of digits, much more than 19.

How does CPython do this? Does it use a data type like ' octaword '?

Perhaps I am missing some fundamental facts. Therefore, I would appreciate some ideas and / or reading links. Thanks!

UPDATE: Thanks to everyone for the explanation. Does this mean that CPython uses the GNU Multi-precision library (or some other similar library)?

UPDATE 2: I'm looking for a Python implementation of 'bignum' in the sources. Where exactly is this? Its here at http://svn.python.org/view/python/trunk/Objects/longobject.c?view=markup . Thank you, Bayshampayan.

Answer 1

He called arbitrary precision arithmetic. There's more here: http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic

Answer 2

Looking at the Python source code, it seems that the long type (at least in pre-Python 3 code) is defined in longintrepr.h like this -

 /* 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. CAUTION: Generic code manipulating subtypes of PyVarObject has to aware that longs abuse ob_size sign bit. */ struct _longobject { PyObject_VAR_HEAD digit ob_digit[1]; }; 

The actual useful interface of type long then defined in longobject.h by creating a new PyLongObject type like this -

 typedef struct _longobject PyLongObject; 

And so on.

There are more things in longobject.c , you can look at them in more detail.

Answer 3

Data types, such as int in C, are directly mapped (more or less) to the data types supported by the processor. Thus, the limits of C int are essentially the limits imposed by the hardware of the processor.

But you can implement one native int data type entirely in software. For example, you can use an array of numbers as your main representation. Maybe so:

 class MyInt { private int [] digits; public MyInt(int noOfDigits) { digits = new int[noOfDigits]; } } 

After that, you can use this class and store integers containing as many digits as you want if you have not run out of memory.

Perhaps Python is doing something similar in its virtual machine. You can read this article about arbitrary precision arithmetic to get the details.

Answer 4

Not an octavord. It implements a bignum structure for storing arbitrary precision numbers.

Answer 5

Python assigns long integers (all int in Python 3) as much space as they need - an array of “numbers” (base 2) is allocated as needed.