"क्रानिक", या पाई के अंक खोजने के लिए एक एल्गोरिथ्म

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

और मुझे ऐसा एल्गोरिथ्म मिला, बहुत "नल" एल्गोरिथ्म । नल शब्द यहां अजीब लगता है, लेकिन मुझे इस एल्गोरिथ्म का नाम अंग्रेजी से अनुवाद करने का एक बेहतर तरीका नहीं मिला, कैसे शब्दशः अनुवाद करना है। सामान्य तौर पर, मूल में यह "पी के अंकों के लिए एक स्पिगोट एल्गोरिथम" जैसा लगता है। एल्गोरिथ्म और इसके हर के लेखक अमेरिकन गणितज्ञ स्टेनली रैबिनोविट (स्टेनली रैबिनोविट) और स्टेन वैगन (स्टेन वैगन) हैं। इन दोनों साथियों ने 1995 में नंबर पाई के अंकों को खोजने के लिए अपना एल्गोरिदम बनाया। एल्गोरिथ्म का बहुत विचार 1968 में एक निश्चित बिक्री (बिक्री) की कलम से निकला, और उस एल्गोरिथ्म का उद्देश्य संख्या ई के अंकों को खोजना था।

सामान्य तौर पर, अंग्रेजी-रूसी शब्दकोश स्पिगोट शब्द का अनुवाद "आस्तीन" के रूप में करते हैं। स्पष्टता का यह अनुवाद कोई संकेत नहीं देता है। इसलिए, मैंने इस शब्द को "नल" के रूप में अनुवादित किया, क्योंकि अंग्रेजी में स्पिगोट को एक तंत्र के रूप में वर्णित किया गया है जो द्रव प्रवाह को नियंत्रित करता है। एल्गोरिथ्म का विचार यह है कि एक पुनरावृत्ति के लिए हमें संख्या पाई का एक अंक मिलता है और फिर हम इसका उपयोग नहीं करते हैं। यही है, संख्या एल्गोरिथ्म से पालन करने लगती है, जैसे नल से पानी।

अब एल्गोरिथ्म ही। मैं सभी गणित में नहीं जाऊंगा (जो कि मैंने, वास्तव में, एल्गोरिदम का विश्लेषण नहीं किया था), आप इसके बारे में और अधिक यहाँ पढ़ सकते हैं। वैसे, इस लिंक पर, पास्कल में पाई नंबर के 1000 अंकों को खोजने के लिए एल्गोरिथ्म का कार्यान्वयन भी है, जिसे मैंने अपने आलस्य में तुरंत उपयोग करने का फैसला किया था। मैंने इसे जावा में फिर से लिखा, लेकिन नहीं - यह काम नहीं किया। यह मुझे बकवास करने के लिए कुछ अस्पष्ट लाया। मैंने इस बात को दूर फेंक दिया, क्योंकि आप एक कोड को डीबग कर सकते हैं जिसे आप नहीं समझते हैं, आप खुद जानते हैं कि पानी के साथ एक जलते हुए तेल को कैसे बुझाना है। इसलिए, मैंने खुद एल्गोरिथ्म से निपटने का फैसला किया।
पाई के एन अंकों को खोजने के लिए, आपको लंबाई [10 * n / 3] की एक सरणी की आवश्यकता होती है। और पूर्णांक। एल्गोरिथ्म की ख़ासियत यह है कि केवल पूर्णांक अंकगणित का उपयोग किया जाता है। हम संख्या 2 के साथ सरणी के सभी कक्षों को इनिशियलाइज़ करते हैं।



अगला, पाई संख्या के एक अंक को खोजने के लिए, आपको अंत से शुरुआत तक सरणी की सभी कोशिकाओं के माध्यम से जाने और सरल क्रियाएं करने की आवश्यकता है। एक तालिका के उदाहरण पर, हम क्रम में सब कुछ पर विचार करेंगे। मान लीजिए हम पाई के 3 अंक ढूंढना चाहते हैं। ऐसा करने के लिए, हमें एक पूर्णांक प्रकार की 3 * 10/3 = 10 कोशिकाओं को आरक्षित करना होगा। हम उन सभी को संख्या 2 से भरते हैं। अब पहले अंक की खोज शुरू करते हैं ...

सरणी के अंत में प्रारंभ करें। हम अंतिम तत्व लेते हैं (संख्या 9 के तहत, यदि हम 0. के साथ गिनती शुरू करते हैं। उसी संख्या को अंश कहा जाएगा, और तालिका में इसके नीचे एक भाजक है) - यह 2. है इसे 10 से गुणा करें (2 * 10 * 20) । परिणामी संख्या 20 में हम "स्थानांतरण" सेल से संख्या जोड़ते हैं - वह संख्या जो अधिक सही संचालन से स्थानांतरित की जाती है। बेशक, हमने कुछ भी सही नहीं गिना है, इसलिए यह संख्या 0. है। परिणाम "योग" में लिखा गया है। "शेष" में हम भाजक द्वारा योग को विभाजित करने के शेष लिखते हैं: 20 मॉड 19 = 1 । और अब हम अगले चरण के लिए "स्थानांतरण" पर विचार करते हैं। यह अंश के हर के योग को अंश में विभाजित करने के परिणाम के बराबर होगा: (20/19) * 9 = 9 । और सेल में परिणामी संख्या को "स्थानांतरण" के साथ लिखें, जो वर्तमान कॉलम के बाईं ओर खड़ा है। हम सरणी के प्रत्येक तत्व के साथ एक ही क्रिया करते हैं (10 से गुणा करें, योग की गणना करें, शेष और अगले चरण तक ले जाएं) जब तक हम तत्व संख्या 0. पर नहीं पहुंच जाते हैं। यहां क्रियाएं थोड़ी भिन्न हैं। तो, आइए देखें कि हमारे पास तालिका में क्या है। शून्य के तहत - 2 के बराबर एक सरणी तत्व, और पिछले चरण से 10. के बराबर स्थानांतरण। पिछले चरणों में, हम सरणी तत्व को 10 से गुणा करते हैं और इसमें स्थानांतरण जोड़ते हैं। कुल में, हमें 30 मिलीं। और अब हम राशि को भाजक से नहीं, बल्कि 10 (!) से विभाजित करते हैं। नतीजतन, हमें 30/10 = 3 + 0 (जहां 0 शेष है) मिलता है। परिणामी संख्या 3 वह संख्या पाई का पहला अंक पोषित होगी। और शेष 0 उसे लिखी गई सेल में लिखा गया है। बचे हुए के लिए क्या थे? उन्हें अगले पुनरावृत्ति में उपयोग करने की आवश्यकता है - पाई के अगले अंक को खोजने के लिए। इसलिए, हमारे मूल 10 * n / 3 सरणी में बचे हुए को स्टोर करना बुद्धिमानी है। इस प्रकार, यह स्पष्ट है कि एल्गोरिथ्म की क्षमताएं इस सरणी के आकार पर सटीक रूप से निर्भर करती हैं। इसलिए, पाए गए अंकों की संख्या उपलब्ध कंप्यूटर मेमोरी या उस भाषा से सीमित है जिसमें आप एल्गोरिथ्म को लागू करते हैं (निश्चित रूप से, भाषा प्रतिबंधों को दरकिनार किया जा सकता है)।

लेकिन यह सब नहीं है। एक कैविएट है। प्रत्येक पुनरावृत्ति के अंत में, एक अतिप्रवाह की स्थिति हो सकती है। यानी "योग" में शून्य कॉलम में हमें 100 से अधिक संख्या मिलती है (यह स्थिति बहुत कम ही होती है)। फिर पाई का अगला आंकड़ा 10. अजीब है, है ना? आखिरकार, दशमलव संख्या प्रणाली में अंक केवल 0 से 9. तक होते हैं। इस मामले में, 10 के बजाय, आपको 0 लिखना होगा, और पिछले अंक को 1 से बढ़ाना होगा (और अंतिम से पहले वाला एक है अगर अंतिम 9 है, आदि)। इस प्रकार, एक दर्जन की उपस्थिति पहले से मिली संख्याओं में से एक या अधिक को बदल सकती है। ऐसी स्थितियों को कैसे ट्रैक करें? यह आवश्यक है कि शुरू में नया आंकड़ा अमान्य पाया जाए। ऐसा करने के लिए, एक चर होना पर्याप्त है, जो अमान्य अंकों की संख्या की गणना करेगा। हमने एक अंक पाया - हमने अमान्य अंकों की संख्या में 1. वृद्धि की। यदि अगला पाया गया अंक 9 या 10 के बराबर नहीं है, तो हम पहले पाए गए अंकों (और अमान्य के रूप में चिह्नित) को वैध मानते हैं, अर्थात् हम अमान्य अंकों की संख्या को 0 पर रीसेट करते हैं, और पाए गए नए अंकों को अमान्य मानने लगते हैं (यानी, आप तुरंत 1 पर रीसेट कर सकते हैं)। यदि अगला अंक 9 पाया जाता है, तो अमान्य अंकों की संख्या में 1. वृद्धि करें। यदि अगला अंक 10 है, तो हम सभी अमान्य अंकों को 10 के बजाय 1 से बढ़ाते हैं, 0 लिखते हैं और इस 0 को अमान्य मानते हैं। यदि इन स्थितियों की निगरानी नहीं की जाती है, तो एकल गलत नंबर (या अधिक) दिखाई देंगे।

यह संपूर्ण एल्गोरिथ्म है कि लेखकों ने नल के साथ तुलना की है। नीचे जावा में कार्यान्वित एक विधि का कोड है जो संख्या पीआई के साथ एक स्ट्रिंग लौटाता है।

public static String piSpigot(final int n) { //        StringBuilder StringBuilder pi = new StringBuilder(n); int boxes = n * 10 / 3; //   int reminders[] = new int[boxes]; //    for (int i = 0; i < boxes; i++) { reminders[i] = 2; } int heldDigits = 0; //     for (int i = 0; i < n; i++) { int carriedOver = 0; //     int sum = 0; for (int j = boxes - 1; j >= 0; j--) { reminders[j] *= 10; sum = reminders[j] + carriedOver; int quotient = sum / (j * 2 + 1); //      reminders[j] = sum % (j * 2 + 1); //       carriedOver = quotient * j; // j -  } reminders[0] = sum % 10; int q = sum / 10; //     //    if (q == 9) { heldDigits++; } else if (q == 10) { q = 0; for (int k = 1; k <= heldDigits; k++) { int replaced = Integer.parseInt(pi.substring(i - k, i - k + 1)); if (replaced == 9) { replaced = 0; } else { replaced++; } pi.deleteCharAt(i - k); pi.insert(i - k, replaced); } heldDigits = 1; } else { heldDigits = 1; } pi.append(q); //    } if (pi.length() >= 2) { pi.insert(1, '.'); //      3 } return pi.toString(); } 

ब्याज के लिए, मैंने n के मान (पाया जाने वाले अंकों की संख्या) के आधार पर एक एल्गोरिथ्म प्रदर्शन परीक्षण किया। यहाँ निम्नलिखित चार्ट है:



एक लाख अंक खोजने में साढ़े आठ घंटे से अधिक समय लगा। मैंने परिणामों को छापे बिना परीक्षण किया और स्ट्रिंग स्ट्रिंग का उपयोग नहीं किया, लेकिन एक बाइट सरणी।

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

पुनश्च: बेली - बोरवेइन - डिस्चार्ज श्रेणी से प्लॉफ़ी सूत्र पर आधारित एल्गोरिथ्म पर पहले इस लेख में हैबे पर चर्चा की गई थी।

http://en.wikipedia.org/wiki/Pi
http://en.wikipedia.org/wiki/Spigot_algorithm
http://www.mathpropress.com/stan/bibliography/spigot.pdf
http://www.pi314.net/eng/goutte.php
http://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula
http://habrahabr.ru/post/179829/