Hướng dẫn how do ints work in python? - ints hoạt động như thế nào trong python?

Question

Trong các phần trước của loạt bài này, chúng tôi đã nghiên cứu cốt lõi của thông dịch viên CPython và thấy các khía cạnh cơ bản nhất của Python được thực hiện như thế nào. Chúng tôi đã đưa ra một cái nhìn tổng quan về VM Cpython, xem xét trình biên dịch CPython, bước qua mã nguồn CPython, nghiên cứu cách VM thực thi mã byte và học cách các biến hoạt động. Trong hai bài viết gần đây nhất, chúng tôi tập trung vào hệ thống đối tượng Python. Chúng tôi đã học được những đối tượng Python và loại Python là gì, cách chúng được xác định và những gì quyết định hành vi của chúng. Cuộc thảo luận này đã cho chúng ta một sự hiểu biết tốt về cách các đối tượng Python hoạt động nói chung. Những gì chúng ta chưa thảo luận là làm thế nào các đối tượng cụ thể, chẳng hạn như chuỗi, số nguyên và danh sách, được thực hiện. Trong phần này và một số bài đăng sắp tới, chúng tôi sẽ đề cập đến việc triển khai các loại tích hợp quan trọng nhất và thú vị nhất. Chủ đề của bài hôm nay là

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

4.

Nội dung chính Show

Tại sao số nguyên python lại thú vị
Đại diện Bignum
Số học Bignum
Cộng và trừ)
Phép nhân
Bignums của CPython so với các triển khai Bignum khác
Cân nhắc sử dụng bộ nhớ
Sự kết luận
INT được đại diện như thế nào trong Python?
INT làm tròn hay xuống trong Python?
Int () làm gì trong Python cho số thập phân?
Số int trong Python là gì?

Lưu ý: Trong bài đăng này, tôi đang đề cập đến CPython 3.9. Một số chi tiết thực hiện chắc chắn sẽ thay đổi khi CPython phát triển. Tôi sẽ cố gắng theo dõi các thay đổi quan trọng và thêm ghi chú cập nhật.: In this post I'm referring to CPython 3.9. Some implementation details will certainly change as CPython evolves. I'll try to keep track of important changes and add update notes.

Tại sao số nguyên python lại thú vị

Số nguyên yêu cầu không giới thiệu. Chúng có mặt khắp nơi và có vẻ cơ bản đến mức bạn có thể nghi ngờ liệu nó có đáng để thảo luận về cách chúng được thực hiện hay không. Tuy nhiên, các số nguyên Python rất thú vị vì chúng không chỉ là số nguyên 32 bit hoặc 64 bit mà CPU hoạt động với nguyên bản. Các số nguyên Python là các số nguyên chính xác tùy ý, còn được gọi là bignums. Điều này có nghĩa là chúng có thể lớn như chúng ta muốn, và kích thước của chúng chỉ bị giới hạn bởi lượng bộ nhớ có sẵn.

Bignums có ích để làm việc vì chúng ta không cần phải lo lắng về những thứ như tràn và dòng chảy. Chúng được sử dụng rộng rãi trong các lĩnh vực như mật mã và đại số máy tính, nơi số lượng lớn phát sinh mọi lúc và phải được biểu diễn chính xác. Vì vậy, nhiều ngôn ngữ lập trình có các bignums tích hợp. Chúng bao gồm Python, JavaScript, Ruby, Haskell, Erlang, Julia, vợt. Những người khác cung cấp bignums như một phần của thư viện tiêu chuẩn. Chúng bao gồm Go, Java, C#, D, PHP. Nhiều thư viện bên thứ ba thực hiện Bignums. Phổ biến nhất là Thư viện số học chính xác GNU (GMP). Nó cung cấp API C nhưng có các ràng buộc cho tất cả các ngôn ngữ chính.

Có rất nhiều triển khai Bignum. Chúng khác nhau về chi tiết, nhưng cách tiếp cận chung để thực hiện Bignums là như nhau. Hôm nay chúng ta sẽ thấy cách tiếp cận này trông như thế nào và sử dụng triển khai của Cpython làm ví dụ tham khảo. Hai câu hỏi chính chúng ta sẽ phải trả lời là:

làm thế nào để đại diện cho Bignums; và
Làm thế nào để thực hiện các hoạt động số học, chẳng hạn như bổ sung và nhân, trên bignums.

Chúng tôi cũng sẽ thảo luận về cách triển khai của CPython so với những người khác và những gì CPython làm để làm cho các số nguyên hiệu quả hơn.

Đại diện Bignum

Hãy suy nghĩ trong một khoảnh khắc làm thế nào bạn sẽ đại diện cho các số nguyên lớn trong chương trình của bạn nếu bạn tự thực hiện chúng. Có lẽ cách rõ ràng nhất để làm điều đó là lưu trữ một số nguyên dưới dạng một chuỗi các chữ số, giống như chúng ta thường viết ra các số. Ví dụ, số nguyên

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

5 có thể được biểu diễn là

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

6. Đây thực chất là cách Bignums được thể hiện trong thực tế. Sự khác biệt quan trọng duy nhất là thay vì cơ sở 10, các cơ sở lớn hơn nhiều được sử dụng. Ví dụ: Cpython sử dụng cơ sở 2^15 hoặc cơ sở 2^30 tùy thuộc vào nền tảng. Có gì sai với Base 10? Nếu chúng ta đại diện cho mỗi chữ số theo một chuỗi với một byte duy nhất nhưng chỉ sử dụng 10 trong số 256 giá trị có thể, thì nó sẽ rất chính xác. Chúng tôi có thể giải quyết vấn đề hiệu quả bộ nhớ này nếu chúng tôi sử dụng cơ sở 256, để mỗi chữ số có giá trị từ 0 đến 255. Nhưng các cơ sở lớn hơn vẫn được sử dụng trong thực tế. Lý do cho điều đó là vì cơ sở lớn hơn có nghĩa là các số có ít chữ số hơn và các số chữ số ít hơn có, các hoạt động số học nhanh hơn được thực hiện. Các cơ sở không thể là lớn tùy ý. Nó thường bị giới hạn bởi kích thước của các số nguyên mà CPU có thể hoạt động. Chúng ta sẽ thấy lý do tại sao đây là trường hợp khi chúng ta thảo luận về số học Bignum trong phần tiếp theo. Bây giờ chúng ta hãy xem Cpython đại diện cho Bignums như thế nào.

Tất cả mọi thứ liên quan đến việc đại diện cho các số nguyên Python có thể được tìm thấy trong

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

7. Về mặt kỹ thuật, các số nguyên python là các trường hợp của

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

8, được xác định trong

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

9, nhưng

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

8 thực sự là một typedef cho

$ python -q
>>> base = 2**30
>>> -(3 * base**0 + 5 * base**1 + 1 * base**2)
-1152921509975556099

1 được xác định trong

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

7:

struct _longobject {
    PyVarObject ob_base; // expansion of PyObject_VAR_HEAD macro
    digit ob_digit[1];
};

Cấu trúc này mở rộng

$ python -q
>>> base = 2**30
>>> -(3 * base**0 + 5 * base**1 + 1 * base**2)
-1152921509975556099

3, lần lượt mở rộng

$ python -q
>>> base = 2**30
>>> -(3 * base**0 + 5 * base**1 + 1 * base**2)
-1152921509975556099

4:

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

Vì vậy, bên cạnh một số lượng tham chiếu và một loại mà tất cả các đối tượng Python có, một đối tượng số nguyên có hai thành viên khác:

$ python -q
>>> base = 2**30
>>> -(3 * base**0 + 5 * base**1 + 1 * base**2)
-1152921509975556099

5 đến từ

$ python -q
>>> base = 2**30
>>> -(3 * base**0 + 5 * base**1 + 1 * base**2)
-1152921509975556099

3; và

$ python -q
>>> base = 2**30
>>> -(3 * base**0 + 5 * base**1 + 1 * base**2)
-1152921509975556099

7 được xác định trong

$ python -q
>>> base = 2**30
>>> -(3 * base**0 + 5 * base**1 + 1 * base**2)
-1152921509975556099

1.

Thành viên

$ python -q
>>> base = 2**30
>>> -(3 * base**0 + 5 * base**1 + 1 * base**2)
-1152921509975556099

7 là một con trỏ đến một mảng các chữ số. Trên các nền tảng 64 bit, mỗi chữ số là một số nguyên 30 bit có các giá trị trong khoảng từ 0 đến 2^30-1 và được lưu trữ dưới dạng int 32 bit không dấu (

>>> x = 51090942171709440000
>>> x % base
952369152
>>> (x // base) % base
337507546
>>> (x // base // base) % base
44
>>> (x // base // base // base) % base
0

0 là một typedef cho

>>> x = 51090942171709440000
>>> x % base
952369152
>>> (x // base) % base
337507546
>>> (x // base // base) % base
44
>>> (x // base // base // base) % base
0

1). Trên các nền tảng 32 bit, mỗi chữ số là một số nguyên 15 bit có các giá trị trong khoảng từ 0 đến 2^15-1 và được lưu trữ dưới dạng int 16 bit không dấu (

>>> x = 51090942171709440000
>>> x % base
952369152
>>> (x // base) % base
337507546
>>> (x // base // base) % base
44
>>> (x // base // base // base) % base
0

0 là một typedef cho

>>> x = 51090942171709440000
>>> x % base
952369152
>>> (x // base) % base
337507546
>>> (x // base // base) % base
44
>>> (x // base // base // base) % base
0

3). Để làm cho mọi thứ cụ thể, trong bài đăng này, chúng tôi sẽ cho rằng các chữ số dài 30 bit.

Thành viên

$ python -q
>>> base = 2**30
>>> -(3 * base**0 + 5 * base**1 + 1 * base**2)
-1152921509975556099

5 là một int đã ký, có giá trị tuyệt đối cho chúng ta biết số lượng chữ số trong mảng

$ python -q
>>> base = 2**30
>>> -(3 * base**0 + 5 * base**1 + 1 * base**2)
-1152921509975556099

7. Dấu hiệu của

$ python -q
>>> base = 2**30
>>> -(3 * base**0 + 5 * base**1 + 1 * base**2)
-1152921509975556099

5 cho thấy dấu hiệu của số nguyên. Âm

$ python -q
>>> base = 2**30
>>> -(3 * base**0 + 5 * base**1 + 1 * base**2)
-1152921509975556099

5 có nghĩa là số nguyên là âm. Nếu

$ python -q
>>> base = 2**30
>>> -(3 * base**0 + 5 * base**1 + 1 * base**2)
-1152921509975556099

5 là 0, thì số nguyên là 0.

Các chữ số được lưu trữ theo thứ tự nhỏ. Chữ số đầu tiên (

>>> x = 51090942171709440000
>>> x % base
952369152
>>> (x // base) % base
337507546
>>> (x // base // base) % base
44
>>> (x // base // base // base) % base
0

9) là ít có ý nghĩa nhất và chữ số cuối cùng (

import ctypes


MAX_DIGITS = 1000

# This is a class to map a C `PyLongObject` struct to a Python object
class PyLongObject(ctypes.Structure):
    _fields_ = [
        ("ob_refcnt", ctypes.c_ssize_t),
        ("ob_type", ctypes.c_void_p),
        ("ob_size", ctypes.c_ssize_t),
        ("ob_digit", MAX_DIGITS * ctypes.c_uint32)
    ]


def get_digits(num):
    obj = PyLongObject.from_address(id(num))
    digits_len = abs(obj.ob_size)
    return obj.ob_digit[:digits_len]

0) là có ý nghĩa nhất.

Cuối cùng, giá trị tuyệt đối của một số nguyên được tính toán như sau:

$$ val = ob \ _digit [0] \ Times (2 ^{30}) ^0 + ob \ _digit [1] \ Times (2 ^{30}) _Size | - 1] \ lần (2 ^{30}) ^{| ob \ _size | - 1} $$

Hãy xem tất cả những điều này có nghĩa là gì với một ví dụ. Giả sử chúng ta có một đối tượng số nguyên có

import ctypes


MAX_DIGITS = 1000

# This is a class to map a C `PyLongObject` struct to a Python object
class PyLongObject(ctypes.Structure):
    _fields_ = [
        ("ob_refcnt", ctypes.c_ssize_t),
        ("ob_type", ctypes.c_void_p),
        ("ob_size", ctypes.c_ssize_t),
        ("ob_digit", MAX_DIGITS * ctypes.c_uint32)
    ]


def get_digits(num):
    obj = PyLongObject.from_address(id(num))
    digits_len = abs(obj.ob_size)
    return obj.ob_digit[:digits_len]

1 và

import ctypes


MAX_DIGITS = 1000

# This is a class to map a C `PyLongObject` struct to a Python object
class PyLongObject(ctypes.Structure):
    _fields_ = [
        ("ob_refcnt", ctypes.c_ssize_t),
        ("ob_type", ctypes.c_void_p),
        ("ob_size", ctypes.c_ssize_t),
        ("ob_digit", MAX_DIGITS * ctypes.c_uint32)
    ]


def get_digits(num):
    obj = PyLongObject.from_address(id(num))
    digits_len = abs(obj.ob_size)
    return obj.ob_digit[:digits_len]

2. Để tính toán giá trị của nó, chúng ta có thể làm như sau:

$ python -q
>>> base = 2**30
>>> -(3 * base**0 + 5 * base**1 + 1 * base**2)
-1152921509975556099

Bây giờ chúng ta hãy làm ngược lại. Giả sử chúng ta muốn có được biểu diễn Bignum của số

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

5. Đây là cách chúng ta có thể làm điều đó:

>>> x = 51090942171709440000
>>> x % base
952369152
>>> (x // base) % base
337507546
>>> (x // base // base) % base
44
>>> (x // base // base // base) % base
0

Vì vậy,

import ctypes


MAX_DIGITS = 1000

# This is a class to map a C `PyLongObject` struct to a Python object
class PyLongObject(ctypes.Structure):
    _fields_ = [
        ("ob_refcnt", ctypes.c_ssize_t),
        ("ob_type", ctypes.c_void_p),
        ("ob_size", ctypes.c_ssize_t),
        ("ob_digit", MAX_DIGITS * ctypes.c_uint32)
    ]


def get_digits(num):
    obj = PyLongObject.from_address(id(num))
    digits_len = abs(obj.ob_size)
    return obj.ob_digit[:digits_len]

4 và

import ctypes


MAX_DIGITS = 1000

# This is a class to map a C `PyLongObject` struct to a Python object
class PyLongObject(ctypes.Structure):
    _fields_ = [
        ("ob_refcnt", ctypes.c_ssize_t),
        ("ob_type", ctypes.c_void_p),
        ("ob_size", ctypes.c_ssize_t),
        ("ob_digit", MAX_DIGITS * ctypes.c_uint32)
    ]


def get_digits(num):
    obj = PyLongObject.from_address(id(num))
    digits_len = abs(obj.ob_size)
    return obj.ob_digit[:digits_len]

5. Trên thực tế, chúng ta thậm chí không phải tính toán các chữ số, chúng ta có thể nhận chúng bằng cách kiểm tra đối tượng số nguyên bằng thư viện tiêu chuẩn

import ctypes


MAX_DIGITS = 1000

# This is a class to map a C `PyLongObject` struct to a Python object
class PyLongObject(ctypes.Structure):
    _fields_ = [
        ("ob_refcnt", ctypes.c_ssize_t),
        ("ob_type", ctypes.c_void_p),
        ("ob_size", ctypes.c_ssize_t),
        ("ob_digit", MAX_DIGITS * ctypes.c_uint32)
    ]


def get_digits(num):
    obj = PyLongObject.from_address(id(num))
    digits_len = abs(obj.ob_size)
    return obj.ob_digit[:digits_len]

6:

import ctypes


MAX_DIGITS = 1000

# This is a class to map a C `PyLongObject` struct to a Python object
class PyLongObject(ctypes.Structure):
    _fields_ = [
        ("ob_refcnt", ctypes.c_ssize_t),
        ("ob_type", ctypes.c_void_p),
        ("ob_size", ctypes.c_ssize_t),
        ("ob_digit", MAX_DIGITS * ctypes.c_uint32)
    ]


def get_digits(num):
    obj = PyLongObject.from_address(id(num))
    digits_len = abs(obj.ob_size)
    return obj.ob_digit[:digits_len]

>>> from num_digits import get_digits
>>> x = 51090942171709440000
>>> get_digits(x)
[952369152, 337507546, 44]

Như bạn có thể đoán, đại diện của Bignums là một phần dễ dàng. Thách thức chính là thực hiện các hoạt động số học và thực hiện chúng một cách hiệu quả.

Số học Bignum

Chúng tôi đã học được trong Phần 6 rằng hành vi của một đối tượng Python được xác định bởi loại đối tượng. Mỗi thành viên của một loại, được gọi là khe, chịu trách nhiệm cho một khía cạnh cụ thể của hành vi của đối tượng. Vì vậy, để hiểu cách CPython thực hiện các hoạt động số học trên các số nguyên, chúng ta cần nghiên cứu các vị trí của loại

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

4 thực hiện các hoạt động đó.

Trong mã C, loại

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

4 được gọi là

import ctypes


MAX_DIGITS = 1000

# This is a class to map a C `PyLongObject` struct to a Python object
class PyLongObject(ctypes.Structure):
    _fields_ = [
        ("ob_refcnt", ctypes.c_ssize_t),
        ("ob_type", ctypes.c_void_p),
        ("ob_size", ctypes.c_ssize_t),
        ("ob_digit", MAX_DIGITS * ctypes.c_uint32)
    ]


def get_digits(num):
    obj = PyLongObject.from_address(id(num))
    digits_len = abs(obj.ob_size)
    return obj.ob_digit[:digits_len]

9. Nó được định nghĩa trong

>>> from num_digits import get_digits
>>> x = 51090942171709440000
>>> get_digits(x)
[952369152, 337507546, 44]

0 như sau:

PyTypeObject     PyVarObject_HEAD_INIT     "int",     offsetof(    sizeof(<     0,     0,     0,     0,     0,     long_to_decimal_string    &long_as_number     0,     0,     (hashfunc    0,     0,     PyObject_GenericGetAttr    0,     0,     Py_TPFLAGS_DEFAULT         Py_TPFLAGS_LONG_SUBCLASS     long_doc,     0,     0,     long_richcompare    0,     0,     0,     long_methods,     0,     long_getset,     0,     0,     0,     0,     0,     0,     0,     long_new,     PyObject_Del, };

PyLong_Type = { (&PyType_Type, 0) /* tp_name */ >PyLongObject, ob_digit), /* tp_basicsize */ span>digit), /* tp_itemsize */ /* tp_dealloc */ /* tp_vectorcall_offset */ /* tp_getattr */ /* tp_setattr */ /* tp_as_async */ >, /* tp_repr */ , /* tp_as_number */ /* tp_as_sequence */ /* tp_as_mapping */ >)long_hash, /* tp_hash */ /* tp_call */ /* tp_str */ n>, /* tp_getattro */ /* tp_setattro */ /* tp_as_buffer */ | Py_TPFLAGS_BASETYPE | , /* tp_flags */ /* tp_doc */ /* tp_traverse */ /* tp_clear */ >, /* tp_richcompare */ /* tp_weaklistoffset */ /* tp_iter */ /* tp_iternext */ /* tp_methods */ /* tp_members */ /* tp_getset */ /* tp_base */ /* tp_dict */ /* tp_descr_get */ /* tp_descr_set */ /* tp_dictoffset */ /* tp_init */ /* tp_alloc */ /* tp_new */ /* tp_free */

Chúng ta có thể thấy hàm

>>> from num_digits import get_digits
>>> x = 51090942171709440000
>>> get_digits(x)
[952369152, 337507546, 44]

1 tạo ra các số nguyên mới, hàm

>>> from num_digits import get_digits
>>> x = 51090942171709440000
>>> get_digits(x)
[952369152, 337507546, 44]

2 tính toán băm và việc triển khai một số vị trí quan trọng khác. Trong bài đăng này, chúng tôi sẽ tập trung vào các vị trí thực hiện các hoạt động số học cơ bản: bổ sung, trừ và nhân. Các khe này được nhóm lại với nhau trong bộ

>>> from num_digits import get_digits
>>> x = 51090942171709440000
>>> get_digits(x)
[952369152, 337507546, 44]

3. Đây là những gì nó trông giống như:

static PyNumberMethods long_as_number = {
    (binaryfunc)long_add,       /*nb_add*/
    (binaryfunc)long_sub,       /*nb_subtract*/
    (binaryfunc)long_mul,       /*nb_multiply*/
    long_mod,                   /*nb_remainder*/
    long_divmod,                /*nb_divmod*/
    long_pow,                   /*nb_power*/
    (unaryfunc)long_neg,        /*nb_negative*/
    long_long,                  /*tp_positive*/
    (unaryfunc)long_abs,        /*tp_absolute*/
    (inquiry)long_bool,         /*tp_bool*/
    (unaryfunc)long_invert,     /*nb_invert*/
    long_lshift,                /*nb_lshift*/
    long_rshift,                /*nb_rshift*/
    long_and,                   /*nb_and*/
    long_xor,                   /*nb_xor*/
    long_or,                    /*nb_or*/
    long_long,                  /*nb_int*/
    0,                          /*nb_reserved*/
    long_float,                 /*nb_float*/
    0,                          /* nb_inplace_add */
    0,                          /* nb_inplace_subtract */
    0,                          /* nb_inplace_multiply */
    0,                          /* nb_inplace_remainder */
    0,                          /* nb_inplace_power */
    0,                          /* nb_inplace_lshift */
    0,                          /* nb_inplace_rshift */
    0,                          /* nb_inplace_and */
    0,                          /* nb_inplace_xor */
    0,                          /* nb_inplace_or */
    long_div,                   /* nb_floor_divide */
    long_true_divide,           /* nb_true_divide */
    0,                          /* nb_inplace_floor_divide */
    0,                          /* nb_inplace_true_divide */
    long_long,                  /* nb_index */
};

Chúng tôi sẽ bắt đầu bằng cách nghiên cứu hàm

>>> from num_digits import get_digits
>>> x = 51090942171709440000
>>> get_digits(x)
[952369152, 337507546, 44]

4 thực hiện bổ sung số nguyên.

Cộng và trừ)

Đầu tiên lưu ý rằng một hàm thêm hai số nguyên có thể được thể hiện thông qua hai hàm khác chỉ liên quan đến các giá trị tuyệt đối:

một hàm thêm các giá trị tuyệt đối của hai số nguyên; và
Một hàm trừ các giá trị tuyệt đối của hai số nguyên.

Nó có thể bởi vì:

$$-| A |+(-| B |) =-(| A |+| B |) $$ $$

$$ | A |+(-| B |) = | A |-| B | $$

$$-| A |+| B | = | B |-| A | $$

CPython sử dụng các danh tính đơn giản này để thể hiện hàm

>>> from num_digits import get_digits
>>> x = 51090942171709440000
>>> get_digits(x)
[952369152, 337507546, 44]

4 thông qua hàm

>>> from num_digits import get_digits
>>> x = 51090942171709440000
>>> get_digits(x)
[952369152, 337507546, 44]

6 thêm các giá trị tuyệt đối của hai số nguyên và hàm

>>> from num_digits import get_digits
>>> x = 51090942171709440000
>>> get_digits(x)
[952369152, 337507546, 44]

7 trừ các giá trị tuyệt đối của hai số nguyên:

static PyObject *
long_add(PyLongObject *a, PyLongObject *b)
{
    PyLongObject *z;

    CHECK_BINOP(a, b);

    if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
        return PyLong_FromLong(MEDIUM_VALUE(a) + MEDIUM_VALUE(b));
    }
    if (Py_SIZE(a) < 0) {
        if (Py_SIZE(b) < 0) {
            z = x_add(a, b); // -|a|+(-|b|) = -(|a|+|b|)
            if (z != NULL) {
                /* x_add received at least one multiple-digit int,
                   and thus z must be a multiple-digit int.
                   That also means z is not an element of
                   small_ints, so negating it in-place is safe. */
                assert(Py_REFCNT(z) == 1);
                Py_SET_SIZE(z, -(Py_SIZE(z)));
            }
        }
        else
            z = x_sub(b, a); // -|a|+|b| = |b|-|a|
    }
    else {
        if (Py_SIZE(b) < 0)
            z = x_sub(a, b); // |a|+(-|b|) = |a|-|b|
        else
            z = x_add(a, b);
    }
    return (PyObject *)z;
}

Vì vậy, chúng ta cần hiểu làm thế nào

>>> from num_digits import get_digits
>>> x = 51090942171709440000
>>> get_digits(x)
[952369152, 337507546, 44]

6 và

>>> from num_digits import get_digits
>>> x = 51090942171709440000
>>> get_digits(x)
[952369152, 337507546, 44]

7 được thực hiện.

Nó chỉ ra rằng cách tốt nhất để thêm các giá trị tuyệt đối của hai Bignums là phương pháp cột được dạy trong trường tiểu học. Chúng tôi lấy chữ số ít đáng kể nhất của Bignum thứ nhất, lấy chữ số ít đáng kể nhất của Bignum thứ hai, thêm chúng lên và viết kết quả vào chữ số ít có ý nghĩa nhất của Bignum đầu ra. Nếu kết quả của việc bổ sung không phù hợp với một chữ số, chúng tôi viết cơ sở modulo kết quả và nhớ mang theo. Sau đó, chúng tôi lấy chữ số ít có ý nghĩa nhất thứ hai của Bignum thứ nhất, chữ số ít có ý nghĩa thứ hai của Bignum thứ hai, thêm chúng vào mang, viết cơ sở modulo kết quả vào chữ số ít có ý nghĩa thứ hai của bignum đầu ra và nhớ mang theo. Quá trình tiếp tục cho đến khi không còn chữ số và lần mang cuối cùng được ghi vào đầu ra Bignum. Đây là việc triển khai thuật toán này của CPYThon:

// Some typedefs and macros used in the algorithm:
// typedef uint32_t digit;
// #define PyLong_SHIFT    30
// #define PyLong_BASE     ((digit)1 << PyLong_SHIFT)
// #define PyLong_MASK     ((digit)(PyLong_BASE - 1))


/* Add the absolute values of two integers. */
static PyLongObject *
x_add(PyLongObject *a, PyLongObject *b)
{
    Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));
    PyLongObject *z;
    Py_ssize_t i;
    digit carry = 0;

    /* Ensure a is the larger of the two: */
    if (size_a < size_b) {
        { PyLongObject *temp = a; a = b; b = temp; }
        { Py_ssize_t size_temp = size_a;
            size_a = size_b;
            size_b = size_temp; }
    }
    z = _PyLong_New(size_a+1);
    if (z == NULL)
        return NULL;
    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;
    return long_normalize(z);
}

Đầu tiên lưu ý rằng số nguyên python là bất biến. Cpython trả về một số nguyên mới là kết quả của một hoạt động số học. Kích thước của số nguyên mới ban đầu được đặt ở kích thước tối đa có thể của kết quả. Sau đó, nếu sau khi hoạt động được thực hiện, một số chữ số hàng đầu là số không, CPython thu nhỏ kích thước của số nguyên bằng cách gọi

PyTypeObject PyLong_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "int",                                      /* tp_name */
    offsetof(PyLongObject, ob_digit),           /* tp_basicsize */
    sizeof(digit),                              /* tp_itemsize */
    0,                                          /* tp_dealloc */
    0,                                          /* tp_vectorcall_offset */
    0,                                          /* tp_getattr */
    0,                                          /* tp_setattr */
    0,                                          /* tp_as_async */
    long_to_decimal_string,                     /* tp_repr */
    &long_as_number,                            /* tp_as_number */
    0,                                          /* tp_as_sequence */
    0,                                          /* tp_as_mapping */
    (hashfunc)long_hash,                        /* tp_hash */
    0,                                          /* tp_call */
    0,                                          /* tp_str */
    PyObject_GenericGetAttr,                    /* tp_getattro */
    0,                                          /* tp_setattro */
    0,                                          /* tp_as_buffer */
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE |
        Py_TPFLAGS_LONG_SUBCLASS,               /* tp_flags */
    long_doc,                                   /* tp_doc */
    0,                                          /* tp_traverse */
    0,                                          /* tp_clear */
    long_richcompare,                           /* tp_richcompare */
    0,                                          /* tp_weaklistoffset */
    0,                                          /* tp_iter */
    0,                                          /* tp_iternext */
    long_methods,                               /* tp_methods */
    0,                                          /* tp_members */
    long_getset,                                /* tp_getset */
    0,                                          /* tp_base */
    0,                                          /* tp_dict */
    0,                                          /* tp_descr_get */
    0,                                          /* tp_descr_set */
    0,                                          /* tp_dictoffset */
    0,                                          /* tp_init */
    0,                                          /* tp_alloc */
    long_new,                                   /* tp_new */
    PyObject_Del,                               /* tp_free */
};

0. Trong trường hợp bổ sung, CPython tạo ra một số nguyên mới dài hơn một chữ số so với toán hạng lớn hơn. Sau đó, nếu sau khi hoạt động được thực hiện, chữ số quan trọng nhất của kết quả là 0, CPython giảm kích thước của kết quả.

Cũng lưu ý rằng một chữ số mất 30 bit thấp hơn của int 32 bit. Khi chúng tôi thêm hai chữ số, chúng tôi nhận được tối đa số nguyên 31 bit và mang theo được lưu trữ ở bit 30 (đếm từ 0), vì vậy chúng tôi có thể dễ dàng truy cập nó.

Việc trừ các giá trị tuyệt đối của hai Bignum được thực hiện theo cách tương tự ngoại trừ việc mang theo được thay thế bằng vay. Chúng tôi cũng cần đảm bảo rằng Bignum đầu tiên là lớn hơn trong hai. Nếu đây không phải là trường hợp, chúng tôi trao đổi các bignums và thay đổi dấu hiệu của kết quả sau khi phép trừ được thực hiện. Vì nó được thực hiện trong Cpython, việc vay mượn rất dễ dàng vì theo đặc điểm kỹ thuật C, INT không dấu là một đối tượng của số học mô -đun:

Mặt khác, nếu loại mới không được ký, giá trị được chuyển đổi bằng cách liên tục thêm hoặc trừ một giá trị tối đa có thể được biểu diễn trong loại mới cho đến khi giá trị nằm trong phạm vi của loại mới.

Điều này có nghĩa là khi chúng ta trừ một chữ số lớn hơn từ một chữ số nhỏ hơn, int tối đa có thể được thêm vào kết quả để có được giá trị trong phạm vi hợp lệ. Ví dụ,

PyTypeObject PyLong_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "int",                                      /* tp_name */
    offsetof(PyLongObject, ob_digit),           /* tp_basicsize */
    sizeof(digit),                              /* tp_itemsize */
    0,                                          /* tp_dealloc */
    0,                                          /* tp_vectorcall_offset */
    0,                                          /* tp_getattr */
    0,                                          /* tp_setattr */
    0,                                          /* tp_as_async */
    long_to_decimal_string,                     /* tp_repr */
    &long_as_number,                            /* tp_as_number */
    0,                                          /* tp_as_sequence */
    0,                                          /* tp_as_mapping */
    (hashfunc)long_hash,                        /* tp_hash */
    0,                                          /* tp_call */
    0,                                          /* tp_str */
    PyObject_GenericGetAttr,                    /* tp_getattro */
    0,                                          /* tp_setattro */
    0,                                          /* tp_as_buffer */
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE |
        Py_TPFLAGS_LONG_SUBCLASS,               /* tp_flags */
    long_doc,                                   /* tp_doc */
    0,                                          /* tp_traverse */
    0,                                          /* tp_clear */
    long_richcompare,                           /* tp_richcompare */
    0,                                          /* tp_weaklistoffset */
    0,                                          /* tp_iter */
    0,                                          /* tp_iternext */
    long_methods,                               /* tp_methods */
    0,                                          /* tp_members */
    long_getset,                                /* tp_getset */
    0,                                          /* tp_base */
    0,                                          /* tp_dict */
    0,                                          /* tp_descr_get */
    0,                                          /* tp_descr_set */
    0,                                          /* tp_dictoffset */
    0,                                          /* tp_init */
    0,                                          /* tp_alloc */
    long_new,                                   /* tp_new */
    PyObject_Del,                               /* tp_free */
};

1. Để có được hiệu quả của việc vay, chúng tôi chỉ viết các bit 0-29 vào kết quả và kiểm tra bit 30 để xem việc vay có xảy ra không. Đây là cách Cpython làm tất cả những điều đó:

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

0

Hàm

PyTypeObject PyLong_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "int",                                      /* tp_name */
    offsetof(PyLongObject, ob_digit),           /* tp_basicsize */
    sizeof(digit),                              /* tp_itemsize */
    0,                                          /* tp_dealloc */
    0,                                          /* tp_vectorcall_offset */
    0,                                          /* tp_getattr */
    0,                                          /* tp_setattr */
    0,                                          /* tp_as_async */
    long_to_decimal_string,                     /* tp_repr */
    &long_as_number,                            /* tp_as_number */
    0,                                          /* tp_as_sequence */
    0,                                          /* tp_as_mapping */
    (hashfunc)long_hash,                        /* tp_hash */
    0,                                          /* tp_call */
    0,                                          /* tp_str */
    PyObject_GenericGetAttr,                    /* tp_getattro */
    0,                                          /* tp_setattro */
    0,                                          /* tp_as_buffer */
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE |
        Py_TPFLAGS_LONG_SUBCLASS,               /* tp_flags */
    long_doc,                                   /* tp_doc */
    0,                                          /* tp_traverse */
    0,                                          /* tp_clear */
    long_richcompare,                           /* tp_richcompare */
    0,                                          /* tp_weaklistoffset */
    0,                                          /* tp_iter */
    0,                                          /* tp_iternext */
    long_methods,                               /* tp_methods */
    0,                                          /* tp_members */
    long_getset,                                /* tp_getset */
    0,                                          /* tp_base */
    0,                                          /* tp_dict */
    0,                                          /* tp_descr_get */
    0,                                          /* tp_descr_set */
    0,                                          /* tp_dictoffset */
    0,                                          /* tp_init */
    0,                                          /* tp_alloc */
    long_new,                                   /* tp_new */
    PyObject_Del,                               /* tp_free */
};

2 thực hiện phép trừ số nguyên ủy quyền cho công việc cho

>>> from num_digits import get_digits
>>> x = 51090942171709440000
>>> get_digits(x)
[952369152, 337507546, 44]

6 và

>>> from num_digits import get_digits
>>> x = 51090942171709440000
>>> get_digits(x)
[952369152, 337507546, 44]

7, giống như

>>> from num_digits import get_digits
>>> x = 51090942171709440000
>>> get_digits(x)
[952369152, 337507546, 44]

4. Đây là:

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

1

Các hoạt động số học trên Bignums chậm hơn nhiều so với các hoạt động số học trên các số nguyên bản địa được thực hiện bởi CPU. Cụ thể, Bignum bổ sung chậm hơn nhiều so với bổ sung CPU. Và nó chậm hơn không chỉ bởi vì CPU thực hiện nhiều hoạt động số học để thêm hai Bignum mà chủ yếu là do Bignum bổ sung thường liên quan đến nhiều truy cập bộ nhớ và truy cập bộ nhớ có thể khá tốn kém, tức là tốn nhiều lần hơn hàng trăm lần so với hoạt động số học. May mắn thay, Cpython sử dụng một tối ưu hóa để thêm và trừ các số nguyên nhỏ nhanh hơn. Tối ưu hóa này được thực hiện bằng kiểm tra sau:

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

2

Nếu cả hai số nguyên bao gồm tối đa một chữ số, CPython không gọi

>>> from num_digits import get_digits
>>> x = 51090942171709440000
>>> get_digits(x)
[952369152, 337507546, 44]

6 hoặc

>>> from num_digits import get_digits
>>> x = 51090942171709440000
>>> get_digits(x)
[952369152, 337507546, 44]

7 mà chỉ cần tính toán kết quả với một thao tác duy nhất. Nếu kết quả cũng phù hợp với một chữ số, không cần tính toán nhiều hơn và Bignums được thêm vào một cách hiệu quả (hoặc trừ) như thể chúng là số nguyên bản địa.

Phép nhân

Không có thuật toán bạc bullet để nhân Bignum. Một số thuật toán được sử dụng trong thực tế vì một số hoạt động tốt hơn trên các bignums tương đối nhỏ và một số khác hoạt động tốt hơn trên các bignums lớn và cực lớn. CPYThon thực hiện hai thuật toán nhân:

Thuật toán nhân lớp cấp lớp được sử dụng theo mặc định; và
Thuật toán nhân Karatsuba được sử dụng khi cả hai số nguyên có hơn 70 chữ số.

Wikipedia tóm tắt thuật toán nhân cấp lớp như sau:

Nhân số nhân với mỗi chữ số của số nhân và sau đó thêm tất cả các kết quả được thay đổi đúng.

Việc thực hiện Bignum có một sự khác biệt quan trọng. Thay vì lưu trữ kết quả nhân với mỗi chữ số và sau đó thêm chúng lên, chúng tôi thêm các kết quả này vào đầu ra Bignum ngay khi chúng tôi tính toán chúng. GIF sau đây minh họa ý tưởng:

Tối ưu hóa này tiết kiệm cả bộ nhớ và thời gian. Cách tốt nhất để hiểu các chi tiết khác của thuật toán là xem xét việc triển khai thực tế. Đây là một của Cpython:

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

3

Lưu ý rằng khi chúng ta nhân hai chữ số 30 bit, chúng ta có thể nhận được kết quả 60 bit. Nó không phù hợp với INT 32 bit, nhưng đây không phải là vấn đề vì CPython sử dụng các chữ số 30 bit trên các nền tảng 64 bit, do đó INT 64 bit có thể được sử dụng để thực hiện tính toán. Sự tiện lợi này là lý do chính tại sao CPython không sử dụng kích thước chữ số lớn hơn.

Thuật toán nhân lớp cấp độ mất \ (o (n^2) \) thời gian khi nhân hai bignum n-chữ số n. Thuật toán nhân Karatsuba mất \ (o (n^{\ log _ {2} 3}) = o (n^{1.584 ...}) \). Cpython sử dụng cái sau khi cả hai toán hạng có hơn 70 chữ số.$O(n^2)$ time when multiplying two n-digit bignums. The Karatsuba multiplication algorithm takes $O(n^{\log _{2}3})= O(n^{1.584...})$. CPython uses the latter when both operands have more than 70 digits.

Ý tưởng về thuật toán Karatsuba dựa trên hai quan sát. Đầu tiên, quan sát rằng mỗi toán hạng có thể được chia thành hai phần: một phần bao gồm các chữ số bậc thấp và phần còn lại bao gồm các chữ số bậc cao:

$$ x = x_1 + x_2 \ lần cơ sở ^ {len (x_1)} $$

Sau đó, một phép nhân của hai bignum n chữ N có thể được thay thế bằng bốn phép nhân của các bignum nhỏ hơn. Giả sử phân tách được thực hiện để \ (len (x_1) = len (y_1) \),$len(x_1) = len(y_1)$,

$$ xy = (x_1 + x_2 \ thời gian cơ sở ^ {len )} + x_2Y_2 \ lần cơ sở ^ {2Len (x_1)} $$

Kết quả của bốn phép nhân sau đó có thể được tính toán đệ quy. Thuật toán này, tuy nhiên, cũng hoạt động cho \ (o (n^2) \). Chúng ta có thể làm cho nó nhanh hơn không có triệu chứng bằng cách sử dụng quan sát sau: Bốn phép nhân có thể được thay thế bằng ba phép nhân với chi phí của một vài bổ sung và phép trừ thêm vì$O(n^2)$. We can make it asymptotically faster using the following observation: four multiplications can be replaced with three multiplications at the cost of a few extra additions and subtractions because

$$ X_1Y_2+X_2Y_1 = (X_1+X_2) (Y_1+Y_2) - X_1Y_1 - X_2Y_2 $$

Vì vậy, chúng ta chỉ cần tính toán \ (x_1y_1 \), \ (x_2y_2 \) và \ ((x_1+x_2) (y_1+y_2) \). Nếu chúng ta phân chia từng toán hạng theo cách sao cho các bộ phận của nó có khoảng một nửa số chữ số, thì chúng ta sẽ nhận được một thuật toán hoạt động cho \ (o (n^{\ log _ {2} 3}) \). Thành công!$x_1y_1$, $x_2y_2$ and $(x_1+x_2) (y_1+y_2)$. If we split each operand in such a way so that its parts have about half as many digits, then we get an algorithm that works for $O(n^{\log _{2}3})$. Success!

Bộ phận Bignum khó thực hiện hơn một chút. Chúng tôi sẽ không thảo luận về nó ở đây, nhưng về cơ bản đó là thuật toán phân chia dài quen thuộc. Kiểm tra

>>> from num_digits import get_digits
>>> x = 51090942171709440000
>>> get_digits(x)
[952369152, 337507546, 44]

0 để xem cách phân chia Bignum và các hoạt động số học khác được thực hiện trong CPython. Các mô tả của các thuật toán được triển khai có thể được tìm thấy trong Chương 14 của Sổ tay mật mã được áp dụng của Alfred Menezes (nó miễn phí!).

Bignums của CPython so với các triển khai Bignum khác

Việc triển khai Bignums của CPython nhanh như thế nào so với các triển khai khác? Mặc dù đó không phải là nhiệm vụ dễ dàng nhất để đưa ra một bài kiểm tra hoàn toàn đại diện, chúng ta có thể có một số ý tưởng. Trò chơi điểm chuẩn có điểm chuẩn Pidigits để đo lường hiệu suất của Bignums trong các ngôn ngữ lập trình khác nhau. Điểm chuẩn yêu cầu thực hiện một thuật toán cụ thể để tạo ra các chữ số của PI. Bạn có thể tìm thấy kết quả ở đây. Một điều quan trọng cần biết về những kết quả này là các chương trình nhanh nhất sử dụng Bignums được cung cấp bởi thư viện GMP chứ không phải các bignums được cung cấp bởi ngôn ngữ. Nếu chúng tôi loại trừ các chương trình sử dụng các ràng buộc GMP, chúng tôi sẽ nhận được kết quả sau:

#	nguồn	giây
1	Haskell GHC #5 *	0.75
2	Nhà nguyện #2 *	0.76
3	Julia *	1.56
4	Đi #8	2.68
5	Phi tiêu #2	3.33
6	Python 3 #4	3.85
7	OCAML #5	4.36
8	Lisp SBCL #2	5.77
9	Node JS #4	6.15
10	Java	7.61
11	Erlang Hipe #3	7.94
12	Vw smalltalk #4	8.02
13	Vợt	11.40
14	Miễn phí pascal	14.65
15	Ruby	17.10
16	PHP	5 phút

Một số ngôn ngữ dựa vào GMP để thực hiện các bignum tích hợp. Chúng được đánh dấu bằng dấu hoa thị (*).

Kết quả cho thấy việc triển khai của Cpython có hiệu suất khá. Tuy nhiên, GMP chứng minh rằng Bignums có thể được thực hiện hiệu quả hơn. Câu hỏi tự nhiên để hỏi là: Điều gì làm cho Bignums của GMP nhanh hơn so với Bignums của Cpython? Tôi có thể nghĩ ra ba lý do chính:

Một số phần của GMP được viết bằng ngôn ngữ lắp ráp. Mã này được tối ưu hóa cao cho các kiến trúc CPU khác nhau.

GMP sử dụng kích thước chữ số lớn hơn. Nó sử dụng các chữ số 64 bit trên các nền tảng 64 bit và các chữ số 32 bit trên các nền tảng 32 bit. Do đó, GMP đại diện cho các số nguyên giống nhau với ít chữ số hơn. Do đó, các hoạt động số học được thực hiện nhanh hơn. Điều này là có thể vì lý do 1. Ví dụ, GMP có thể đọc cờ Carring hoặc sử dụng hướng dẫn

PyTypeObject PyLong_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "int",                                      /* tp_name */
    offsetof(PyLongObject, ob_digit),           /* tp_basicsize */
    sizeof(digit),                              /* tp_itemsize */
    0,                                          /* tp_dealloc */
    0,                                          /* tp_vectorcall_offset */
    0,                                          /* tp_getattr */
    0,                                          /* tp_setattr */
    0,                                          /* tp_as_async */
    long_to_decimal_string,                     /* tp_repr */
    &long_as_number,                            /* tp_as_number */
    0,                                          /* tp_as_sequence */
    0,                                          /* tp_as_mapping */
    (hashfunc)long_hash,                        /* tp_hash */
    0,                                          /* tp_call */
    0,                                          /* tp_str */
    PyObject_GenericGetAttr,                    /* tp_getattro */
    0,                                          /* tp_setattro */
    0,                                          /* tp_as_buffer */
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE |
        Py_TPFLAGS_LONG_SUBCLASS,               /* tp_flags */
    long_doc,                                   /* tp_doc */
    0,                                          /* tp_traverse */
    0,                                          /* tp_clear */
    long_richcompare,                           /* tp_richcompare */
    0,                                          /* tp_weaklistoffset */
    0,                                          /* tp_iter */
    0,                                          /* tp_iternext */
    long_methods,                               /* tp_methods */
    0,                                          /* tp_members */
    long_getset,                                /* tp_getset */
    0,                                          /* tp_base */
    0,                                          /* tp_dict */
    0,                                          /* tp_descr_get */
    0,                                          /* tp_descr_set */
    0,                                          /* tp_dictoffset */
    0,                                          /* tp_init */
    0,                                          /* tp_alloc */
    long_new,                                   /* tp_new */
    PyObject_Del,                               /* tp_free */
};

9 để thêm bằng mang theo. Nó cũng có thể nhận được kết quả 128 bit của hai số nguyên 64 bit với hướng dẫn

static PyNumberMethods long_as_number = {
    (binaryfunc)long_add,       /*nb_add*/
    (binaryfunc)long_sub,       /*nb_subtract*/
    (binaryfunc)long_mul,       /*nb_multiply*/
    long_mod,                   /*nb_remainder*/
    long_divmod,                /*nb_divmod*/
    long_pow,                   /*nb_power*/
    (unaryfunc)long_neg,        /*nb_negative*/
    long_long,                  /*tp_positive*/
    (unaryfunc)long_abs,        /*tp_absolute*/
    (inquiry)long_bool,         /*tp_bool*/
    (unaryfunc)long_invert,     /*nb_invert*/
    long_lshift,                /*nb_lshift*/
    long_rshift,                /*nb_rshift*/
    long_and,                   /*nb_and*/
    long_xor,                   /*nb_xor*/
    long_or,                    /*nb_or*/
    long_long,                  /*nb_int*/
    0,                          /*nb_reserved*/
    long_float,                 /*nb_float*/
    0,                          /* nb_inplace_add */
    0,                          /* nb_inplace_subtract */
    0,                          /* nb_inplace_multiply */
    0,                          /* nb_inplace_remainder */
    0,                          /* nb_inplace_power */
    0,                          /* nb_inplace_lshift */
    0,                          /* nb_inplace_rshift */
    0,                          /* nb_inplace_and */
    0,                          /* nb_inplace_xor */
    0,                          /* nb_inplace_or */
    long_div,                   /* nb_floor_divide */
    long_true_divide,           /* nb_true_divide */
    0,                          /* nb_inplace_floor_divide */
    0,                          /* nb_inplace_true_divide */
    long_long,                  /* nb_index */
};

0.

GMP sử dụng các thuật toán tinh vi hơn để thực hiện số học bignum. Ví dụ, thuật toán Karatsuba không phải là thuật toán nhân nhanh nhất không có triệu chứng. Và GMP thực hiện bảy thuật toán nhân khác nhau. Cái nào được sử dụng phụ thuộc vào kích thước của toán hạng.

Hiệu suất của Bignums của Cpython là đủ cho hầu hết các ứng dụng. Khi không đủ, Bignums của GMP có thể được sử dụng trong chương trình Python thông qua mô -đun

static PyNumberMethods long_as_number = {
    (binaryfunc)long_add,       /*nb_add*/
    (binaryfunc)long_sub,       /*nb_subtract*/
    (binaryfunc)long_mul,       /*nb_multiply*/
    long_mod,                   /*nb_remainder*/
    long_divmod,                /*nb_divmod*/
    long_pow,                   /*nb_power*/
    (unaryfunc)long_neg,        /*nb_negative*/
    long_long,                  /*tp_positive*/
    (unaryfunc)long_abs,        /*tp_absolute*/
    (inquiry)long_bool,         /*tp_bool*/
    (unaryfunc)long_invert,     /*nb_invert*/
    long_lshift,                /*nb_lshift*/
    long_rshift,                /*nb_rshift*/
    long_and,                   /*nb_and*/
    long_xor,                   /*nb_xor*/
    long_or,                    /*nb_or*/
    long_long,                  /*nb_int*/
    0,                          /*nb_reserved*/
    long_float,                 /*nb_float*/
    0,                          /* nb_inplace_add */
    0,                          /* nb_inplace_subtract */
    0,                          /* nb_inplace_multiply */
    0,                          /* nb_inplace_remainder */
    0,                          /* nb_inplace_power */
    0,                          /* nb_inplace_lshift */
    0,                          /* nb_inplace_rshift */
    0,                          /* nb_inplace_and */
    0,                          /* nb_inplace_xor */
    0,                          /* nb_inplace_or */
    long_div,                   /* nb_floor_divide */
    long_true_divide,           /* nb_true_divide */
    0,                          /* nb_inplace_floor_divide */
    0,                          /* nb_inplace_true_divide */
    long_long,                  /* nb_index */
};

1.

Để biết thêm ý kiến về kết quả của điểm chuẩn Pidigits, hãy xem bài viết này.

Cân nhắc sử dụng bộ nhớ

Số nguyên Python lấy một lượng bộ nhớ đáng kể. Ngay cả các số nguyên nhỏ nhất cũng có 28 byte trên nền tảng 64 bit:

Số lượng tham chiếu

static PyNumberMethods long_as_number = {
    (binaryfunc)long_add,       /*nb_add*/
    (binaryfunc)long_sub,       /*nb_subtract*/
    (binaryfunc)long_mul,       /*nb_multiply*/
    long_mod,                   /*nb_remainder*/
    long_divmod,                /*nb_divmod*/
    long_pow,                   /*nb_power*/
    (unaryfunc)long_neg,        /*nb_negative*/
    long_long,                  /*tp_positive*/
    (unaryfunc)long_abs,        /*tp_absolute*/
    (inquiry)long_bool,         /*tp_bool*/
    (unaryfunc)long_invert,     /*nb_invert*/
    long_lshift,                /*nb_lshift*/
    long_rshift,                /*nb_rshift*/
    long_and,                   /*nb_and*/
    long_xor,                   /*nb_xor*/
    long_or,                    /*nb_or*/
    long_long,                  /*nb_int*/
    0,                          /*nb_reserved*/
    long_float,                 /*nb_float*/
    0,                          /* nb_inplace_add */
    0,                          /* nb_inplace_subtract */
    0,                          /* nb_inplace_multiply */
    0,                          /* nb_inplace_remainder */
    0,                          /* nb_inplace_power */
    0,                          /* nb_inplace_lshift */
    0,                          /* nb_inplace_rshift */
    0,                          /* nb_inplace_and */
    0,                          /* nb_inplace_xor */
    0,                          /* nb_inplace_or */
    long_div,                   /* nb_floor_divide */
    long_true_divide,           /* nb_true_divide */
    0,                          /* nb_inplace_floor_divide */
    0,                          /* nb_inplace_true_divide */
    long_long,                  /* nb_index */
};

2: 8 byte

Một loại

static PyNumberMethods long_as_number = {
    (binaryfunc)long_add,       /*nb_add*/
    (binaryfunc)long_sub,       /*nb_subtract*/
    (binaryfunc)long_mul,       /*nb_multiply*/
    long_mod,                   /*nb_remainder*/
    long_divmod,                /*nb_divmod*/
    long_pow,                   /*nb_power*/
    (unaryfunc)long_neg,        /*nb_negative*/
    long_long,                  /*tp_positive*/
    (unaryfunc)long_abs,        /*tp_absolute*/
    (inquiry)long_bool,         /*tp_bool*/
    (unaryfunc)long_invert,     /*nb_invert*/
    long_lshift,                /*nb_lshift*/
    long_rshift,                /*nb_rshift*/
    long_and,                   /*nb_and*/
    long_xor,                   /*nb_xor*/
    long_or,                    /*nb_or*/
    long_long,                  /*nb_int*/
    0,                          /*nb_reserved*/
    long_float,                 /*nb_float*/
    0,                          /* nb_inplace_add */
    0,                          /* nb_inplace_subtract */
    0,                          /* nb_inplace_multiply */
    0,                          /* nb_inplace_remainder */
    0,                          /* nb_inplace_power */
    0,                          /* nb_inplace_lshift */
    0,                          /* nb_inplace_rshift */
    0,                          /* nb_inplace_and */
    0,                          /* nb_inplace_xor */
    0,                          /* nb_inplace_or */
    long_div,                   /* nb_floor_divide */
    long_true_divide,           /* nb_true_divide */
    0,                          /* nb_inplace_floor_divide */
    0,                          /* nb_inplace_true_divide */
    long_long,                  /* nb_index */
};

3: 8 byte

Kích thước của một đối tượng

$ python -q
>>> base = 2**30
>>> -(3 * base**0 + 5 * base**1 + 1 * base**2)
-1152921509975556099

5: 8 byte

________ 27: & nbsp; 4 byte.

Phân bổ một danh sách một triệu số nguyên đòi hỏi phải tự phân bổ số nguyên cộng với một triệu tham chiếu cho họ, tổng cộng khoảng 35 megabyte. So sánh nó với 4 megabyte cần thiết để phân bổ một mảng gồm một triệu ints 32 bit. Vì vậy, đôi khi thật hợp lý khi sử dụng mô -đun

static PyNumberMethods long_as_number = {
    (binaryfunc)long_add,       /*nb_add*/
    (binaryfunc)long_sub,       /*nb_subtract*/
    (binaryfunc)long_mul,       /*nb_multiply*/
    long_mod,                   /*nb_remainder*/
    long_divmod,                /*nb_divmod*/
    long_pow,                   /*nb_power*/
    (unaryfunc)long_neg,        /*nb_negative*/
    long_long,                  /*tp_positive*/
    (unaryfunc)long_abs,        /*tp_absolute*/
    (inquiry)long_bool,         /*tp_bool*/
    (unaryfunc)long_invert,     /*nb_invert*/
    long_lshift,                /*nb_lshift*/
    long_rshift,                /*nb_rshift*/
    long_and,                   /*nb_and*/
    long_xor,                   /*nb_xor*/
    long_or,                    /*nb_or*/
    long_long,                  /*nb_int*/
    0,                          /*nb_reserved*/
    long_float,                 /*nb_float*/
    0,                          /* nb_inplace_add */
    0,                          /* nb_inplace_subtract */
    0,                          /* nb_inplace_multiply */
    0,                          /* nb_inplace_remainder */
    0,                          /* nb_inplace_power */
    0,                          /* nb_inplace_lshift */
    0,                          /* nb_inplace_rshift */
    0,                          /* nb_inplace_and */
    0,                          /* nb_inplace_xor */
    0,                          /* nb_inplace_or */
    long_div,                   /* nb_floor_divide */
    long_true_divide,           /* nb_true_divide */
    0,                          /* nb_inplace_floor_divide */
    0,                          /* nb_inplace_true_divide */
    long_long,                  /* nb_index */
};

6 hoặc

static PyNumberMethods long_as_number = {
    (binaryfunc)long_add,       /*nb_add*/
    (binaryfunc)long_sub,       /*nb_subtract*/
    (binaryfunc)long_mul,       /*nb_multiply*/
    long_mod,                   /*nb_remainder*/
    long_divmod,                /*nb_divmod*/
    long_pow,                   /*nb_power*/
    (unaryfunc)long_neg,        /*nb_negative*/
    long_long,                  /*tp_positive*/
    (unaryfunc)long_abs,        /*tp_absolute*/
    (inquiry)long_bool,         /*tp_bool*/
    (unaryfunc)long_invert,     /*nb_invert*/
    long_lshift,                /*nb_lshift*/
    long_rshift,                /*nb_rshift*/
    long_and,                   /*nb_and*/
    long_xor,                   /*nb_xor*/
    long_or,                    /*nb_or*/
    long_long,                  /*nb_int*/
    0,                          /*nb_reserved*/
    long_float,                 /*nb_float*/
    0,                          /* nb_inplace_add */
    0,                          /* nb_inplace_subtract */
    0,                          /* nb_inplace_multiply */
    0,                          /* nb_inplace_remainder */
    0,                          /* nb_inplace_power */
    0,                          /* nb_inplace_lshift */
    0,                          /* nb_inplace_rshift */
    0,                          /* nb_inplace_and */
    0,                          /* nb_inplace_xor */
    0,                          /* nb_inplace_or */
    long_div,                   /* nb_floor_divide */
    long_true_divide,           /* nb_true_divide */
    0,                          /* nb_inplace_floor_divide */
    0,                          /* nb_inplace_true_divide */
    long_long,                  /* nb_index */
};

7 để lưu trữ một lượng lớn dữ liệu đồng nhất.

Chúng tôi đã nói trước đó rằng Cpython tạo ra một đối tượng số nguyên mới trên mọi hoạt động số học. May mắn thay, nó sử dụng tối ưu hóa để phân bổ số nguyên nhỏ chỉ một lần trong suốt cuộc đời của người phiên dịch. Các số nguyên trong phạm vi [-5, 256] được phân bổ khi CPython bắt đầu. Sau đó, khi CPython cần tạo một đối tượng số nguyên mới, trước tiên, nó sẽ kiểm tra xem giá trị số nguyên có nằm trong phạm vi [-5, 256] và, nếu nó nằm trong phạm vi, sẽ trả về đối tượng được phân chia. Việc loại bỏ phân bổ bộ nhớ thêm giúp tiết kiệm cả bộ nhớ và thời gian.

Phạm vi [-5, 256] được chọn vì các giá trị trong phạm vi này được sử dụng rộng rãi trên khắp Cpython và thư viện tiêu chuẩn Python. Để biết thêm chi tiết về sự lựa chọn, hãy xem bài viết này.

Sự kết luận

Thiết kế của các loại tích hợp chắc chắn đã góp phần vào thành công của Python. Các số nguyên Python phục vụ như một ví dụ về việc thực hiện Bignum có thể truy cập khá hiệu quả. Chúng tôi đã sử dụng thực tế này ngày hôm nay để tìm hiểu cả về số nguyên Python và về bignums. Lần tới, chúng tôi sẽ tiếp tục nghiên cứu các loại Python tích hợp. Hãy theo dõi để tìm hiểu về cách các chuỗi Python hoạt động.

Nếu bạn có bất kỳ câu hỏi, nhận xét hoặc đề xuất nào, vui lòng liên hệ với tôi tại

INT được đại diện như thế nào trong Python?

Giá trị số nguyên được biểu thị bằng hai biến khác: ob_digit và ob_size.Python sử dụng mảng ob_digit để lưu trữ từng chữ số của số một cách riêng biệt ở các vị trí chỉ mục khác nhau.Ngoài ra, biến OB_SIZE được sử dụng để lưu trữ hai giá trị.ob_digit and ob_size . Python uses the ob_digit array to store each digit of the number separately in different index locations. Additionally, the ob_size variable is used to store two values.

INT làm tròn hay xuống trong Python?

Trước tiên, bạn phải đánh giá xem số có bằng số nguyên của nó không, luôn làm tròn.Nếu kết quả là đúng, bạn trả về số, nếu không, hãy trả về số nguyên (số) + 1.always rounds down. If the result is True, you return the number, if is not, return the integer(number) + 1.

Int () làm gì trong Python cho số thập phân?

Hàm python int () trả về một số nguyên từ một đối tượng đã cho hoặc chuyển đổi một số trong một cơ sở nhất định thành một số thập phân.converts a number in a given base to a decimal.

Số int trong Python là gì?

Int, hoặc số nguyên, là một số nguyên, dương hoặc âm, không có số thập phân, có độ dài không giới hạn.a whole number, positive or negative, without decimals, of unlimited length.

programming python int() python Float Python Python to int Python bignum Python integer representation

Hướng dẫn how do ints work in python? - ints hoạt động như thế nào trong python?

Tại sao số nguyên python lại thú vị

Đại diện Bignum

Số học Bignum

Cộng và trừ)

Phép nhân

Bignums của CPython so với các triển khai Bignum khác

Cân nhắc sử dụng bộ nhớ

Sự kết luận

INT được đại diện như thế nào trong Python?

INT làm tròn hay xuống trong Python?

Int () làm gì trong Python cho số thập phân?

Số int trong Python là gì?

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội