कोडिंग साक्षात्कार की तैयारी · पाठ

Fast Modular Exponentiation

pow(a, b, m) से powers निकालें

पाठ 2, कुल 4 में से13 चरण

Fast Modular Exponentiation, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 2वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

घात की समस्या

अक्सर आपको किसी संख्या को बहुत बड़े घात तक उठाना होता है और यह सब मॉड्यूलस के अंतर्गत करना होता है। एक-एक गुणनखंड करके गुणा करने में बहुत अधिक चरण लगेंगे। ⚡

सरल तरीका बहुत धीमा है

b बार गुणा करने वाला लूप O(b) चरणों में चलता है। जब घातांक लगभग एक अरब का हो, तो काम पूरा होने से पहले ही यह समय-सीमा पार कर जाएगा।

for _ in range(b): r = r * a % MOD

तेज़ी से बढ़ने के लिए वर्ग कीजिए

युक्ति वर्ग करने की है: a की 8वीं घात ((a का वर्ग) का वर्ग) का वर्ग होती है। प्रत्येक वर्ग करने पर घातांक दोगुना हो जाता है, इसलिए कुछ ही चरणों में बहुत बड़ी घातें प्राप्त हो जाती हैं।

घातांक को द्विआधारी रूप में पढ़िए

हर घातांक दो की घातों का योग होता है, और यही उसका द्विआधारी रूप है। इसलिए केवल उन आधार-घातों से गुणा कीजिए जिनके स्थान पर बिट 1 है और बाकी को छोड़ दीजिए।

# 13 = 1101 -> a^8 * a^4 * a^1

सबसे निचली बिट जाँचिए

सबसे निचली बिट जाँचने के लिए b & 1 देखिए। यदि इसका परिणाम 1 हो, तो आगे बढ़ने से पहले वर्तमान आधार को अब तक के परिणाम में गुणा करके शामिल कर दीजिए।

if b & 1: result = result * base % MOD

हर चक्र में शिफ्ट और वर्ग कीजिए

प्रत्येक बिट के बाद आधार का वर्ग कीजिए और घातांक को एक स्थान दाईं ओर शिफ्ट कीजिए। किसी भी व्यावहारिक इनपुट के लिए लूप केवल लगभग 30 से 60 बार चलता है।

base = base * base % MOD
b >>= 1

सब कुछ एक साथ रखिए

परिणाम को 1 से शुरू कीजिए, फिर तब तक लूप चलाइए जब तक घातांक धनात्मक हो। इस पूरी तेज़ घातांक गणना को द्विआधारी घातांक या वर्ग करके घातांक निकालना भी कहा जाता है।

result = 1
while b > 0:
    if b & 1: result = result*base%MOD
    base = base*base%MOD
    b >>= 1

लॉग समय में चलता है

क्योंकि प्रत्येक चक्र घातांक को आधा कर देता है, इसलिए लागत O(log b) होती है। इससे एक अरब गुणनों का काम लगभग तीस गुणनों में बदल जाता है और यह किसी भी समय-सीमा के भीतर हो जाता है।

Python आपको pow देता है

आपको यह लूप स्वयं लिखने की आवश्यकता बहुत कम पड़ती है: Python का अंतर्निहित pow(a, b, m) आपके लिए शुद्ध C जैसी गति से तेज़ मॉड्यूलर घातांक गणना करता है।

print(pow(2, 100, MOD))

यह शीघ्र ही क्यों महत्वपूर्ण होगा

तेज़ घातांक गणना फर्मा के मॉड्यूलर प्रतिलोम के पीछे की मुख्य तकनीक है, जिससे आपका परिचय अगले पाठ में होगा। इसे अभी अच्छी तरह सीख लीजिए, फिर मॉड के अंतर्गत भाग करना आसान हो जाएगा।

पहले आधार पर ध्यान दीजिए

लूप से पहले आधार को base % MOD से छोटा कर लीजिए। यदि आधार मॉड्यूलस से पहले ही बड़ा हो, तो हर वर्ग करने के चरण में संख्याएँ अनावश्यक रूप से बड़ी हो जाएँगी।

base = a % MOD

त्वरित जाँच

तेज़ मॉड्यूलर घातांक गणना कितनी तेज़ होती है?

इंटरैक्टिव पाठ में इसका उत्तर दें

पुनरावृत्ति

अब आप वर्ग करके और बिट्स को पढ़कर O(log b) में बहुत बड़े घातांकों तक संख्याएँ उठा सकते हैं। Python में बस pow(a, b, m) को बुलाइए और आगे बढ़िए। 🚀

शुरुआत निःशुल्क

एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क

अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।

पाठ्यक्रम: 90
पाठ: 360

निःशुल्क सीखना शुरू करें पूरा पाठ्यक्रम देखें

अक्सर पूछे जाने वाले प्रश्न

क्या “Fast Modular Exponentiation” पाठ निःशुल्क है?

हाँ—“Fast Modular Exponentiation” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

“Fast Modular Exponentiation” में मैं क्या सीखूँगा?

pow(a, b, m) से powers निकालें आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।

क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?

पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 2वाँ पाठ है।

“Fast Modular Exponentiation” पाठ पूरा करने में कितना समय लगता है?

CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।

क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?

हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।

इस पाठ्यक्रम के सभी पाठ

← कोडिंग साक्षात्कार की तैयारी पर वापस जाएँ