Làm thế nào để python lưu trữ số nguyên lớn?

Python đại diện cho tất cả các đối tượng theo cấu trúc C. Cấu trúc dữ liệu sau chịu trách nhiệm cho tất cả các đối tượng số nguyên

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

Sau khi mở rộng macro, một phiên bản đơn giản hóa của cấu trúc trông như sau

struct {
    ssize_t ob_refcnt;
    struct _typeobject *ob_type;
    ssize_t ob_size; 
    uint32_t ob_digit[1];
};

Trường ob_refcnt chịu trách nhiệm về kỹ thuật đếm tham chiếu được sử dụng trong cơ chế thu gom rác, trong khi đó, ob_type là con trỏ tới cấu trúc mô tả kiểu số nguyên

Nói chung, trong các ngôn ngữ như C/C++, độ chính xác của số nguyên được giới hạn ở 64 bit, nhưng Python có hỗ trợ tích hợp cho số nguyên có độ chính xác tùy ý. Vì Python 3 không còn kiểu số nguyên đơn giản nữa và tất cả các số nguyên được biểu diễn dưới dạng bignum

Làm thế nào để lưu trữ số nguyên lớn tùy ý?

Một trong những giải pháp là biểu diễn số nguyên dưới dạng một mảng các chữ số. Để làm điều đó một cách hiệu quả, chúng ta cần chuyển đổi số của mình từ cơ số 10 sang hệ số cơ số $2^{30}$, trong đó mỗi phần tử đại diện cho một 'chữ số' trong phạm vi từ $0$ đến $2^{30}-1 . Tùy thuộc vào nền tảng, Python sử dụng mảng số nguyên không dấu 32 bit với các chữ số 30 bit hoặc mảng số nguyên không dấu 16 bit với các chữ số 15 bit. Sử dụng cách tiếp cận như vậy giới thiệu, đó là lý do tại sao chúng ta không thể sử dụng tất cả các bit của số nguyên. Trường ob_digit trong cấu trúc ở trên chịu trách nhiệm cho các mảng đó

Để loại bỏ tính toán không cần thiết, CPython có triển khai "đường dẫn nhanh" cho các số nguyên trong phạm vi từ $-2^{30}$ đến $2^{30}$. Các số nguyên như vậy được lưu trữ dưới dạng một mảng của một phần tử và nếu có thể được coi là số nguyên 32 bit cố định

Lưu ý rằng, không giống như cách tiếp cận cổ điển, dấu của một số nguyên được lưu trữ riêng trong trường ob_size. Trường này lưu trữ kích thước của mảng ob_digit. Vì vậy, nếu bạn muốn đổi dấu của mảng có kích thước 2, bạn cần đặt ob_size thành -2

Từ mã nguồn mô tả nó như sau

/* 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