🤰🏻 🙎 🧗🏽 पायथन में बहुत लंबे पूर्णांक प्रकार कैसे लागू किए जाते हैं? 👱🏿 👩🏾‍🌾 🤹

लेख का अनुवाद विशेष रूप से पायथन डेवलपर पाठ्यक्रम के छात्रों के लिए तैयार किया गया था ।

जब आप सी जैसी निम्न-स्तरीय भाषा में लिखते हैं, तो आप अपने पूर्णांकों के लिए सही डेटा प्रकार और क्वालीफायर चुनने के बारे में चिंतित होते हैं, प्रत्येक चरण पर आप विश्लेषण करते हैं कि क्या यह बस इसे उपयोग करने के लिए पर्याप्त होगा intया आपको इसे जोड़ने की आवश्यकता है longया नहीं long double। हालाँकि, जब पायथन में कोड लिखते हैं, तो आपको इन "मामूली" चीजों के बारे में चिंता करने की ज़रूरत नहीं है, क्योंकि पायथन integerकिसी भी आकार प्रकार की संख्याओं के साथ काम कर सकता है ।

सी में, यदि आप अंतर्निहित फ़ंक्शन का उपयोग करके 2 ^{20000 की} गणना करने का प्रयास करते हैं, तो आपको powlआउटपुट मिलेगा inf।

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

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

$ ./a.out
inf

लेकिन पायथन में, यह पहले से आसान बनाना आसान है:

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

यह हुड के नीचे होना चाहिए कि पायथन बहुत सुंदर कुछ कर रहा है, और आज हम पता लगाएंगे कि यह मनमाने आकार के पूर्णांक के साथ क्या काम करता है!

प्रस्तुति और परिभाषा

Integer पायथन में, यह एक सी संरचना है जिसे निम्नानुसार परिभाषित किया गया है:

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

PyObject_VAR_HEADएक मैक्रो है, इसका विस्तार होता है PyVarObject, जिसमें निम्न संरचना होती है:

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

अन्य प्रकार PyObject_VAR_HEAD:

PyBytesObject
PyTupleObject
PyListObject

इसका मतलब है कि एक पूर्णांक, जैसे कि एक ट्यूल या सूची, की एक चर लंबाई है, और यह समझने के लिए पहला कदम है कि पायथन विशाल संख्याओं के साथ कैसे काम कर सकता है। एक बार विस्तारित होने के बाद, मैक्रो _longobjectको इस प्रकार माना जा सकता है:

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

संरचना में PyObjectकुछ मेटा फ़ील्ड हैं जो संदर्भ गिनती (कचरा संग्रह) के लिए उपयोग किए जाते हैं, लेकिन इस बारे में बात करने के लिए, हमें एक अलग लेख की आवश्यकता है। जिस क्षेत्र पर हम इस ob_digitऔर थोड़ा ध्यान केंद्रित करेंगे ob_size।

डिक्रिप्शन `ob_digit`

ob_digitप्रकार की इकाई लंबाई का एक सांख्यिकीय रूप से आवंटित सरणी है digit (typedef uint32_t)। चूंकि यह एक सरणी है, यह ob_digitमुख्य रूप से एक संख्या के लिए एक संकेतक है, और इसलिए, यदि आवश्यक हो, तो इसे मॉलोक फ़ंक्शन का उपयोग करके किसी भी लंबाई में बढ़ाया जा सकता है। इस तरह से अजगर बहुत लंबी संख्या का प्रतिनिधित्व और प्रक्रिया कर सकता है।

आमतौर पर, सी जैसी निम्न-स्तरीय भाषाओं में, पूर्णांकों की सटीकता 64 बिट्स तक सीमित होती है, हालांकि पायथन मनमाने ढंग से परिशुद्धता के पूर्णांकों का समर्थन करता है । पायथन 3 के साथ शुरू, सभी नंबर फॉर्म में प्रस्तुत किए bignumजाते हैं और केवल उपलब्ध सिस्टम मेमोरी द्वारा सीमित होते हैं।

डिक्रिप्शन `ob_size`

ob_sizeमें मदों की संख्या संग्रहीत करता है ob_digit। पायथन ओवरराइड करता है और फिर ob_sizeसरणी में मेमोरी आवंटित करने की दक्षता बढ़ाने के लिए सरणी में निहित तत्वों की वास्तविक संख्या निर्धारित करने के लिए मूल्य का उपयोग करता है ob_digit।

भंडारण

पूर्णांक संख्याओं को संग्रहीत करने का सबसे भोली तरीका सरणी के एक तत्व में एक दशमलव अंक को संग्रहीत करना है, फिर संचालन, जैसे कि जोड़ और घटाव, प्राथमिक विद्यालय से गणित के नियमों के अनुसार किया जा सकता है।

इस दृष्टिकोण के साथ, 5238 नंबर इस तरह से सहेजा जाएगा:

यह दृष्टिकोण अक्षम है, क्योंकि हम दशमलव अंक को संग्रहीत करने के लिए 32-बिट अंक (uint32_t) तक का उपयोग करेंगे, जो वास्तव में, 0 से 9 तक होता है और केवल 4 बिट्स के साथ आसानी से प्रतिनिधित्व किया जा सकता है। जब अजगर के रूप में बहुमुखी के रूप में कुछ लिखने के लिए, कर्नेल डेवलपर और भी अधिक आविष्कारशील होना चाहिए।

तो, क्या हम बेहतर कर सकते हैं? बेशक, अन्यथा मैं इस लेख को पोस्ट नहीं करता। आइए इस बात पर करीब से नज़र डालें कि पायथन अतिरिक्त-लंबे पूर्णांक को कैसे संग्रहीत करता है।

अजगर का रास्ता

सरणी के प्रत्येक तत्व में केवल एक दशमलव अंक को संग्रहीत करने के बजाय ob_digit, पायथन संख्या प्रणाली में 10 के आधार के साथ संख्याओं को 2 ^{30 के} आधार के साथ एक प्रणाली में संख्याओं में परिवर्तित करता है और प्रत्येक तत्व को एक संख्या के रूप में कॉल करता है, जिसका मान 0 से 2 ³⁰ - 1 तक होता है।

हेक्साडेसिमल संख्या प्रणाली में, बेस 16 ~ 2 ^{4 का} अर्थ है कि हेक्साडेसिमल संख्या के प्रत्येक "अंक" दशमलव संख्या प्रणाली में 0 से 15 तक होता है। पायथन में, इसी तरह, 2 ^{30 के} आधार के साथ एक "संख्या" , जिसका अर्थ है कि संख्या दशमलव में 0 से 2 ³⁰ - 1 = 1073741823 तक भिन्न होगी ।

इस तरह, पायथन कुशलतापूर्वक प्रति अंक 32 बिट्स के आवंटित स्थान का कुशलतापूर्वक उपयोग करता है, संसाधनों का संरक्षण करता है, और अभी भी प्राथमिक विद्यालय के गणित स्तर पर जोड़ने और घटाने जैसे सरल संचालन करता है।

मंच के आधार पर, पायथन 32-बिट अहस्ताक्षरित पूर्णांक सरणियों या 16-बिट अहस्ताक्षरित पूर्णांक सरणियों का उपयोग 15-बिट अंकों के साथ करता है। बाद में चर्चा किए जाने वाले ऑपरेशनों को करने के लिए, आपको केवल कुछ बिट्स की आवश्यकता होगी।

उदाहरण: 1152921504606846976

जैसा कि उल्लेख किया गया है, पायथन के लिए, संख्याओं को आधार 2 ^{30 प्रणाली} में दर्शाया गया है, अर्थात यदि आप 1152921504606846976 को 2 ³⁰ आधार के साथ आधार संख्या में परिवर्तित करते हैं , तो आप 100.

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

चूंकि ob_digitकम से कम महत्वपूर्ण अंक पहले संग्रहीत किया जाता है, इसे 001 को तीन अंकों के रूप में सहेजा जाता है। इस मान के लिए

संरचना में _longobjectशामिल होंगे:

ob_size 3 की तरह
ob_digit जैसे [0, 0, 1]

मैंने एक डेमो आरईपीएल बनाया जो दिखाएगा कि पायथन अपने अंदर एक पूर्णांक कैसे संग्रहीत करता है, और संरचना सदस्यों को भी संदर्भित करता है जैसे कि ob_size, ob_refcountआदि।

पूर्णांक लंबे ऑपरेशन

अब जब हमारे पास यह स्पष्ट विचार है कि पायथन मनमानी परिशुद्धता के पूर्णकों को कैसे लागू करता है, तो यह समझने का समय है कि उनके साथ विभिन्न गणितीय संचालन कैसे किए जाते हैं।

इसके अलावा

इंटेगर को "संख्याओं में" संग्रहीत किया जाता है, जिसका अर्थ है कि इसके अलावा प्राथमिक विद्यालय में भी उतना ही सरल है, और पायथन स्रोत कोड हमें दिखाता है कि यह कैसे लागू किया जाता है। x_addफ़ाइल में नाम के साथ एक फ़ंक्शन longobject.cदो नंबर जोड़ता है।

...
    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;
...

ऊपर कोड स्निपेट एक फ़ंक्शन से लिया गया है x_add। जैसा कि आप देख सकते हैं, यह संख्याओं के आधार पर संख्या में पुनरावृत्ति करता है और संख्याओं को जोड़ता है, परिणाम की गणना करता है और हाइफ़नेशन जोड़ता है।

यह अधिक दिलचस्प हो जाता है जब जोड़ का परिणाम एक नकारात्मक संख्या है। चिन्ह ob_sizeएक पूर्णांक चिन्ह है, अर्थात यदि आपके पास ऋणात्मक संख्या है, तो वह ऋणात्मक ob_sizeहोगा। मान ob_sizeमोडुलो अंकों की संख्या निर्धारित करेगा ob_digit।

घटाव

जैसे जोड़ घटता है, वैसे ही घटाव भी होता है। x_subफ़ाइल में नाम वाला एक फ़ंक्शन longobject.cदूसरे से एक नंबर घटाता है।

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

ऊपर कोड स्निपेट एक फ़ंक्शन से लिया गया है x_sub। इसमें, आप देखते हैं कि संख्याओं की गणना कैसे होती है और घटाव किया जाता है, परिणाम की गणना की जाती है और स्थानांतरण वितरित किया जाता है। वास्तव में, यह इसके अतिरिक्त बहुत समान है।

गुणन

और फिर, गुणा को उसी भोले तरीके से लागू किया जाएगा जो हमने प्राथमिक विद्यालय में गणित के पाठों से सीखा था, लेकिन यह बहुत कुशल नहीं है। दक्षता बनाए रखने के लिए, पायथन , करतसुबा एल्गोरिथ्म को लागू करता है , जो ओ (एन ^लॉग₂³ ) सरल चरणों में दो एन-अंकों की संख्या को गुणा करता है ।

एल्गोरिथ्म सरल नहीं है और इसका कार्यान्वयन इस लेख के दायरे से परे है, लेकिन आप इसके कार्यान्वयन को कार्यों k_mul और k_lopsided_mulफ़ाइल में पा सकते हैं longobject.c।

डिवीजन और अन्य संचालन

पूर्णांक पर सभी ऑपरेशन फ़ाइल में परिभाषित किए गए हैं longobject.c, वे प्रत्येक के काम को खोजने और ट्रेस करने के लिए बहुत सरल हैं। ध्यान दें: उनमें से प्रत्येक के काम की एक विस्तृत समझ में समय लगेगा, इसलिए पॉपकॉर्न के साथ पूर्व-स्टॉक करें ।

अजगर preallocates एक से -5 256 से लेकर स्मृति में पूर्णांकों की छोटी संख्या इस आवंटन आरंभीकरण के दौरान होता है, और तब से हम पूर्णांकों (अचल स्थिति) बदल नहीं सकते, इन पूर्व आवंटित संख्या सिंगलटन कर रहे हैं और के बजाय सीधे आवंटित किया जा रहा है दर्शाया जाता है। इसका मतलब यह है कि हर बार जब हम एक छोटी संख्या का उपयोग करते हैं / बनाते हैं, तो इसे बेचने के बजाय पहले से आवंटित संख्या का संदर्भ देता है।

इस तरह के अनुकूलन को मैक्रो IS_SMALL_INTऔर फ़ंक्शन get_small_intसी में पता लगाया जा सकता है longobject.c। इसलिए पायथन आमतौर पर उपयोग किए जाने वाले पूर्णांक संख्याओं की गणना करने में बहुत अधिक स्थान और समय बचाता है।

पायथन इंटरनैल्स सीरीज़ का यह दूसरा लेख है। पहला लेख इस बारे में था कि मैंने इसे बनाने के लिए पायथन के अपने संस्करण को कैसे बदल दियाअस्पष्ट । यह पायथन स्रोत कोड को समझने में पहला कदम उठाने में आपकी मदद करेगा और पायथन कर्नेल डेवलपर बनने का मार्ग जारी रखेगा।

यदि आप अधिक समान लेख देखना चाहते हैं, तो मेरे न्यूज़लेटर की सदस्यता लें और उन्हें सीधे अपने इनबॉक्स में प्राप्त करें। मैं हर शुक्रवार को इंजीनियरिंग, सिस्टम इंजीनियरिंग और प्रोग्रामिंग के बारे में थोड़ा लिखता हूं। ईमेल पर मुझे @arpit_bhayani । आप मेरे पिछले लेख @ arpitbhayani.me / ब्लॉग पर पा सकते हैं ।

बस इतना ही। कोर्स पर मिलते हैं !

पायथन में बहुत लंबे पूर्णांक प्रकार कैसे लागू किए जाते हैं?