🕺🏾 👨🏿 🤷 Comment les nombres entiers très longs sont-ils implémentés en Python? 🙃 🤚🏾 🗼

Une traduction de l'article a été préparée spécialement pour les étudiants du cours de développeur Python .

Lorsque vous écrivez dans un langage de bas niveau tel que C, vous vous inquiétez de choisir le bon type de données et les bons qualificateurs pour vos entiers, à chaque étape, vous analysez s'il sera suffisant de l'utiliser simplement intou si vous devez ajouter longou même long double. Cependant, lorsque vous écrivez du code en Python, vous n'avez pas à vous soucier de ces choses "mineures", car Python peut fonctionner avec des nombres de integern'importe quel type de taille.

En C, si vous essayez de calculer 2 ^{20000 en} utilisant la fonction intégrée powl, vous obtiendrez la sortie inf.

#include <stdio.h>
#include <math.h>

int main(void) {
  printf("%Lf\n", powl(2, 20000));
  return 0;
}

$ ./a.out
inf

Mais en Python, rendre cela plus facile que jamais est facile:

>>> 2 ** 20000
39802768403379665923543072061912024537047727804924259387134 ...
...
... 6021 digits long ...
...
6309376

Ce doit être sous le capot que Python fait quelque chose de très beau, et aujourd'hui nous allons découvrir ce qu'il fait pour travailler avec des entiers de taille arbitraire!

Présentation et définition

Integer en Python, il s'agit d'une structure C définie comme suit:

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

PyObject_VAR_HEADEst une macro, elle se développe en PyVarObject, qui a la structure suivante:

typedef struct {
    PyObject ob_base;
    Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;

D'autres types qui ont PyObject_VAR_HEAD:

PyBytesObject
PyTupleObject
PyListObject

Cela signifie qu'un entier, comme un tuple ou une liste, a une longueur variable, et c'est la première étape pour comprendre comment Python peut prendre en charge le travail avec des nombres géants. Une fois développée, la macro _longobjectpeut être considérée comme:

struct _longobject {
    PyObject ob_base;
    Py_ssize_t ob_size; /* Number of items in variable part */
    digit ob_digit[1];
};

Il PyObjecty a quelques méta-champs dans la structure qui sont utilisés pour le comptage des références (garbage collection), mais pour en parler, nous avons besoin d'un article séparé. Le domaine sur lequel nous allons nous concentrer sur cela ob_digitet dans un peu ob_size.

Décryptage `ob_digit`

ob_digitEst un tableau alloué statiquement de longueur unitaire de type digit (typedef uint32_t). Puisqu'il s'agit d'un tableau, il ob_digits'agit principalement d'un pointeur vers un nombre et, par conséquent, si nécessaire, il peut être augmenté à l'aide de la fonction malloc à n'importe quelle longueur. De cette façon, python peut représenter et traiter des nombres très longs.

En règle générale, dans les langages de bas niveau tels que C, la précision des entiers est limitée à 64 bits, mais Python prend en charge les entiers de précision arbitraire . À partir de Python 3, tous les nombres sont présentés sous la forme bignumet ne sont limités que par la mémoire système disponible.

Décryptage `ob_size`

ob_sizestocke le nombre d'éléments dans ob_digit. Python remplace et utilise ensuite la valeur ob_sizepour déterminer le nombre réel d'éléments contenus dans le tableau pour augmenter l'efficacité de l'allocation de mémoire au tableau ob_digit.

Espace de rangement

La façon la plus naïve de stocker des nombres entiers est de stocker un chiffre décimal dans un élément du tableau, puis des opérations telles que l'addition et la soustraction peuvent être effectuées selon les règles mathématiques de l'école primaire.

Avec cette approche, le nombre 5238 sera enregistré comme ceci:

Cette approche est inefficace, car nous utiliserons jusqu'à 32 bits (uint32_t) pour stocker un chiffre décimal, qui, en fait, va de 0 à 9 et peut être facilement représenté avec seulement 4 bits, car lors de l'écriture de quelque chose d'aussi polyvalent que python, le développeur du noyau doit être encore plus inventif.

Alors, pouvons-nous faire mieux? Bien sûr, sinon je n'aurais pas posté cet article. Examinons de plus près comment Python stocke un entier extra-long.

Chemin Python

Au lieu de stocker un seul chiffre décimal dans chaque élément du tableau ob_digit, Python convertit les nombres du système numérique avec une base de 10 en nombres dans un système avec une base de 2 ³⁰ et appelle chaque élément comme un chiffre dont la valeur varie de 0 à 2 ^30-1 .

Dans le système numérique hexadécimal, la base 16 ~ 2 ⁴ signifie que chaque "chiffre" du nombre hexadécimal va de 0 à 15 dans le système numérique décimal. En Python, de même, un «nombre» avec une base de 2 ³⁰ , ce qui signifie que le nombre variera de 0 à 2 ³⁰ - 1 = 1073741823 en décimal.

De cette façon, Python utilise efficacement la quasi-totalité de l'espace alloué de 32 bits par chiffre, économise des ressources et effectue toujours des opérations simples, telles que l'ajout et la soustraction au niveau mathématique de l'école élémentaire.

Selon la plate-forme, Python utilise soit des tableaux entiers non signés 32 bits, soit des tableaux entiers non signés 16 bits avec des chiffres de 15 bits. Pour effectuer les opérations qui seront discutées plus loin, vous n'avez besoin que de quelques bits.

Exemple: 1152921504606846976

Comme mentionné, pour Python, les nombres sont représentés dans un système de base 2 ³⁰ , c'est-à-dire que si vous convertissez 1152921504606846976 en un nombre de base avec 2 ³⁰ base , vous obtenez 100.

1152921504606846976 = 1 * (2 ³⁰) ² + 0 * (2 ³⁰ ) ¹ + 0 * (2 ³⁰ ) ⁰

Étant donné que le ob_digitchiffre le moins significatif est enregistré en premier, il est enregistré sous 001 sous forme de trois chiffres.

La structure _longobjectde cette valeur contiendra:

ob_size comme 3
ob_digit comme [0, 0, 1]

J'ai créé une démo REPL qui montrera comment Python stocke un entier à l'intérieur de lui-même, et fait également référence aux membres de la structure tels que ob_size, ob_refcountetc.

Opérations longues entières

Maintenant que nous avons une idée claire de la façon dont Python implémente des entiers de précision arbitraire, il est temps de comprendre comment diverses opérations mathématiques sont effectuées avec eux.

Une addition

Les entiers sont stockés "en nombre", ce qui signifie que l'addition est aussi simple qu'à l'école primaire, et le code source Python nous montre que c'est ainsi que l'addition est implémentée. Une fonction avec un nom x_adddans un fichier longobject.cajoute deux nombres.

...
    for (i = 0; i < size_b; ++i) {
        carry += a->ob_digit[i] + b->ob_digit[i];
        z->ob_digit[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    for (; i < size_a; ++i) {
        carry += a->ob_digit[i];
        z->ob_digit[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    z->ob_digit[i] = carry;
...

L'extrait de code ci-dessus est tiré d'une fonction x_add. Comme vous pouvez le voir, il itère sur un nombre par nombre et effectue l'ajout de nombres, calcule le résultat et ajoute un trait d'union.

Cela devient plus intéressant lorsque le résultat de l'addition est un nombre négatif. Le signe ob_sizeest un signe entier, c'est-à-dire que si vous avez un nombre négatif, ce ob_sizesera un moins. La valeur ob_sizemodulo déterminera le nombre de chiffres dans ob_digit.

Soustraction

Tout comme l'addition a lieu, la soustraction a également lieu. Une fonction avec un nom x_subdans le fichier longobject.csoustrait un nombre d'un autre.

...
    for (i = 0; i < size_b; ++i) {
        borrow = a->ob_digit[i] - b->ob_digit[i] - borrow;
        z->ob_digit[i] = borrow & PyLong_MASK;
        borrow >>= PyLong_SHIFT;
        borrow &= 1; /* Keep only one sign bit */
    }
    for (; i < size_a; ++i) {
        borrow = a->ob_digit[i] - borrow;
        z->ob_digit[i] = borrow & PyLong_MASK;
        borrow >>= PyLong_SHIFT;
        borrow &= 1; /* Keep only one sign bit */
    }
...

L'extrait de code ci-dessus est tiré d'une fonction x_sub. Vous y voyez comment l'énumération des nombres se produit et la soustraction est effectuée, le résultat est calculé et le transfert est distribué. En effet, il est très similaire à l'addition.

Multiplication

Et encore une fois, la multiplication sera mise en œuvre de la même manière naïve que celle que nous avons apprise des leçons de mathématiques au primaire, mais elle n'est pas très efficace. Pour maintenir l'efficacité, Python implémente l'algorithme de Karatsuba , qui multiplie deux nombres à n chiffres en O (n ^log₂³ ) étapes simples.

L'algorithme n'est pas simple et son implémentation dépasse le cadre de cet article, mais vous pouvez trouver son implémentation dans les fonctions k_mul et k_lopsided_muldans le fichier longobject.c.

Division et autres opérations

Toutes les opérations sur les entiers sont définies dans le fichier longobject.c, elles sont très simples pour trouver et tracer le travail de chacun. Attention: Une compréhension détaillée du travail de chacun d'entre eux prendra du temps, alors faites le plein de pop-corn à l'avance .

Python préalloue un petit nombre d'entiers en mémoire allant de -5 à 256. Cette allocation se produit lors de l'initialisation, et comme nous ne pouvons pas changer les entiers (immuabilité), ces nombres pré-alloués sont singleton et sont directement référencés au lieu d'être alloués. Cela signifie que chaque fois que nous utilisons / créons un petit nombre, Python au lieu de le vendre renvoie simplement une référence au numéro précédemment alloué.

Une telle optimisation peut être tracée dans la macro IS_SMALL_INTet la fonction get_small_intc longobject.c. Python économise donc beaucoup d'espace et de temps dans le calcul des nombres entiers couramment utilisés.

Ceci est le deuxième article de la série Python Internals. Le premier article était sur la façon dont j'ai changé ma version de Python pour la rendreambigu . Il vous aidera à faire les premiers pas dans la compréhension du code source Python et à continuer le chemin pour devenir un développeur de noyau Python.

Si vous souhaitez voir plus d'articles similaires, abonnez-vous à ma newsletter et recevez-les directement dans votre boîte de réception. J'écris sur l'ingénierie, l'ingénierie des systèmes et un peu sur la programmation tous les vendredis. Envoyez- moi un courriel à @arpit_bhayani . Vous pouvez retrouver mes précédents articles sur @ arpitbhayani.me / blogs .

C'est tout. Rendez-vous sur le parcours !

Comment les nombres entiers très longs sont-ils implémentés en Python?