Nवें रूट एल्गोरिदम को स्थानांतरित करना

स्थानांतरण Nवें मूल एल्गोरिदम एक धनात्मक वास्तविक संख्या के Nवें मूल को निकालने के लिए एक एल्गोरिदम है जो मूलांक के Nअंकों में परिवर्तन करके पुनरावृत्त रूप से आगे बढ़ता है, अधिक महत्वपूर्ण से प्रारंभ होता है, और लंबे विभाजन के समान विधि से प्रत्येक पुनरावृत्ति पर मूल का एक अंक उत्पन्न करता है।

एल्गोरिथम

संकेतन

मान लीजिए कि आप जिस संख्या प्रणाली का उपयोग कर रहे हैं उसका आधार $B$ है और निकाले जाने वाले मूल की डिग्री $n$ है। मान लीजिए कि अब तक संसाधित किया गया मूलांक $x$ है, अब तक निकाली गई मूल $y$ है और शेषफल $r$ है। मान लीजिए $\alpha$ मूलांक का अगला $n$ अंक है, और $\beta$ मूल का अगला अंक है। मान लीजिए $x'$ अगले पुनरावृत्ति के लिए $x$ का नया मान है, $y'$ अगले पुनरावृत्ति के लिए $y$ का नया मान है, और $r'$ अगले पुनरावृत्ति के लिए $r$ का नया मान है। ये सभी पूर्णांक हैं.

अपरिवर्तनीय

प्रत्येक पुनरावृत्ति पर, अपरिवर्तनीय $y^{n}+r=x$ कायम रहेगा। अपरिवर्तनीय $(y+1)^{n}>x$ धारण करेगा। इस प्रकार $y$, x के nवें मूल से कम या उसके समान अधिक उच्च पूर्णांक है, और r शेषफल है।

आरंभीकरण

यदि $x,y$ और $r$ का प्रारंभिक मान 0 होना चाहिए। पुनः पुनरावृत्ति के लिए $\alpha$ का मान मूलांक के n अंकों का अधिक महत्वपूर्ण संरेखित ब्लॉक होना चाहिए। यदि $n$ अंकों के एक संरेखित ब्लॉक का अर्थ है अंकों का एक ब्लॉक संरेखित करना जिससे दशमलव बिंदु ब्लॉकों के मध्य आ जाए उदाहरण के लिए, 123.4 में दो अंकों का अधिक महत्वपूर्ण संरेखित ब्लॉक 01 है, अगला अधिक महत्वपूर्ण 23 है, और तृतीय अधिक महत्वपूर्ण 40 है।

मुख्य लूप

प्रत्येक पुनरावृत्ति पर हम मूलांक के $n$ अंकों में परिवर्तन करते हैं, इसलिए हमारे पास $x'=B^{n}x+\alpha$ है और हम मूल का एक अंक उत्पन्न करते हैं, इसलिए हमारे पास $y'=By+\beta$ है। प्रथम अपरिवर्तनीय तात्पर्य यह है कि $r'=x'-y'^{n}$. हम $\beta$ चुनना चाहते हैं जिससे ऊपर वर्णित अपरिवर्तनीयता बनाय रहे। इससे पता चलता है कि सदैव ऐसा ही एक विकल्प होता है, जैसा कि नीचे सिद्ध किया जाएगा।

संक्षेप में, प्रत्येक पुनरावृत्ति पर:

1. मान लीजिए $\alpha$ मूलांक से अंकों का अगला संरेखित ब्लॉक बनें
2. मान लीजिए $x'=B^{n}x+\alpha$
3. मान लीजिए $\beta$ अधिक उच्च हो $\beta$ ऐसा है कि $(By+\beta )^{n}\leq B^{n}x+\alpha$
4. मान लीजिए $y'=By+\beta$
5. मान लीजिए $r'=x'-y'^{n}$

अब, उस पर ध्यान दें $x=y^{n}+r$, तो स्थिति

$(By+\beta )^{n}\leq B^{n}x+\alpha$

के समान है

$(By+\beta )^{n}-B^{n}y^{n}\leq B^{n}r+\alpha$

और

$r'=x'-y'^{n}=B^{n}x+\alpha -(By+\beta )^{n}$

के समान है

$r'=B^{n}r+\alpha -((By+\beta )^{n}-B^{n}y^{n}).$

इस प्रकार, हमें वास्तव में $x$ की आवश्यकता नहीं है, और चूँकि $r=x-y^{n}$ और $x<(y+1)^{n}$, $r<(y+1)^{n}-y^{n}$या $r<ny^{n-1}+O(y^{n-2})$, या $r<nx^{{n-1} \over n}+O(x^{{n-2} \over n})$ इसलिए x के अतिरिक्त $r$ का उपयोग करके हम 1/$n$ के कारक द्वारा समय और स्थान बचाते हैं। साथ ही, नए परीक्षण में हम जो $B^{n}y^{n}$ घटाते हैं, वह $(By+\beta )^{n}$ में से एक को समाप्त कर देता है, इसलिए जहाँ $y$ की उच्चतम घात जिसका हमें मूल्यांकन करना है वह $y^{n}$ के अतिरिक्त $y^{n-1}$ है।

सारांश

1. r और y को 0 से प्रारंभ करें।
2. वांछित दशमलव परिशुद्धता प्राप्त होने तक दोहराएँ:
   1. मान लीजिए $\alpha$ मूलांक से अंकों का अगला संरेखित ब्लॉक बनें।
   2. मान लीजिए $\beta$ सबसे बड़ा हो $\beta$ ऐसा है कि $(By+\beta )^{n}-B^{n}y^{n}\leq B^{n}r+\alpha .$
   3. मान लीजिए $y'=By+\beta$.
   4. मान लीजिए $r'=B^{n}r+\alpha -((By+\beta )^{n}-B^{n}y^{n}).$
   5. नियुक्‍त करें $y\leftarrow y'$ और $r\leftarrow r'.$
3. $y$ अधिक उच्च पूर्णांक है जैसे कि $y^{n}<xB^{k}$, और $y^{n}+r=xB^{k}$, , जहां $k$ दशमलव बिंदु के पश्चात मूलांक के अंकों की संख्या है जो उपयोग किया गया है (एक ऋणात्मक संख्या यदि एल्गोरिदम अभी तक दशमलव बिंदु तक नहीं पहुंचा है)।

कागज-और-पेंसिल nवाँ मूल

जैसा कि ऊपर उल्लेख किया गया है, यह एल्गोरिथ्म लंबे विभाजन के समान है, और यह स्वयं को उसी अंकन के लिए उधार देता है:

1. 4 4 2 2 4

 ——————————————————————
_ 3/ 3.000 000 000 000 000
 \/ 1 = 3(10×0)2×1 +3(10×0)×12+13
 —
 2 000
 1 744 = 3(10×1)2×4 +3(10×1)×42+43
 —————
 256 000
 241 984 = 3(10×14)2×4 +3(10×14)×42+43
 ———————
 14 016 000
 12 458 888 = 3(10×144)2×2 +3(10×144)×22+23
 ——————————
 1 557 112 000
 1 247 791 448 = 3(10×1442)2×2 +3(10×1442)×22+23
 —————————————
 309 320 552 000
 249 599 823 424 = 3(10×14422)2×4 +3(10×14422)×42+43
 ———————————————
 59 720 728 576

ध्यान दें कि पहले या दो पुनरावृत्तियों के बाद प्रमुख पद $(By+\beta )^{n}-B^{n}y^{n}$ पर हावी होता है, इसलिए हम $B^{n}r+\alpha$ को $nB^{n-1}y^{n-1}$ से विभाजित करके $\beta$ पर अधिकांशतः सही पहला अनुमान प्राप्त कर सकते हैं।

प्रदर्शन

प्रत्येक पुनरावृत्ति पर, सबसे अधिक समय लेने वाला कार्य $\beta$ का चयन करना है। हम जानते हैं कि $B$ संभावित मान हैं, इसलिए हम $O(\log(B))$ तुलनाओं का उपयोग करके $\beta$ पा सकते हैं। प्रत्येक तुलना के लिए $(By+\beta )^{n}-B^{n}y^{n}$ का मूल्यांकन करना आवश्यक होगा। Kवें पुनरावृत्ति में, $y$ में $k$ अंक हैं, और बहुपद का मूल्यांकन $k(n-1)$ अंकों तक के $2n-4$ गुणन और $k(n-1)$ अंकों तक $n-2$ जोड़ के साथ किया जा सकता है, एक बार जब हम $y$ के लिए $n-1$ और $\beta$ के लिए n के माध्यम से y और $\beta$ की घात को जान लेते हैं। $\beta$ की एक प्रतिबंधित सीमा है, इसलिए हम स्थिर समय में $\beta$ की घात प्राप्त कर सकते हैं। हम $k(n-1)$ अंकों तक $n-2$ गुणन के साथ y की घात प्राप्त कर सकते हैं। यह मानते हुए कि n-अंकीय गुणन में $O(n^{2})$ समय लगता है और जोड़ने में $O(n)$ समय लगता है, हम प्रत्येक तुलना के लिए समय $O(k^{2}n^{2})$ लेते हैं, या $\beta$ चुनने के लिए समय $O(k^{2}n^{2}\log(B))$ लेते हैं। एल्गोरिथ्म का शेष भाग जोड़ और घटाव है जिसमें $O(k)$ समय लगता है, इसलिए प्रत्येक पुनरावृत्ति में $O(k^{2}n^{2}\log(B))$ लगता है। सभी $k$ अंकों के लिए, हमें समय $O(k^{3}n^{2}\log(B))$ चाहिए।

एकमात्र आंतरिक संचयन की आवश्यकता $r$ है, जो kवें पुनरावृत्ति पर $O(k)$ अंक है। इस एल्गोरिदम में सीमित मेमोरी उपयोग नहीं है, अंकगणित के अधिक प्राथमिक एल्गोरिदम के विपरीत, मानसिक रूप से गणना की जा सकने वाली अंकों की संख्या पर ऊपरी सीमा लगा दी गई है। दुर्भाग्य से, आवधिक इनपुट वाली कोई भी बाउंडेड मेमोरी स्टेट मशीन केवल आवधिक आउटपुट उत्पन्न कर सकती है, इसलिए ऐसे कोई एल्गोरिदम नहीं हैं जो तर्कसंगत संख्याओं से अपरिमेय संख्याओं की गणना कर सकें, और इस प्रकार कोई बाउंडेड मेमोरी मूल निष्कर्षण एल्गोरिदम नहीं हैं।

ध्यान दें कि आधार बढ़ाने से $O(\log(B))$ के कारक द्वारा $\beta$ चुनने के लिए आवश्यक समय बढ़ जाता है, किंतु उसी कारक द्वारा दी गई स्पष्टता प्राप्त करने के लिए आवश्यक अंकों की संख्या घट जाती है, और चूंकि एल्गोरिदम अंकों की संख्या में घन समय है, आधार बढ़ाने से $O(\log ^{2}(B))$ की समग्र गति मिलती है। जब आधार रेडिकैंड से बड़ा होता है, तो एल्गोरिदम बाइनरी खोज में परिवर्तन हो जाता है, इसलिए यह इस प्रकार है कि यह एल्गोरिदम कंप्यूटर के साथ मूल की गणना के लिए उपयोगी नहीं है, क्योंकि यह सदैव अधिक सरल बाइनरी खोज से उत्तम प्रदर्शन करता है, और इसमें समान मेमोरी सम्मिश्र होती है।

उदाहरण

बाइनरी में 2 का वर्गमूल

 1. 0 1 1 0 1
 ------------------
_ /10.00 00 00 00 00 1
 \/1+1
 ----- ----
 1 00 100
 0 + 0
 -------- -----
 1 00 00 1001
 10 01 + 1
 -------- ------
 1 11 00 10101
 1 01 01 + 1
 ------- -------
 1 11 00 101100
 0 + 0
 -------- --------
 1 11 00 00 1011001
 1 01 10 01 1
 ----------
 1 01 11 शेष

3 का वर्गमूल

 1. 7 3 2 0 5
 ----------------------
_ / 3.00 00 00 00 00
 \/ 1 = 20×0×1+1^2
 -
 2 00
 1 89 = 20×1×7+7^2 (27 x 7)
 ----
 11 00
 10 29 = 20×17×3+3^2 (343 x 3)
 -----
 71 00
 69 24 = 20×173×2+2^2 (3462 x 2)
 -----
 1 76 00
 0 = 20×1732×0+0^2 (34640 x 0)
 -------
 1 76 00 00
 1 73 20 25 = 20×17320×5+5^2 (346405 x 5)
 ----------
 2 79 75

5 का घनमूल

 1. 7 0 9 9 7
 ----------------------
_ 3/ 5. 000 000 000 000 000
 \/ 1 = 300×(0^2)×1+30×0×(1^2)+1^3
 -
 4 000
 3 913 = 300×(1^2)×7+30×1×(7^2)+7^3
 -----
 87 000
 0 = 300×(17^2)×0+30×17×(0^2)+0^3
 -------
 87 000 000
 78 443 829 = 300×(170^2)×9+30×170×(9^2)+9^3
 ----------
 8 556 171 000
 7 889 992 299 = 300×(1709^2)×9+30×1709×(9^2)+9^3
 -----------------
 666 178 701 000
 614 014 317 973 = 300×(17099^2)×7+30×17099×(7^2)+7^3
 ---------------
 52 164 383 027

7 का चतुर्थ मूल

 1. 6 2 6 5 7
 ----------------------
_ 4/ 7.0000 0000 0000 0000 0000
 \/ 1 = 4000×(0^3)×1+600×(0^2)×(1^2)+40×0×(1^3)+1^4
 -
 6 0000
 5 5536 = 4000×(1^3)×6+600×(1^2)×(6^2)+40×1×(6^3)+6^4
 ------
 4464 0000
 3338 7536 = 4000×(16^3)×2+600×(16^2)×(2^2)+40×16×(2^3)+2^4
 ---------
 1125 2464 0000
 1026 0494 3376 = 4000×(162^3)×6+600×(162^2)×(6^2)+40×162×(6^3)+6^4
 --------------
 99 1969 6624 0000
 86 0185 1379 0625 = 4000×(1626^3)×5+600×(1626^2)×(5^2)+
 ----------------- 40×1626×(5^3)+5^4
 13 1784 5244 9375 0000
 12 0489 2414 6927 3201 = 4000×(16265^3)×7+600×(16265^2)×(7^2)+
 ---------------------- 40×16265×(7^3)+7^4
 1 1295 2830 2447 6799

यह भी देखें

• वर्गमूलों की गणना की विधियाँ
• nवे मूल एल्गोरिथम

बाहरी संबंध

• Why the square root algorithm works "Home School Math". Also related pages giving examples of the long-division-like pencil and paper method for square roots.
• Reflections on The Square Root of Two "Medium". With an example of a C++ implementation.