Nth रूट एल्गोरिथम को स्थानांतरित करना

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

एल्गोरिथम

अंकन

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

अपरिवर्तनीय

प्रत्येक पुनरावृत्ति पर, अपरिवर्तनीय (कंप्यूटर विज्ञान) $y^{n}+r=x$ रोक लेंगे। अपरिवर्तनीय $(y+1)^{n}>x$ पकड़ूँगा। इस प्रकार $y$ के nवें मूल से कम या उसके बराबर सबसे बड़ा पूर्णांक है $x$, और $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$ ताकि ऊपर वर्णित आक्रमणकारियों को रखा जा सके। यह पता चला है कि हमेशा एक ही विकल्प होता है, जैसा कि नीचे सिद्ध किया जाएगा।

Proof of existence and uniqueness of $\beta$

By definition of a digit, $0\leq \beta <B$, and by definition of a block of digits, $0\leq \alpha <B^{n}$

The first invariant says that:

$x'=y'^{n}+r'$

or

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

So, pick the largest integer $\beta$ such that

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

Such a $\beta$ always exists, since $0\leq \beta <B$ and if $\beta =0$ then $B^{n}y^{n}\leq B^{n}x+\alpha$, but since $y^{n}\leq x$, this is always true for $\beta =0$. Thus, there will always be a $\beta$ that satisfies the first invariant

Now consider the second invariant. It says:

$(y'+1)^{n}>x'\,$

or

$(By+\beta +1)^{n}>B^{n}x+\alpha \,$

Now, if $\beta$ is not the largest admissible $\beta$ for the first invariant as described above, then $\beta +1$ is also admissible, and we have

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

This violates the second invariant, so to satisfy both invariants we must pick the largest $\beta$ allowed by the first invariant. Thus we have proven the existence and uniqueness of $\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})$, तो उपयोग करके $r$ के बजाय $x$ हम समय और स्थान को 1/ के कारक से बचाते हैं$n$. यह भी $B^{n}y^{n}$ हम नए परीक्षण में घटाते हैं एक को रद्द कर देता है $(By+\beta )^{n}$, तो अब की उच्चतम शक्ति $y$ हमें मूल्यांकन करना है $y^{n-1}$ इसके बजाय $y^{n}$.

सारांश

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$ उपयोग किए गए दशमलव बिंदु के बाद रेडिकैंड के अंकों की संख्या है (एक ऋणात्मक संख्या यदि एल्गोरिथम अभी तक दशमलव बिंदु तक नहीं पहुंचा है)।

कागज और पेंसिल nth जड़ें

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

1. 4 4 2 2 4 ——————————————————————

_ 3/ 3.000 000 000 000 000

\/ 1 = 3(10×0)²×1 +3(10×0)×1² +1^3</उप>

     —
     2 000

1 744 = 3(10×1)²×4 +3(10×1)×4² +4^3</उप>

     —————
       256 000

241 984 = 3(10×14)²×4 +3(10×14)×4² +4^3</उप>

       ———————
        14 016 000

12 458 888 = 3(10×144)²×2 +3(10×144)×2² +2^3</उप>

        ———————————
         1 557 112 000

1 247 791 448 = 3(10×1442)²×2 +3(10×1442)×2² +2^3</उप>

         ——————————————
           309 320 552 000

249 599 823 424 = 3(10×14422)²×4 +3(10×14422)×4² +4^3</उप>

           ————————————————
            59 720 728 576

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

प्रदर्शन

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

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

ध्यान दें कि बेस बढ़ाने से चुनने में लगने वाला समय बढ़ जाता है $\beta$ के कारक द्वारा $O(\log(B))$, लेकिन एक ही कारक द्वारा दी गई सटीकता प्राप्त करने के लिए आवश्यक अंकों की संख्या कम हो जाती है, और चूंकि एल्गोरिथ्म अंकों की संख्या में घन समय है, आधार को बढ़ाने से समग्र गति मिलती है $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

यह भी देखें

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

बाहरी कड़ियाँ

• 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.