हम एक सरल प्रोग्रामिंग भाषा का एक बहुत तेज़ दुभाषिया लिखने के लिए मैट्रिस के तेजी से घातांक का उपयोग करते हैं

हाल ही में, हब पर एक अच्छा लेख दिखाई दिया - हे (लॉग एन) अंकगणितीय कार्यों में एनटीपी की संख्या की गणना के बारे में। एक उचित सवाल जो टिप्पणियों में पॉप अप हुआ था: "यह अभ्यास में क्यों काम आ सकता है।" अपने आप से एनटीपी की संख्या की गणना बहुत दिलचस्प नहीं हो सकती है, हालांकि, लेख में उपयोग किए जाने वाले मैट्रिसेस के दृष्टिकोण को समस्याओं की एक विस्तृत श्रृंखला के लिए लागू किया जा सकता है।

इस लेख के पाठ्यक्रम में, हम चर्चा करेंगे कि कैसे एक दुभाषिया लिखना है जो सरल संचालन (असाइनमेंट, इसके अलावा, घटाव, और काट-छाँट गुणन) कर सकता है, सीमित संख्या में चर के साथ सीमित संख्या में चर के साथ मनमाने ढंग से पुनरावृत्तियों की संख्या में भिन्नताएं होती हैं, यदि निश्चित रूप से गणना में मध्यवर्ती मूल्य रहते हैं। उचित सीमा)। उदाहरण के लिए, यहाँ एक कोड दुभाषिया को प्रस्तुत किया गया है:

loop 1000000000 loop 1000000000 loop 1000000000 a += 1 b += a end end end end 

तुरंत एक = 100000000000000000000000000 प्रिंट करता है, b = 500000000000000000000000000000000000000000000000000, इस तथ्य के बावजूद कि अगर कार्यक्रम को भोलेपन से निष्पादित किया गया था, तो दुभाषिया को एक ऑक्टिलियन ऑपरेशन करना होगा।

मेरा मानना ​​है कि पाठक को इस बात का अंदाजा है कि मैट्रिक्स क्या है और मैट्रीस का क्या उत्पाद है। इस लेख में, हम विशेष रूप से वर्ग मैट्रिसेस का उपयोग करेंगे और स्क्वायर मैट्रिसेस - एसोसिएटिविटी को गुणा करने की बहुत महत्वपूर्ण संपत्ति पर भरोसा करेंगे।

सादगी के लिए, हम अपने दुभाषिया को चार चर - ए, बी, सी और डी तक सीमित कर देंगे। एक निश्चित समय में दुभाषिया की स्थिति का प्रतिनिधित्व करने के लिए, हम आकार पांच के एक वेक्टर का उपयोग करेंगे, जिनमें से पहले चार तत्वों में क्रमशः चार चर के मान होंगे, और अंतिम एक एकता के बराबर होगा। ।

 (A, B, C, D, 1) 

दुभाषिया के काम की शुरुआत में, हम मानते हैं कि सभी चर के मूल्य शून्य के बराबर हैं।

 (0, 0, 0, 0, 1) 

मान लीजिए कि प्रोग्राम कोड में पहले ऑपरेशन में एक स्ट्रिंग है

 A += 5 

इस आदेश का प्रभाव यह है कि चर A का मान पांच तक बढ़ जाएगा, जबकि अन्य तीन चर के मान नहीं बदलेंगे। इसे निम्न मैट्रिक्स के रूप में दर्शाया जा सकता है:

 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 5 0 0 0 1 

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

 v[0] * 1 + v[4] * 5 

चूँकि v [0] में चर A में वर्तमान मान होता है, और v [4] हमेशा एक के बराबर होता है, फिर

 v[0] * 1 + v[4] * 5 = A + 5 

यदि वर्तमान स्थिति के वेक्टर को इस मैट्रिक्स से गुणा किया जाता है, तो परिणामी वेक्टर एक ऐसी स्थिति के अनुरूप होगा जिसमें A पांच और है, आवश्यकतानुसार।
यदि मैट्रिक्स को थोड़ा बदल दिया जाता है, तो पहली पंक्ति के पहले तत्व में इकाई को हटा दिया जाता है:

 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 5 0 0 0 1 

पहले की तरह, पहले को छोड़कर सभी तत्वों के मूल्य नहीं बदलेंगे, जबकि पहला तत्व v [4] * 5, या सिर्फ पांच के बराबर हो जाएगा। ऐसी मैट्रिक्स द्वारा वर्तमान स्थिति वेक्टर को गुणा करना कमांड निष्पादित करने के बराबर है

 A = 5 

आइए ऐसे मैट्रिक्स को देखें:

 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 

पहचान मैट्रिक्स से इसका एकमात्र अंतर चौथी पंक्ति में दूसरा तत्व है, जो एकता के बराबर है। जाहिर है, इस मैट्रिक्स द्वारा वर्तमान स्थिति वेक्टर को गुणा करना पहले और अंतिम तीन तत्वों में मूल्यों को नहीं बदलेगा, जबकि दूसरे तत्व का मूल्य बदल जाएगा

 v[1] * 1 + v[3] * 1 

चूँकि v [1] में चर B का वर्तमान मान होता है, और v [3] में चर D का वर्तमान मान होता है, ऐसे मैट्रिक्स द्वारा राज्य वेक्टर को गुणा करना कमांड B + = D को निष्पादित करने के बराबर है।

इसी तरह से तर्क करते हुए, यह समझा जा सकता है कि राज्य मैट्रिक्स को अगले मैट्रिक्स से गुणा करना कमांड को निष्पादित करने के बराबर है * * - 7

 1 0 0 0 0 0 1 0 0 0 0 0 7 0 0 0 0 0 1 0 0 0 0 0 1 

टीमों के संयोजन के लिए आगे बढ़ते हैं। वेक्टर v को वर्तमान स्थिति निर्दिष्ट करते हैं, मैट्रिक्स Ma कमांड A + = 5 से मेल खाती है, और मैट्रिक्स Mm कमांड A * = 7. से मेल खाती है, फिर इन दो कमांड के निष्पादन के बाद राज्य के लिए वेक्टर r प्राप्त करने के लिए, हम पहले Ma द्वारा गुणा करते हैं, और फिर मिमी:

 r = v * Ma * Mm 

जैसा कि अपेक्षित था, इन दो मैट्रिसेस द्वारा प्रारंभिक स्टेट वेक्टर को गुणा करना एक ऐसी स्थिति की ओर जाता है जिसमें a = 35:

  1 0 0 0 0 7 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 5 0 0 0 1 0 0 0 0 1 0 0 0 0 1 5 0 0 0 1 35 0 0 0 1 

एक और उदाहरण पर विचार करें - सात से गुणा करने के बजाय, हम सिर्फ पांच को ए सात में जोड़ना चाहते हैं।

 r = v * Ma * Ma * Ma * Ma * Ma * Ma * Ma 

यहां मैट्रिक्स गुणन की सहयोगी संपत्ति बचाव के लिए आती है:

 r = v * Ma * Ma * Ma * Ma * Ma * Ma * Ma = v * (Ma * Ma * Ma * Ma * Ma * Ma * Ma) = v * Ma ^ 7 

यह एक साधारण चक्र का एक उदाहरण है - सात बार मा द्वारा गुणा करने के बजाय, यह मैट्रिक्स मा को सातवीं शक्ति बढ़ाने के लिए पर्याप्त है, और उसके बाद केवल एक गुणा करें। यदि हम तीन बार लूप में निम्नलिखित दो कार्य करना चाहते हैं:

 A += 5 B -= C 

(ऑपरेशन B - = C को मैट्रिक्स Mbc द्वारा दर्शाया जाए), यह इस प्रकार दिखेगा:

 r = v * Ma * Mbc * Ma * Mbc * Ma * Mbc = v * ((Ma * Mbc) * (Ma * Mbc) * (Ma * Mbc)) = v * (Ma * Mbc) ^ 3 

हम केवल एक बार चक्र के शरीर के अनुरूप मैट्रिक्स की गणना करते हैं, जिसके बाद हम इसे शक्ति तक बढ़ाते हैं।

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

मैट्रिक्स के रूप में कार्यक्रम का प्रतिनिधित्व करने के नियम बहुत सरल हैं:
1. प्रत्येक व्यक्तिगत कमांड को एक मैट्रिक्स के रूप में दर्शाया जाता है जो यूनिट से एक तत्व (या असाइनमेंट ऑपरेशन के लिए दो) से भिन्न होता है। इस लेख में ऐसे मेट्रिसेस के उदाहरण ऊपर दिए गए हैं।
2. कई लगातार टीमों को प्रत्येक व्यक्ति टीम के मैट्रिक्स प्रतिनिधित्व के उत्पाद के बराबर मैट्रिक्स के रूप में प्रस्तुत किया जाता है।
3. चक्र को चक्र के पुनरावृत्तियों की संख्या को बढ़ाते हुए, चक्र के शरीर का प्रतिनिधित्व करने वाले मैट्रिक्स के रूप में दर्शाया जाता है।

यदि हमारे पास एक पहचान फ़ंक्शन है जो पहचान मैट्रिक्स लौटाता है:

 def identity(): return [[1 if i == j else 0 for j in range(REGS + 1)] for i in range(REGS + 1)] 

कमांड r1 + = r2 (जहाँ r1 और r2 वैरिएबल हैं) के लिए एक मैट्रिक्स का निर्माण करने वाला फ़ंक्शन इस तरह दिख सकता है:

 def addreg(r1, r2): ret = identity() ret[r2][r1] = 1 return ret 

और कमांड r + = val (r एक वैरिएबल है, वैल एक स्थिर है) इस तरह से है:

 def addval(r, val): ret = identity() ret[REGS][r] = val return ret 

अन्य टीमों के मैट्रिक्स के निर्माण के लिए कार्य समान दिखते हैं - हमें एक एकल मैट्रिक्स मिलता है जिसमें एक तत्व को प्रतिस्थापित किया जाता है।

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

 def doit(): mat = identity() while True: line = sys.stdin.readline().lower() tokens = line.split() if tokens[0] == 'loop': #      elif tokens[0] == 'end': return mat else: r1 = reg_names.index(tokens[0]) try: r2 = reg_names.index(tokens[2]) except: r2 = -1 if tokens[1] == '+=': if r2 == -1: cur = addval(r1, long(tokens[2])) else: cur = addreg(r1, r2) elif tokens[1] == '-=': .... mat = matmul(mat, cur) 

केवल एक चीज बची है, वह है लूप के लिए समर्थन जोड़ना। लूप लूप बॉडी के मैट्रिक्स को उठाकर लूप के पुनरावृत्तियों की संख्या को बढ़ाता है। एक शक्ति को बढ़ाते हुए, जैसा कि ज्ञात है, केवल ओ (लॉग एन) संचालन की आवश्यकता होती है, जहां एन वह शक्ति है जिसके लिए मैट्रिक्स उठाया जाता है। घातांक एल्गोरिथ्म बहुत सरल है:
1. यदि डिग्री शून्य है, तो पहचान मैट्रिक्स लौटें।
2. यदि डिग्री समान है, तो 2N दें, फिर हम M ^ N की गणना कर सकते हैं, और फिर परिणामी मैट्रिक्स के वर्ग को वापस कर सकते हैं।
3. यदि डिग्री विषम है, तो 2N + 1 दें, तो यह M ^ 2N मान को पुनरावर्ती रूप से गणना करने के लिए पर्याप्त है, और परिणामस्वरूप मैट्रिक्स को एम से गुणा करें।

चूंकि हर दो पुनरावृत्तियों में डिग्री दो से कम हो जाती है, ऐसे एल्गोरिथ्म की जटिलता लॉगरिदमिक है।

 def matpow(m, p): if p == 0: return identity() elif p % 2 == 0: tmp = matpow(m, p / 2) return matmul(tmp, tmp) else: return matmul(m, matpow(m, p - 1)) 

दुभाषिया में अब एक पंक्ति को जोड़ना बाकी है:

  ... if tokens[0] == 'loop': cur = matpow(doit(), long(tokens[1])) ... 

और दुभाषिया तैयार है।

एक उदाहरण दुभाषिया गितुब पर उपलब्ध है। सभी कोड 100 से कम लाइनें लेते हैं।

गति परीक्षण के लिए, आप पहले से ही उल्लेखित संख्याओं पर लौट सकते हैं। उदाहरण के लिए, निम्न कोड:

 A = 1 B = 1 loop 100 C = A C += B A = B B = C end end 

101 वें और 102 वें की संख्याओं की गणना की जाएगी:

ए = 573147844013817084101, बी = 927372692193078999176

100 को 1,000,000 के साथ बदलने पर पहले दस लाख और चार सेकंड में एक लाख दूसरी संख्या की गणना होगी। इस तरह के कार्यक्रम का निष्पादन बहुत अधिक माथे को लेगा, क्योंकि कार्यक्रम को कई अंकों की संख्याओं के साथ संचालित करना होता है। यदि आप ऐसा कोड लिखते हैं, जिसका बड़ी संख्याओं के साथ संचालन नहीं होता है, उदाहरण के लिए, लेख की शुरुआत में दिए गए अंकगणितीय प्रगति के योग की गणना करने के लिए कोड, तो पुनरावृत्तियों की संख्या उचित से परे हो सकती है, लेकिन कोड एक दूसरे विभाजन में निष्पादित किया जाएगा

 loop 1000000000000000000000000000000000000000000000 loop 1000000000000000000000000000000000000000000000 loop 1000000000000000000000000000000000000000000000 a += 1 b += a end end end end 

व्यवहार में, इस दृष्टिकोण को लागू किया जा सकता है, उदाहरण के लिए, संकलक को अनुकूलित करने में, जो इस प्रकार बड़ी संख्या में पुनरावृत्तियों को मोड़ सकता है, कम संख्या में चर पर काम कर रहा है।