👰🏼 👨🏾‍🎤 👸🏾 C ++ में लंबी अंकगणित का कार्यान्वयन 👩🏾‍🔧 🤰🏼 🛁

अधिकांश आधुनिक भाषाओं में, प्रोग्रामर को अब उन संख्याओं के बारे में चिंता करने की आवश्यकता नहीं है जो प्रोसेसर सीधे हेरफेर नहीं कर सकते हैं। कहीं, पाइथन या हास्केल की तरह, लंबे पूर्णांक प्रकारों के लिए समर्थन भाषा के मूल में बनाया गया है, कहीं, जावा या सी # में, इसे अलग-अलग वर्गों के रूप में लागू किया गया है। लेकिन सी ++ मानक पुस्तकालय में, लंबी संख्या अभी भी समर्थित नहीं हैं। इसलिए मैंने इसे खुद लिखने का फैसला किया।

वर्ग संरचना

पहली बात यह है कि हमारे नंबर को कैसे स्टोर किया जाए। मैं इसे संख्या के एक सरणी के रूप में संग्रहीत करता हूं, रिवर्स ऑर्डर में (यह सभी कार्यों को लागू करना आसान बनाता है), तुरंत सरणी के एक तत्व में 9 अंक (जो मेमोरी बचाता है):

class big_integer { //    (1 000 000 000) static const int BASE = 1000000000; //    std::vector<int> _digits; //   bool _is_negative; };

मेरे कार्यान्वयन में, शून्य के दो तुरंत प्रतिनिधित्व होंगे - एक खाली वेक्टर के रूप में और एक एकल शून्य के साथ वेक्टर के रूप में।

संख्या निर्माण

पहली चीज जो आपको करने के लिए सीखने की ज़रूरत है वह एक नंबर बनाना है। इसे स्ट्रिंग से संख्याओं में परिवर्तित किया जाता है:

 big_integer::big_integer(std::string str) { if (str.length() == 0) { //      this->_is_negative = false; } else { if (str[0] == '-') { str = str.substr(1); this->_is_negative = true; } else { this->_is_negative = false; } // - i    size_t.      , //   int      ,   long long for (long long i = str.length(); i > 0; i -= 9) { if (i < 9) this->_digits.push_back(atoi(str.substr(0, i).c_str())); else this->_digits.push_back(atoi(str.substr(i - 9, 9).c_str())); } //     ,    this->_remove_leading_zeros(); } }

अग्रणी शून्य को हटाने के लिए प्रक्रिया का कोड अपमान के लिए सरल है:

 void big_integer::_remove_leading_zeros() { while (this->_digits.size() > 1 && this->_digits.back() == 0) { this->_digits.pop_back(); } //   ,        if (this->_digits.size() == 1 && this->_digits[0] == 0) this->_is_negative = false; }

हमें नियमित संख्याओं को लंबे समय तक बदलने में सक्षम होना चाहिए:

 big_integer::big_integer(signed long long l) { if (l < 0) { this->_is_negative = true; l = -l; } else this->_is_negative = false; do { this->_digits.push_back(l % big_integer::BASE); l /= big_integer::BASE; } while (l != 0); } big_integer::big_integer(unsigned long long l) { this->_is_negative = false; do { this->_digits.push_back(l % big_integer::BASE); l /= big_integer::BASE; } while (l != 0); }

अन्य प्रकारों से रूपांतरण कोड और भी सरल है, मैंने इसे यहां उद्धृत नहीं किया है।

संख्या उत्पादन

अब हमें यह जानने की जरूरत है कि हम अपने नंबर को एक स्ट्रीम में कैसे प्रिंट करें और इसे स्ट्रिंग में बदलें:

 std::ostream& operator <<(std::ostream& os, const big_integer& bi) { if (bi._digits.empty()) os << 0; else { if (bi._is_negative) os << '-'; os << bi._digits.back(); //        9  //    -,     char old_fill = os.fill('0'); for (long long i = static_cast<long long>(bi._digits.size()) - 2; i >= 0; --i) { os << std::setw(9) << bi._digits[i]; } os.fill(old_fill); } return os; } big_integer::operator std::string() const { std::stringstream ss; ss << *this; return ss.str(); }

संख्या तुलना

अब हमें यह सीखने की जरूरत है कि एक दूसरे के साथ दो नंबरों की तुलना कैसे करें। सिद्धांत कहता है कि इसके लिए, केवल दो ऑपरेशन पर्याप्त हैं, बाकी को उनके आधार पर प्राप्त किया जा सकता है। तो, पहले हम सीखते हैं कि समानता के लिए दो संख्याओं की तुलना कैसे करें:

 bool operator ==(const big_integer& left, const big_integer& right) { //       if (left._is_negative != right._is_negative) return false; //      ,     if (left._digits.empty()) { if (right._digits.empty() || (right._digits.size() == 1 && right._digits[0] == 0)) return true; else return false; } if (right._digits.empty()) { if (left._digits.size() == 1 && left._digits[0] == 0) return true; else return false; } //       ,         () if (left._digits.size() != right._digits.size()) return false; for (size_t i = 0; i < left._digits.size(); ++i) if (left._digits[i] != right._digits[i]) return false; return true; }

अब जांचें कि क्या एक संख्या दूसरे से कम है:

 bool operator <(const big_integer& left, const big_integer& right) { if (left == right) return false; if (left._is_negative) { if (right._is_negative) return ((-right) < (-left)); else return true; } else if (right._is_negative) return false; else { if (left._digits.size() != right._digits.size()) { return left._digits.size() < right._digits.size(); } else { for (long long i = left._digits.size() - 1; i >= 0; --i) { if (left._digits[i] != right._digits[i]) return left._digits[i] < right._digits[i]; } return false; } } }

यहां हम संख्या के संकेत को बदलने के लिए एकात्मक निषेध का उपयोग करते हैं। मैंने समरूपता के लिए एक संयुक्त प्लस भी पेश किया:

 const big_integer big_integer::operator +() const { return big_integer(*this); } const big_integer big_integer::operator -() const { big_integer copy(*this); copy._is_negative = !copy._is_negative; return copy; }

आपको कॉन्स्टेबल big_integer को वापस करने की आवश्यकता क्यों है, इसके बारे में ज्ञान है, न कि big_integer, साथ ही एक फ्रेंडली ऑपरेटर फंक्शन और एक क्लास के मेंबर ऑपरेटर के बीच चयन के नियमों के बारे में, मैंने इस लेख से सीखा है।

फिर सब कुछ काफी सरल है:

 bool operator !=(const big_integer& left, const big_integer& right) { return !(left == right); } bool operator <=(const big_integer& left, const big_integer& right) { return (left < right || left == right); } bool operator >(const big_integer& left, const big_integer& right) { return !(left <= right); } bool operator >=(const big_integer& left, const big_integer& right) { return !(left < right); }

अंकगणित संचालन

इसके अलावा

मैं संचालन के साथ समझदार नहीं हुआ और एक कॉलम में सामान्य स्कूल जोड़ को महसूस किया। चूंकि किसी भी स्थिति में हमें ऑपरेशन के परिणाम के रूप में एक नया नंबर बनाने की आवश्यकता होगी, मैं तुरंत स्टैक पर बाएं ऑपरेंड को मान से कॉपी करता हूं और सीधे संख्याओं को इसमें जोड़ता हूं:

 const big_integer operator +(big_integer left, const big_integer& right) { //        //   ,      if (left._is_negative) { if (right._is_negative) return -(-left + (-right)); else return right - (-left); } else if (right._is_negative) return left - (-right); int carry = 0; //      for (size_t i = 0; i < std::max(left._digits.size(), right._digits.size()) || carry != 0; ++i) { if (i == left._digits.size()) left._digits.push_back(0); left._digits[i] += carry + (i < right._digits.size() ? right._digits[i] : 0); carry = left._digits[i] >= big_integer::BASE; if (carry != 0) left._digits[i] -= big_integer::BASE; } return left; }

यहां मैंने उस मामले में "महंगा" विभाजन ऑपरेशन से बचा था जहां परिणामी "संख्या" उस आधार से बड़ी है जिसके लिए मैं एक साधारण तुलना द्वारा काम करता हूं।

घटाव

सिद्धांत रूप में, घटाव इसके अलावा के समान है। घटाव की तुलना में कमी होने पर इस मामले पर विचार करना आवश्यक है:

 const big_integer operator -(big_integer left, const big_integer& right) { if (right._is_negative) return left + (-right); else if (left._is_negative) return -(-left + right); else if (left < right) return -(right - left); int carry = 0; for (size_t i = 0; i < right._digits.size() || carry != 0; ++i) { left._digits[i] -= carry + (i < right._digits.size() ? right._digits[i] : 0); carry = left._digits[i] < 0; if (carry != 0) left._digits[i] += big_integer::BASE; } left._remove_leading_zeros(); return left; }

वेतन वृद्धि और गिरावट

इन दो कार्यों को लागू करने से पहले, हमें असाइनमेंट के साथ जोड़ और घटाव को लागू करना होगा:

 big_integer& big_integer::operator +=(const big_integer& value) { return *this = (*this + value); } big_integer& big_integer::operator -=(const big_integer& value) { return *this = (*this - value); }

फिर ऑपरेशन के उपसर्ग संस्करणों को एक पंक्ति में लागू किया जाता है, और पोस्टफ़िक्स संस्करण केवल थोड़े अधिक जटिल होते हैं:

 const big_integer big_integer::operator++() { return (*this += 1); } const big_integer big_integer::operator ++(int) { *this += 1; return *this - 1; } const big_integer big_integer::operator --() { return *this -= 1; } const big_integer big_integer::operator --(int) { *this -= 1; return *this + 1; }

गुणन

मैंने करातसुबा का तेज गुणा नहीं लिखा, और फिर से "स्कूल" अंकगणित का उपयोग किया:

 const big_integer operator *(const big_integer& left, const big_integer& right) { big_integer result; result._digits.resize(left._digits.size() + right._digits.size()); for (size_t i = 0; i < left._digits.size(); ++i) { int carry = 0; for (size_t j = 0; j < right._digits.size() || carry != 0; ++j) { long long cur = result._digits[i + j] + left._digits[i] * 1LL * (j < right._digits.size() ? right._digits[j] : 0) + carry; result._digits[i + j] = static_cast<int>(cur % big_integer::BASE); carry = static_cast<int>(cur / big_integer::BASE); } } //     result._is_negative = left._is_negative != right._is_negative; result._remove_leading_zeros(); return result; }

विभाजन

चूंकि मुझे इंटरनेट पर विभाजित करने के तेज तरीके नहीं मिले, इसलिए हम स्कूल डिवीजन कॉर्नर का उपयोग करेंगे। चलो उच्च रैंक के साथ साझा करना शुरू करते हैं। हमें लाभांश की अधिकतम संभव संख्या से लाभांश के वर्तमान मूल्य को कम करने की आवश्यकता है। यह अधिकतम मूल्य द्विआधारी खोज द्वारा खोजा जाएगा। लेकिन सबसे पहले, हमें संख्या को दाईं ओर "शिफ्टिंग" के कार्य को निर्धारित करने की आवश्यकता है, जो हमें बिट्स पर क्रमिक रूप से पुनरावृति करने की अनुमति देगा:

 void big_integer::_shift_right() { if (this->_digits.size() == 0) { this->_digits.push_back(0); return; } this->_digits.push_back(this->_digits[this->_digits.size() - 1]); //             , //  i  ""  size_t for (size_t i = this->_digits.size() - 2; i > 0; --i) this->_digits[i] = this->_digits[i - 1]; this->_digits[0] = 0; }

अब हम स्वयं विभाजन का वर्णन करेंगे:

 const big_integer operator /(const big_integer& left, const big_integer& right) { //     if (right == 0) throw big_integer::divide_by_zero(); big_integer b = right; b._is_negative = false; big_integer result, current; result._digits.resize(left._digits.size()); for (long long i = static_cast<long long>(left._digits.size()) - 1; i >= 0; --i) { current._shift_right(); current._digits[0] = left._digits[i]; current._remove_leading_zeros(); int x = 0, l = 0, r = big_integer::BASE; while (l <= r) { int m = (l + r) / 2; big_integer t = b * m; if (t <= current) { x = m; l = m + 1; } else r = m - 1; } result._digits[i] = x; current = current - b * x; } result._is_negative = left._is_negative != right._is_negative; result._remove_leading_zeros(); return result; }

यहाँ big_integer::divide_by_zero एक खाली वर्ग है जिसे std::exception से विरासत में मिला std::exception ।

शेष लेना

वास्तव में, पिछले ऑपरेशन में, शेष वास्तव में current चर में संग्रहीत है। लेकिन मैंने शेष के संकेत की परिभाषा पर आश्चर्य किया। विकिपीडिया का कहना है कि एक विभाजन का शेष हमेशा सकारात्मक होता है। इसलिए, मैंने इस ऑपरेशन का यह संस्करण लिखा:

 const big_integer operator %(const big_integer& left, const big_integer& right) { big_integer result = left - (left / right) * right; if (result._is_negative) result += right; return result; }

पेचीदगी

मैंने त्वरित घातांक एल्गोरिथ्म का उपयोग किया। इसमें विषमता के लिए संख्या की जांच करना आवश्यक है। चूँकि 2 के बंटवारे के शेष भाग की गणना करना महंगा होगा, इसे हल्के ढंग से रखने के लिए, हम निम्नलिखित कार्यों को प्रस्तुत करते हैं:

 bool big_integer::odd() const { if (this->_digits.size() == 0) return false; return this->_digits[0] & 1; } bool big_integer::even() const { return !this->odd(); }

अब इरेक्शन को ही लिखें:

 const big_integer big_integer::pow(big_integer n) const { big_integer a(*this), result(1); while (n != 0) { if (n.odd()) result *= a; a *= a; n /= 2; } return result; }

पूर्ण वर्ग कोड: pastebin.com/MxQdP5s9

वह सब है! अब आप गणना कर सकते हैं, उदाहरण के लिए, 2 ¹⁰⁰⁰ , या तथ्यात्मक 100:

 #include <iostream> #include "big_integer.hpp" using namespace std; int main() { big_integer bi("2"), bi2 = 100; cout << bi.pow(1000) << endl; big_integer f = 1; for (big_integer i = 2; i <= bi2; ++i) f *= i; cout << f << endl; }

साहित्य

e-maxx.ru - साइट जो ओलंपियाड एल्गोरिदम को समर्पित है
cppalgo.blogspot.ru/2010/05/blog-post.html - इगोर बिल्लायेव का ब्लॉग

C ++ में लंबी अंकगणित का कार्यान्वयन