Как языки, такие как Python, преодолевают ограничения на интегральные данные C?

Question

Выполняя случайные эксперименты с факториальной программой на C, Python и Scheme. Я сталкивался с этим фактом:

В C, используя тип данных «unsigned long long», самый большой факториал, который я могу напечатать, равен 65. Это «9223372036854775808», что составляет 19 цифр, как указано здесь .

В Python я могу найти факториал числа, равного 999, который состоит из большого числа цифр, гораздо больше, чем 19.

Как CPython достигает этого? Использует ли он тип данных как ' octaword '?

Я мог бы упустить некоторые фундаментальные факты здесь. Итак, я был бы признателен за некоторые идеи и / или ссылки для чтения. Спасибо!

ОБНОВЛЕНИЕ: Спасибо всем за объяснение. Означает ли это, что CPython использует библиотеку GNU Multi-Precision (или другую подобную библиотеку)?

ОБНОВЛЕНИЕ 2: Я ищу реализацию Python 'bignum' в исходниках. Где именно это? Это здесь в http://svn.python.org/view/python/trunk/Objects/longobject.c?view=markup. Спасибо Baishampayan.

Answer 1

Это называется Произвольная арифметика точности . Здесь больше: http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic

Answer 2

Глядя на исходный код Python, кажется, что тип long (по крайней мере, в коде, предшествующем Python 3) определен в longintrepr.h следующим образом -

/* 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's sign bit.
*/

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

Фактический используемый интерфейс типа long затем определяется в longobject.h путем создания нового типа PyLongObject, подобного этому -

typedef struct _longobject PyLongObject;

и т. Д.

Внутри longobject.c происходит больше вещей, вы можете взглянуть на них для более подробной информации.

Answer 3

Типы данных, такие как int в C, напрямую (более или менее) отображаются на типы данных, поддерживаемые процессором. Таким образом, ограничения на C int по сути являются ограничениями, налагаемыми аппаратным обеспечением процессора.

Но можно реализовать собственный тип данных int полностью в программном обеспечении. Например, вы можете использовать массив цифр в качестве основного представления. Может быть так:

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

Как только вы это сделаете, вы можете использовать этот класс и хранить целые числа, содержащие столько цифр, сколько вы хотите, до тех пор, пока у вас не закончится память.

Возможно, Python делает что-то подобное внутри своей виртуальной машины. Вы можете прочитать эту статью об Арифметике произвольной точности, чтобы узнать подробности.

Answer 4

Не октаворд. В нем реализована структура bignum для хранения чисел произвольной точности.

Answer 5

Python присваивает long целым числам (все int s в Python 3) столько места, сколько им нужно - массив «цифр» (основание равно степени 2), выделяемый по мере необходимости.