Phần phụ trợ @Unacademy • Dữ liệu @Amazon • Nền tảng @Practo. Viết về Ngôn ngữ bên trong và Toán học trong Khoa học Máy tính
Làm thế nào python thực hiện các số nguyên siêu dài?Xuất bản ngày 10 tháng 1 năm 2020
Khi bạn viết mã bằng ngôn ngữ cấp thấp như C, bạn lo lắng về việc chọn đúng kiểu dữ liệu và bộ định tính cho số nguyên của mình; . Nhưng khi code trong python, bạn không cần lo lắng về những thứ "vặt vãnh" này vì python hỗ trợ các số nguyên có kích thước tùy ý
Trong C, khi bạn cố gắng tính toán 2²⁰⁰⁰⁰ bằng cách sử dụng hàm
>>> 2 ** 20000
39802768403379665923543072061912024537047727804924259387134 ...
...
.. 6021 digits long ...
...
6309376
>>> 2 ** 20000
39802768403379665923543072061912024537047727804924259387134 ...
...
.. 6021 digits long ...
...
6309376
#include
#include
int main[void] {
printf["%Lf\n", powl[2, 20000]];
return 0;
}
$ ./a.out
inf
Nhưng đối với trăn, đó là một miếng bánh 🎂
>>> 2 ** 20000
39802768403379665923543072061912024537047727804924259387134 ...
...
.. 6021 digits long ...
...
6309376
Python phải làm một cái gì đó đẹp đẽ bên trong để hỗ trợ các số nguyên có kích thước tùy ý và hôm nay chúng ta tìm hiểu những gì nằm dưới mui xe
Biểu diễn và định nghĩaMột số nguyên trong Python là một cấu trúc C được định nghĩa như sau
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
>>> 2 ** 20000
39802768403379665923543072061912024537047727804924259387134 ...
...
.. 6021 digits long ...
...
6309376
>>> 2 ** 20000
39802768403379665923543072061912024537047727804924259387134 ...
...
.. 6021 digits long ...
...
6309376
typedef struct {
PyObject ob_base;
Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;
Các loại khác có
>>> 2 ** 20000
39802768403379665923543072061912024537047727804924259387134 ...
...
.. 6021 digits long ...
...
6309376
5>>> 2 ** 20000 39802768403379665923543072061912024537047727804924259387134 ... ... .. 6021 digits long ... ... 6309376
6>>> 2 ** 20000 39802768403379665923543072061912024537047727804924259387134 ... ... .. 6021 digits long ... ... 6309376
7>>> 2 ** 20000 39802768403379665923543072061912024537047727804924259387134 ... ... .. 6021 digits long ... ... 6309376
Điều này chỉ ra rằng một số nguyên, giống như
>>> 2 ** 20000
39802768403379665923543072061912024537047727804924259387134 ...
...
.. 6021 digits long ...
...
6309376
>>> 2 ** 20000
39802768403379665923543072061912024537047727804924259387134 ...
...
.. 6021 digits long ...
...
6309376
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
>>> 2 ** 20000
39802768403379665923543072061912024537047727804924259387134 ...
...
.. 6021 digits long ...
...
6309376
Đây là một số trường meta trong cấu trúc
1, được sử dụng để đếm tham chiếu [thu gom rác], nhưng chúng tôi sẽ yêu cầu một bài viết riêng. Lĩnh vực mà chúng tôi sẽ tập trung vào làstruct _longobject { PyObject_VAR_HEAD digit ob_digit[1]; };2 và ở một mức độ nào đó làstruct _longobject { PyObject_VAR_HEAD digit ob_digit[1]; };3struct _longobject { PyObject_VAR_HEAD digit ob_digit[1]; };
Giải mã struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
2
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
typedef struct {
PyObject ob_base;
Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
Nói chung, trong các ngôn ngữ cấp thấp như C, độ chính xác của số nguyên được giới hạn ở 64-bit, nhưng Python thực hiện các số nguyên có độ chính xác tùy ý. Vì Python 3, tất cả các số nguyên được biểu diễn dưới dạng bignum và chúng chỉ bị giới hạn bởi bộ nhớ khả dụng của hệ thống máy chủ
Giải mã struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
3
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
Một cách ngây thơ để lưu trữ một chữ số nguyên khôn ngoan là lưu trữ một chữ số thập phân trong một mục của mảng và sau đó các phép toán như cộng và trừ có thể được thực hiện giống như toán ở trường phổ thông
Với phương pháp này, một số
typedef struct {
PyObject ob_base;
Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;
Cách tiếp cận này không hiệu quả vì chúng ta sẽ sử dụng tới 32 bit chữ số [
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
Vì vậy, chúng ta có thể làm tốt hơn? . Hãy đi sâu vào cách python lưu trữ một số nguyên siêu dài
con đường Pythonic
Thay vì chỉ lưu trữ một chữ số thập phân trong mỗi mục của mảng
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
Trong hệ thống số thập lục phân, cơ số là 16 ~ 2⁴ điều này có nghĩa là mỗi "chữ số" của một số thập lục phân nằm trong khoảng từ 0 đến 15 của hệ thống thập phân. Tương tự như vậy đối với python, "chữ số" nằm trong cơ số 2³⁰, có nghĩa là nó sẽ nằm trong khoảng từ 0 đến 2³⁰ - 1 = 1073741823 của hệ thập phân
Bằng cách này, python sử dụng hiệu quả gần như toàn bộ không gian được phân bổ là 32 bit cho mỗi chữ số và giữ cho nó luôn linh hoạt và vẫn thực hiện các phép toán như cộng và trừ như toán học ở trường phổ thông
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. Nó yêu cầu một vài bit để thực hiện các thao tác sẽ được thảo luận trong một số bài viết trong tương lai
Thí dụ. 1152921504606846976
Như đã đề cập, đối với Python, một "chữ số" là cơ số 2³⁰ do đó nếu bạn chuyển đổi
>>> 2 ** 20000
39802768403379665923543072061912024537047727804924259387134 ...
...
.. 6021 digits long ...
...
6309376
>>> 2 ** 20000
39802768403379665923543072061912024537047727804924259387134 ...
...
.. 6021 digits long ...
...
6309376
1152921504606846976 = 0 * [2³⁰]⁰ + 0 * [2³⁰]¹ + 1 * [2³⁰]²
Cấu trúc
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
3 nhưstruct _longobject { PyObject_VAR_HEAD digit ob_digit[1]; };
55>>> 2 ** 20000 39802768403379665923543072061912024537047727804924259387134 ... ... .. 6021 digits long ... ... 6309376
2 nhưstruct _longobject { PyObject_VAR_HEAD digit ob_digit[1]; };
57>>> 2 ** 20000 39802768403379665923543072061912024537047727804924259387134 ... ... .. 6021 digits long ... ... 6309376
Tôi đã tạo một REPL demo sẽ xuất ra cách python lưu trữ các số nguyên bên trong và cũng có tham chiếu đến các thành viên cấu trúc như
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
>>> 2 ** 20000
39802768403379665923543072061912024537047727804924259387134 ...
...
.. 6021 digits long ...
...
6309376
Bây giờ chúng ta đã có một ý tưởng hợp lý về cách python hỗ trợ và triển khai các số nguyên chính xác tùy ý, đã đến lúc hiểu các phép toán khác nhau xảy ra như thế nào trên chúng
Phép cộng
Các số nguyên được duy trì "khôn ngoan bằng chữ số", điều này có nghĩa là phép cộng đơn giản như những gì chúng ta đã học ở trường phổ thông và mã nguồn của python cho chúng ta thấy rằng đây chính xác là cách nó được triển khai. Hàm có tên x_add trong tệp longobject. c thực hiện phép cộng hai số
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
Đoạn mã ở trên được lấy từ hàm
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
Mọi thứ trở nên thú vị khi kết quả của phép cộng là một số âm. Dấu của
3 là dấu của số nguyên, có nghĩa là nếu bạn có số âm thìstruct _longobject { PyObject_VAR_HEAD digit ob_digit[1]; };3 sẽ âm. Giá trị tuyệt đối củastruct _longobject { PyObject_VAR_HEAD digit ob_digit[1]; };3 sẽ xác định số chữ số trongstruct _longobject { PyObject_VAR_HEAD digit ob_digit[1]; };2struct _longobject { PyObject_VAR_HEAD digit ob_digit[1]; };
phép trừ
Tương tự như cách thực hiện phép cộng, phép trừ cũng xảy ra theo kiểu chữ số. Hàm có tên x_sub trong tệp longobject. c thực hiện phép trừ hai số
>>> 2 ** 20000
39802768403379665923543072061912024537047727804924259387134 ...
...
.. 6021 digits long ...
...
6309376
Đoạn mã trên được lấy từ hàm
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
Phép nhân
Một lần nữa, một cách ngây thơ để thực hiện phép nhân sẽ là những gì chúng ta đã học trong môn toán ở trường tiểu học nhưng nó sẽ không hiệu quả lắm. Python, để giữ cho mọi thứ hiệu quả, thực hiện thuật toán Karatsuba nhân hai số có n chữ số trong các bước cơ bản O [ nˡᵒᵍ³ ]
Thuật toán hơi phức tạp nằm ngoài phạm vi của bài viết này nhưng bạn có thể tìm thấy cách triển khai nó trong các hàm k_mul và
k_lopside_mul trong tệp longobject. c.
Bộ phận và các hoạt động khác
Tất cả các thao tác trên số nguyên được định nghĩa trong tệp longobject. c và rất đơn giản để xác định vị trí và theo dõi từng cái. Cảnh báo. sẽ mất một chút thời gian để hiểu chi tiết từng thứ, vì vậy hãy lấy một ít bỏng ngô trước khi bạn bắt đầu đọc lướt
Tối ưu hóa các số nguyên thường được sử dụngPython phân bổ trước các số nguyên nhỏ trong phạm vi từ -5 đến 256. Việc phân bổ này xảy ra trong quá trình khởi tạo và vì chúng tôi không thể cập nhật số nguyên [không thay đổi] nên các số nguyên được phân bổ trước này là các số đơn lẻ và được tham chiếu trực tiếp thay vì phân bổ lại. Điều này có nghĩa là mỗi khi chúng ta sử dụng/tạo một số nguyên nhỏ, python thay vì phân bổ lại chỉ trả về tham chiếu của số nguyên đã phân bổ trước
Tối ưu hóa này có thể được theo dõi trong macro
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
Đây là bài viết thứ hai trong loạt bài Python Internals. Bài viết đầu tiên là Cách tôi thay đổi Python của mình và làm cho nó trở nên đáng ngờ và nó giúp bạn thực hiện những bước đầu tiên trong mã nguồn của Python và mở đường cho bạn trở thành Nhà phát triển lõi Python
Bài viết này ban đầu được xuất bản trên blog của tôi - Làm thế nào python thực hiện các số nguyên siêu dài?
Nếu bạn muốn đọc thêm các bài viết như thế này, hãy đăng ký nhận bản tin của tôi và nhận bài đăng được gửi trực tiếp vào hộp thư đến của bạn. Tôi viết về Kỹ thuật, Thiết kế hệ thống và một chút về lập trình vào thứ Sáu hàng tuần. Hãy hét lên cho tôi @arpit_bhayani. Bạn có thể tìm thấy các bài viết trước của tôi @arpitbhayani. tôi/blog
Python Lập trình nội bộ Python
Bài báo cáo
Thưởng thức bài viết này?
7
Chia sẻ
Arpit Bhayani
Phần phụ trợ @Unacademy • Dữ liệu @Amazon • Nền tảng @Practo. Viết về Ngôn ngữ bên trong và Toán học trong Khoa học Máy tính
Tôi là một lập trình viên đam mê, đam mê viết mã, thiết kế, khởi nghiệp và công nghệ. Hiện tại tôi đang làm việc tại Amazon với vị trí Kỹ sư phát triển phần mềm 2. Trước Amazon, tôi đang làm việc cho một công ty khởi nghiệp về chăm sóc sức khỏe tên là Practo, nơi tôi độc thân
Làm theo
Khám phá và đọc thêm các bài viết từ Arpit Bhayani
bắt đầu
Thưởng thức bài viết này?
Để lại một lượt thích và bình luận cho Arpit
7
Gửi đi
Abhishek Inamdar
9 tháng trước
Bài viết tuyệt vời Arpit, nhưng để chuyển đổi 1152921504606846976 thành cơ số 2^30, chúng ta cần thực hiện phép toán số học và một lần nữa, chúng ta cần lưu trữ 1152921504606846976 phải không? . Làm thế nào python giải quyết điều đó? . Thanks
Hồi đáp
BanglaVashi
3 tháng trước
Này, tôi cũng đang nghĩ như vậy và tôi rất vui vì mình không đơn độc trong việc này.
Làm ơn, đừng quên chia sẻ với tôi nếu bạn tìm thấy bất kỳ giải pháp nào liên quan đến vấn đề này.
Lưu ý. Tôi đã cố gắng tìm kiếm hàm ###builtin int trong mã nguồn python.
int chuyển đổi một chuỗi cơ số 10 bình thường thành số nguyên [trong một nghĩa là số nguyên dài của cơ số 2**30]
Vì vậy, tôi nghĩ mình có thể .
Nhưng tôi không thể tìm thấy cách triển khai hàm int [đã thử trong Python/bltinmodule. c
Vì vậy, nếu bạn tìm thấy bất kỳ bài viết hoặc tài liệu tham khảo nào liên quan đến vấn đề này, tôi rất mong bạn chia sẻ PLZ
Hồi đáp
Abhishek Govekar
3 năm trước
thật tuyệt
2
Hồi đáp
NimrodF
3 năm trước
Ồ - thật hấp dẫn. Bài báo tuyệt vời. Viết rất mạch lạc.
Bạn có thể giải thích thêm về mục đích của hai bit phụ trong mỗi chữ số không?
1
Hồi đáp
Arpit Bhayani
3 năm trước
Cảm ơn vì tất cả những lời tốt đẹp. Tôi đang định viết về cách python sử dụng hai bit bổ sung và cách nó phù hợp với tất cả các phép toán