बहुपद मूल्यांकन: Difference between revisions

Revision as of 01:36, 16 March 2023

गणित और कंप्यूटर विज्ञान में, बहुपद मूल्यांकन एक बहुपद के मूल्य की गणना को संदर्भित करता है तथा इसके अनिश्चित चर को कुछ मूल्यों के लिए प्रतिस्थापित किया जाता है। दूसरे शब्दों में, बहुपद के मूल्यांकन $P(x_{1},x_{2})=2x_{1}x_{2}+x_{1}^{3}+4$ पर $x_{1}=2,x_{2}=3$ को $P(2,3)=2\cdot 2\cdot 3+2^{3}+4=24.$ को कंप्यूटिंग में समिम्लित किया जाता है,तथा बहुपद वलय § बहुपद मूल्यांकन भी दर्शाया गया है

अविभाज्य बहुपद के मूल्यांकन के लिए $a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{0},$ सबसे सरल विधि का उपयोग करेंगे $n$ गुणन की गणना करने के लिए $a_{n}x^{n}$ , का,तथा $n-1$ गुणन की गणना करने के लिए $a_{n-1}x^{n-1}$ उपयोग करेंगे और इसी तरह कुल मिलाकर ${\tfrac {n(n+1)}{2}}$ से गुणन करेंगेऔर $n$ को जोड़ देंगे।हॉर्नर के नियम जैसे बेहतर विधियों का उपयोग करके $n$ गुणन और $n$ जोड़ को न्यूनतम किया जा सकता है। यदि कुछ प्रीप्रोसेसिंग की अनुमति दी जाती है, तो और भी बचत संभव है।

पृष्ठभूमि

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

पूर्व स्थिति में, फ्लोटिंग-पॉइंट अंकगणित का उपयोग करके बहुपदों का मूल्यांकन किया जाता है, जो सटीक नहीं है। इस प्रकार, मूल्यांकन के लिए भिन्न-भिन्न योजनाएँ, सामान्य तौर पर, थोड़ा विभिन्न उत्तर देंगी। उपरांत वाले स्थिति में, बहुपदों का मूल्यांकन सामान्यतः परिमित क्षेत्र में किया जाता है, इस स्थिति में उत्तर सदैव सटीक होते हैं।

सामान्य विधि

हॉर्नर का नियम

हॉर्नर विधि बार-बार ब्रैकेटिंग का उपयोग करके बहुपद का मूल्यांकन करती है:

{\begin{aligned}a_{0}+&a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\&=a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x(a_{n-1}+x\,a_{n})\cdots {\big )}{\Big )}{\bigg )}.\end{aligned}}

यह विधि गुणन और जोड़ की संख्या को घटाकर केवल

n

कर देती है ,

हॉर्नर विधि इतनी सामान्य है,कि कई कंप्यूटर प्रोसेसर में एक कंप्यूटर निर्देश गुणा-संचय ऑपरेशन जोड़ा गया है, जो एक संयुक्त चरण में जोड़ और गुणा ऑपरेशन करने की अनुमति देता है।

बहुभिन्नरूपी

यदि बहुपद बहुभिन्नरूपी है, तो हॉर्नर के नियम को चर के कुछ क्रम पर पुनरावर्ती रूप से प्रारंभ किया जा सकता है।

उदाहरण.

P(x,y)=4+x+2xy+2x^{2}y+x^{2}y^{2}

के रूप में लिखा जा सकता है

{\begin{aligned}P(x,y)&=4+x(1+y(2)+x(y(2+y)))\quad {\text{or}}\\P(x,y)&=4+x+y(x(2+x(2))+y(x^{2})).\end{aligned}}

इस दृष्टिकोण का एक कुशल संस्करण कार्निसर और गैस्का द्वारा वर्णित किया गया था।^[1]

एस्ट्रिन की योजना

यद्यपि हॉर्नर के नियम की सापेक्ष में न्यूनतम संगणना करना संभव नहीं है, आधुनिक कंप्यूटरों पर मूल्यांकन का क्रम न्यूनतम्प्यूटेशनल दक्षता के लिए बहुत मायने रख सकता है। एस्ट्रिन की योजना के रूप में जाना जाने वाला एक विधि पेड़ जैसे पैटर्न में एक बहुपद की गणना करता है:

{\begin{aligned}P(x)=(a_{0}+a_{1}x)+(a_{2}+a_{3}x)x^{2}+((a_{4}+a_{5}x)+(a_{6}+a_{7}x)x^{2})x^{4}.\end{aligned}}

वर्ग और घातांक द्वारा संयुक्त संगणना को समानांतर करने की अनुमति देता है।

प्रीप्रोसेसिंग के सापेक्ष मूल्यांकन

मनमाने बहुपदों का मूल्यांकन न्यूनतम के सापेक्ष किया जा सकता है अगर हम पहले प्रीप्रोसेस करते हैं तो हॉर्नर के नियम की सापेक्ष में संचालन की आवश्यकता होती है गुणांक $a_{n},\dots ,a_{0}$ .

एक उदाहरण सबसे पहले मोट्ज़किन ने दिया था^[2] जिन्होंने यह नोट किया था

P(x)=x^{4}+a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}

के रूप में लिखा जा सकता है

y=(x+\beta _{0})x+\beta _{1},\quad P(x)=(y+x+\beta _{2})y+\beta _{3},

जहां मान $\beta _{0},\dots ,\beta _{3}$ के आधार पर अग्रिम गणना की जाती है $a_{0},\dots ,a_{3}$ .हॉर्नर के 4 के सापेक्ष में मोट्ज़किन की विधि केवल 3 गुणन का उपयोग करती है।

प्रत्येक के लिए मान $\beta _{i}$ विस्तार करके आसानी से परिकलित किया जा सकता है $P(x)$ और गुणांकों की समान करना:

{\begin{aligned}\beta _{0}&={\tfrac {1}{2}}(a_{3}-1),\quad &z&=a_{2}-\beta _{0}(\beta _{0}+1),\quad &\beta _{1}&=a_{1}-\beta _{0}z,\\\beta _{2}&=z-2\beta _{1},\quad &\beta _{3}&=a_{0}-\beta _{1}(\beta _{1}+\beta _{2}).\end{aligned}}

उदाहरण

टेलर विस्तार की गणना करने के लिए $\exp(x)\approx 1+x+x^{2}/2+x^{3}/6+x^{4}/24$ , हम एक कारक को 24 तक बढ़ा सकते हैं, उपरोक्त चरणों को प्रारंभ कर सकते हैं, और स्केल वापस कर सकते हैं।यह हमें तीन बार गुणन संगणना देता है

y=(x+1.5)x+11.625,\quad P(x)=(y+x-15)y/24+2.63477.

समतुल्य हॉर्नर फॉर्म में सुधार (यानी $P(x)=1+x(1+x(1/2+x(1/6+x/24)))$ ) 1 गुणन द्वारा।

कुछ सामान्य विधियों में नुथ-ईव एल्गोरिथम और राबिन-विनोग्राद एल्गोरिथम समिम्लित हैं।

बहु बिंदु मूल्यांकन

एक $n$ -डिग्री बहुपद और $P(x)$ तथा कई बिंदुओं का मूल्यांकन $x_{1},\dots ,x_{m}$ से किया जा सकता है हॉर्नर विधि का उपयोग करके $mn$ का गुणन $m$ बार किया जाता हैं। प्रीप्रोसेसिंग दृष्टिकोण का उपरोक्त उपयोग करके, इसे दो के कारक से न्यूनतम, अर्थात $mn/2$ गुणन किया जा सकता है। यद्यपि , बेहतर करना संभव है।

समय की आवश्यकता को न्यूनतम करना संभव है $O{\big (}(n+m)\log ^{2}(n+m){\big )}$ .^[3]वो सिद्धांत जो दो बहुपदों को परिभाषित करता है तथा जो क्रमशः पहले और दूसरे भाग में शून्य हैं: $m_{0}(x)=(x-x_{1})\cdots (x-x_{n/2})$ और $m_{1}(x)=(x-x_{n/2+1})\cdots (x-x_{n})$ .हम पुनः गणना करते हैं $R_{0}=P{\bmod {m}}_{0}$ और $R_{1}=P{\bmod {m}}_{1}$ बहुपद विभाजन का उपयोग करके, जो में किया जा सकता है $O(n\log n)$ एक तीव्र फूरियर रूपांतरण का उपयोग करते समय हुए। इसका मतलब यह है $P(x)=Q(x)m_{0}(x)+R_{0}(x)$ और $P(x)=Q(x)m_{1}(x)+R_{1}(x)$ निर्माण द्वारा, कहाँ $R_{0}$ और $R_{1}$ अधिक से अधिक डिग्री के बहुपद हैं $n/2$ .किसका कारण $m_{0}$ और $m_{1}$ परिभाषित किया गया था, और हमारे पास है

{\begin{aligned}R_{0}(x_{i})&=P(x_{i})\quad {\text{for }}i\leq n/2\quad {\text{and}}\\R_{1}(x_{i})&=P(x_{i})\quad {\text{for }}i>n/2.\end{aligned}}

इस प्रकार गणना करने के लिए $P$ सब पर $n$ की $x_{i}$ , यह छोटे बहुपदों की गणना करने के लिए पर्याप्त है $R_{0}$ और $R_{1}$ प्रत्येक आधे अंक पर। यह हमें एक फूट डालो और जीतो एल्गोरिथम देता है $T(n)=2T(n/2)+n\log n$ , जो ये दर्शाता हे $T(n)=O(n(\log n)^{2})$ मास्टर प्रमेय (एल्गोरिदम का विश्लेषण) द्वारा।

ऐसे इस्थिति में जहां जिन बिंदुओं पर हम बहुपदों का मूल्यांकन करना चाहते हैं, उनकी कुछ संरचना है, सरल तरीके मौजूद हैं। उदाहरण के लिए, नुथ^[4] खंड 4.6.4 प्रकार के बहुपद मानों को सारणीबद्ध करने के लिए एक विधि देता है

P(x_{0}+h),P(x_{0}+2h),\dots .

गतिशील मूल्यांकन

इस्थिति में जहां $x_{1},\dots ,x_{m}$ पहले से पता नहीं होता, केदलया और उमंस^[5] आकार के परिमित क्षेत्र में बहुपदों के मूल्यांकन के लिए एक डेटा संरचना प्रदान की $F_{q}$ समय के भीतर $(\log n)^{O(1)}(\log _{2}q)^{1+o(1)}$ कुछ प्रारंभिक प्रीप्रोसेसिंग के बाद प्रति मूल्यांकन। यह कैस्पर ग्रीन लार्सन द्वारा दिखाया गया था^[6] अनिवार्य रूप से इष्टतम होना।

विचार रूपांतरित करना है $P(x)$ डिग्री का $n$ एक बहुभिन्नरूपी बहुपद में $f(x_{1},x_{2},\dots ,x_{m})$ , ऐसा है कि $P(x)=f(x,x^{d},x^{d^{2}},\dots ,x^{d^{m}})$ और व्यक्तिगत डिग्री $f$ अधिक से अधिक है $d$ . चूंकि यह खत्म हो गया है ${\bmod {q}}$ , सबसे बड़ा मूल्य $f$ ले सकता है (ओवर $\mathbb {Z}$ ) है $M=d^{m}(q-1)^{dm}$ . चीनी शेष प्रमेय का उपयोग करना, यह मूल्यांकन करने के लिए पर्याप्त है $f$ मॉड्यूलो विभिन्न प्राइम्स $p_{1},\dots ,p_{\ell }$ एक उत्पाद के सापेक्ष न्यूनतम से न्यूनतम $M$ . प्रत्येक प्रधान को मोटे तौर पर लिया जा सकता है $\log M=O(dm\log q)$ , और आवश्यक अभाज्य संख्याओं की संख्या, $\ell$ , लगभग समान है। इस प्रक्रिया को पुनरावर्ती रूप से करते हुए, हम अभाज्य संख्या जितनी छोटी प्राप्त कर सकते हैं $\log \log q$ . इसका मतलब है कि हम गणना और स्टोर कर सकते हैं $f$ में सभी संभावित मूल्यों पर $T=(\log \log q)^{m}$ समय और स्थान। अगर हम लेते हैं $d=\log q$ , हम पाते हैं $m={\tfrac {\log n}{\log \log q}}$ , इसलिए समय/स्थान की आवश्यकता उचित है $n^{\frac {\log \log q}{\log \log \log q}}.$ Kedlaya और Umans आगे दिखाते हैं कि इस प्रीप्रोसेसिंग को तीव्ऱ (FFT) मल्टीपॉइंट मूल्यांकन के सापेक्ष कैसे जोड़ा जाए। यह बहुपद मॉड्यूलर रचना जैसे कई महत्वपूर्ण बीजगणितीय समस्याओं के लिए इष्टतम एल्गोरिदम की अनुमति देता है।

विशिष्ट बहुपद

जबकि सामान्य बहुपदों की आवश्यकता होती है $\Omega (n)$ संचालन का मूल्यांकन करने के लिए, कुछ बहुपदों की गणना बहुत तीव्री से की जा सकती है। उदाहरण के लिए, बहुपद $P(x)=x^{2}+2x+1$ केवल एक गुणन और एक जोड़ का उपयोग करके गणना की जा सकती है $P(x)=(x+1)^{2}$

शक्तियों का मूल्यांकन

एक विशेष रूप से दिलचस्प प्रकार का बहुपद घात $x^{n}$ है .ऐसे बहुपदों की सदैव गणना $O(\log n)$ संचालन की जा सकती है।मान लीजिए, उदाहरण के लिए, हमें $x^{16}$ गणना करने की आवश्यकता है ; हम बस $x$ और गुणा करें $x$ प्राप्त करने $x^{2}$ . के सापेक्ष प्रारंभ कर सकते हैं इसके उपरांत हम $x^{4}$ से केवल चार गुणा में $x^{8}$ और $x^{16}$ को प्राप्त करने के लिए उसी से गुणा कर सकते हैं ।अन्य घातांक जैसे $x^{5}$ इसी तरह पहली कंप्यूटिंग द्वारा $x^{4}$ 2 गुणा करके और पुनः गुणा करके $x$ . कुशलतापूर्वक गणना की जा सकती है।

किसी दी गई घातांक की गणना करने का सबसे कुशल विधि $x^{n}$ अतिरिक्त-श्रृंखला घातांक द्वारा प्रदान किया जाता है। यद्यपि , इसके लिए प्रत्येक प्रतिपादक के लिए एक विशिष्ट एल्गोरिदम प्रारूपित करने की आवश्यकता होती है, और इन एल्गोरिदम को प्रारूपित करने के लिए आवश्यक गणना कठिन होती है, इसलिए प्रभावी संगणनाओं के लिए सामान्यतःः पर वर्ग द्वारा घातांक को प्राथमिकता दी जाती है।

बहुपद परिवार

सामान्यतः बहुपद प्रसिद्ध रूप से $a_{n}x^{n}+\dots +a_{1}x+a_{0}$ भिन्न रूप में दिखाई देते हैं .चेबिशेव रूप में बहुपदों के लिए हम क्लेंशॉ एल्गोरिथम का उपयोग कर सकते हैं।बेजियर रूप में बहुपदों के लिए हम डी कास्टलजौ के एल्गोरिदम का उपयोग कर सकते हैं,और बी-स्प्लिंस के लिए डी बूर का एल्गोरिदम है।

कठिन बहुपद

तथ्य यह है कि कुछ बहुपदों की गणना सामान्य बहुपदों की सापेक्ष में काफी तीव्रता से की जा सकती है, यह प्रश्न सुझाता है: क्या हम एक साधारण बहुपद का उदाहरण दे सकते हैं जिसकी गणना इसकी डिग्री से बहुत न्यूनतम समय में नहीं की जा सकती है? वोल्कर स्ट्रास ने दर्शाया है^[7] कि बहुपद

P(x)=\sum _{k=0}^{n}2^{2^{kn^{3}}}x^{k}

से न्यूनतम के द्वारा ${\tfrac {1}{2}}n-2$ गुणन और $n-4$ जोड़ का मूल्यांकन नहीं किया जा सकता है ।न्यूनतम से न्यूनतम यह बाध्यता धारण करती है यदि केवल $<n^{2}/\log n$ . प्रकार के संचालन की अनुमति दी जाती है, जो लंबाई की तथाकथित बहुपद श्रृंखला को जन्म देती है

स्ट्रैसन द्वारा दिए गए बहुपद में बहुत बड़े गुणांक हैं, परंतु संभाव्य विधियों से कि केवल 0 और 1 के गुणांक वाले बहुपदों का अस्तित्व होना चाहिए, जो कोई भी दर्शा सकता है जैसे कि मूल्यांकन के लिए न्यूनतम से न्यूनतम आवश्यकता होती है $\Omega (n/\log n)$ गुणन की।^[8]

अन्य साधारण बहुपदों के लिए, जटिलता अज्ञात है।बहुपद $(x+1)(x+2)\cdots (x+n)$ समय $(\log n)^{c}$ किसी के लिए $c$ . पर गणना करने योग्य नहीं होने का अनुमान है यह इस तथ्य से समर्थित है, कि यदि इसकी तीव्रता से गणना की जा सकती है, तो RSA (क्रिप्टोसिस्टम) को तोड़ते हुए बहुपद समय में पूर्णांक गुणनखंड की गणना की जा सकती है।^[9]

मैट्रिक्स बहुपद

कभी-कभी अदिश गुणन की न्यूनतम कम्प्यूटेशनल लागत (जैसे $ax$ )गैर अदिश गुणन की न्यूनतम कम्प्यूटेशनल लागत से न्यूनतम है (जैसे $x^{2}$ ).इसका विशिष्ट उदाहरण मैट्रिसेस है। $M$ एक $m\times m$ मैट्रिक्स में, एक अदिश गुणन लगभग $aM$ और $m^{2}$ गणना करते समय $M^{2}$ अंकगणितीय संचालन लगभग $m^{3}$ लगते हैं

उदाहरण के लिए मैट्रिक्स घातांक की गणना के लिए मैट्रिक्स बहुपद महत्वपूर्ण हैं।

पैटर्सन और स्टॉन्यूनतमेयर ^[10] ने दर्शाया की डिग्री की गणना कैसे की जाती हैं $O({\sqrt {n}})$ गैर अदिश गुणन और $O(n)$ अदिश गुणन केवल $n$ बहुपद का उपयोग करती हैं।इस प्रकार डिग्री $n$ के एक मैट्रिक्स बहुपद $O(m^{2.3}{\sqrt {n}}+m^{2}n)$ का समय मूल्यांकन किया जा सकता है। अगर $m=n$ से $O(n^{3})$ न्यूनतम है ,तो मानक एल्गोरिथम के सापेक्ष एकल मैट्रिक्स गुणन से तीव्र हैं।

यह विधि इस प्रकार काम करती है: एक बहुपद के लिए

P(M)=a_{n-1}M^{n-1}+\dots +a_{1}M+a_{0}I,

मान लीजिए $k$ सबसे छोटा पूर्णांक है जो इससे ${\sqrt {n}}.$ छोटा नही है , $M,M^{2},\dots ,M^{k}$ घातांक के सापेक्ष गणना की जाती है $k$ मैट्रिक्स गुणन, और $M^{k}.$ द्वारा $M^{2k},M^{3k},\dots ,M^{k^{2}-k}$ की बार-बार गुणा करके गणना की जाती है अब,

{\begin{aligned}P(M)=&\,(a_{0}I+a_{1}M+\dots +a_{k-1}M^{k-1})\\+&\,(a_{k}I+a_{k+1}M+\dots +a_{2k-1}M^{k-1})M^{k}\\+&\,\dots \\+&\,(a_{n-k}I+a_{n-k+1}M+\dots +a_{n-1}M^{k-1})M^{k^{2}-k},\end{aligned}}

,

जहाँ $a_{i}=0$ के लिए $i \geq n$ है.इसके लिए बस $k$ अधिक गैर-अदिश गुणन की आवश्यकता है।

क्रोनकर उत्पाद का उपयोग करके हम इसे संक्षेप में लिख सकते हैं:

P(M)={\begin{bmatrix}I\\M\\\vdots \\M^{k-1}\end{bmatrix}}^{T}\left({\begin{bmatrix}a_{0}&a_{1}&a_{2}&\dots \\a_{k}&a_{k+1}&\ddots \\a_{2k}&\ddots \\\vdots \end{bmatrix}}\otimes I\right){\begin{bmatrix}I\\M^{k}\\M^{2k}\\\vdots \end{bmatrix}}

.

इस पद्धति का प्रत्यक्ष अनुप्रयोग का उपयोग $2{\sqrt {n}}$ गैर-अदिश गुणन करता है , परंतु इसे बहुपद मूल्यांकन के सापेक्ष जोड़कर, पैटर्सन और स्टॉन्यूनतमेयर को दर्शाते हैं कि आप ${\sqrt {2n}}$ को न्यूनतम कर सकते हैं

यह भी देखें

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

संदर्भ

↑ Carnicer, J.; Gasca, M. (1990). "बहुभिन्नरूपी बहुपदों और उनके डेरिवेटिव का मूल्यांकन". Mathematics of Computation. 54 (189): 231–243. doi:10.2307/2008692.
↑ Motzkin, T. S. (1955). "बहुपदों का मूल्यांकन और तर्कसंगत कार्यों का मूल्यांकन". Bulletin of the American Mathematical Society. 61 (163): 10.
↑ Von Zur Gathen, Joachim; Jürgen, Gerhard (2013). आधुनिक कंप्यूटर बीजगणित. Cambridge University Press. Chapter 10. ISBN 9781139856065.
↑ Knuth, Donald (2005). Art of Computer Programming. Vol. 2: Seminumerical Algorithms. Addison-Wesley. ISBN 9780201853926.
↑ Kedlaya, Kiran S.; Umans, Christopher (2011). "तेजी से बहुपद गुणनखंडन और मॉड्यूलर रचना". SIAM Journal on Computing. 40 (6): 1767–1802. doi:10.1137/08073408x. hdl:1721.1/71792.
↑ Larsen, K. G. (2012). "उच्च सेल जांच बहुपदों के मूल्यांकन के लिए निचली सीमा". Symposium on Foundations of Computer Science. IEEE. 53: 293–301. doi:10.1109/FOCS.2012.21.
↑ Strassen, Volker (1974). "परिमेय गुणांक वाले बहुपद जिनकी गणना करना कठिन है". SIAM Journal on Computing (in English). 3 (2): 128–149. doi:10.1137/0203010.
↑ Schnorr, C. P. (1979), "On the additive complexity of polynomials and some new lower bounds", Theoretical Computer Science, Springer, vol. 67, pp. 286–297, doi:10.1007/3-540-09118-1_30
↑ Chen, Xi, Neeraj Kayal, and Avi Wigderson. Partial derivatives in arithmetic complexity and beyond. Now Publishers Inc, 2011.
↑ Paterson, Michael S.; Stockmeyer, Larry J. (1973). "बहुपदों का मूल्यांकन करने के लिए आवश्यक नॉनस्केलर गुणन की संख्या पर". SIAM Journal on Computing (in English). 2 (1): 60–66. doi:10.1137/0202007.

[1] Carnicer, J.; Gasca, M. (1990). "बहुभिन्नरूपी बहुपदों और उनके डेरिवेटिव का मूल्यांकन". Mathematics of Computation. 54 (189): 231–243. doi:10.2307/2008692.

[2] Motzkin, T. S. (1955). "बहुपदों का मूल्यांकन और तर्कसंगत कार्यों का मूल्यांकन". Bulletin of the American Mathematical Society. 61 (163): 10.

[3] Von Zur Gathen, Joachim; Jürgen, Gerhard (2013). आधुनिक कंप्यूटर बीजगणित. Cambridge University Press. Chapter 10. ISBN 9781139856065.

[4] Knuth, Donald (2005). Art of Computer Programming. Vol. 2: Seminumerical Algorithms. Addison-Wesley. ISBN 9780201853926.

[5] Kedlaya, Kiran S.; Umans, Christopher (2011). "तेजी से बहुपद गुणनखंडन और मॉड्यूलर रचना". SIAM Journal on Computing. 40 (6): 1767–1802. doi:10.1137/08073408x. hdl:1721.1/71792.

[6] Larsen, K. G. (2012). "उच्च सेल जांच बहुपदों के मूल्यांकन के लिए निचली सीमा". Symposium on Foundations of Computer Science. IEEE. 53: 293–301. doi:10.1109/FOCS.2012.21.

[7] Strassen, Volker (1974). "परिमेय गुणांक वाले बहुपद जिनकी गणना करना कठिन है". SIAM Journal on Computing (in English). 3 (2): 128–149. doi:10.1137/0203010.

[8] Schnorr, C. P. (1979), "On the additive complexity of polynomials and some new lower bounds", Theoretical Computer Science, Springer, vol. 67, pp. 286–297, doi:10.1007/3-540-09118-1_30

[9] Chen, Xi, Neeraj Kayal, and Avi Wigderson. Partial derivatives in arithmetic complexity and beyond. Now Publishers Inc, 2011.

[10] Paterson, Michael S.; Stockmeyer, Larry J. (1973). "बहुपदों का मूल्यांकन करने के लिए आवश्यक नॉनस्केलर गुणन की संख्या पर". SIAM Journal on Computing (in English). 2 (1): 60–66. doi:10.1137/0202007.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ Line 1: / Line 1: @@
 {{short description|Algorithms for polynomial evaluation}}
-गणित और [[कंप्यूटर विज्ञान]] में, [[बहुपद]] मूल्यांकन एक बहुपद के मूल्य की गणना को संदर्भित करता है तथा इसके [[अनिश्चित (चर)|अनिश्चित चर]] को कुछ मूल्यों के लिए प्रतिस्थापित किया जाता है। दूसरे शब्दों में, बहुपद के मूल्यांकन <math>P(x_1, x_2) = 2x_1x_2 + x_1^3 + 4</math> पर <math>x_1=2, x_2=3</math>, <math>P(2,3)= 2\cdot 2\cdot 3 + 2^3+4=24.</math> में कंप्यूटिंग समिम्लित है,तथा {{slink| बहुपद वलय | बहुपद मूल्यांकन}} भी देखें
+गणित और [[कंप्यूटर विज्ञान]] में, [[बहुपद]] मूल्यांकन एक बहुपद के मूल्य की गणना को संदर्भित करता है तथा इसके [[अनिश्चित (चर)|अनिश्चित चर]] को कुछ मूल्यों के लिए प्रतिस्थापित किया जाता है। दूसरे शब्दों में, बहुपद के मूल्यांकन <math>P(x_1, x_2) = 2x_1x_2 + x_1^3 + 4</math> पर <math>x_1=2, x_2=3</math> को <math>P(2,3)= 2\cdot 2\cdot 3 + 2^3+4=24.</math> को कंप्यूटिंग में समिम्लित किया जाता है,तथा {{slink| बहुपद वलय | बहुपद मूल्यांकन}} भी दर्शाया गया है
 [[अविभाज्य बहुपद]] के मूल्यांकन के लिए <math>a_nx^n+a_{n-1}x^{n-1}+\cdots +a_0,</math> सबसे सरल विधि का उपयोग करेंगे <math>n</math> गुणन की गणना करने के लिए  <math>a_n x^n</math>, का,तथा  <math>n-1</math> गुणन की गणना करने के लिए  <math>a_{n-1} x^{n-1}</math> उपयोग करेंगे और इसी तरह कुल मिलाकर <math>\tfrac{n(n+1)}{2}</math> से गुणन करेंगेऔर <math>n</math> को जोड़ देंगे।हॉर्नर के नियम जैसे बेहतर विधियों का उपयोग करके  <math>n</math> गुणन और <math>n</math> जोड़ को न्यूनतम किया जा सकता है। यदि कुछ प्रीप्रोसेसिंग की अनुमति दी जाती है, तो और भी बचत संभव है।
 == पृष्ठभूमि ==
-अभ्यास में यह समस्या सामान्यतया उत्पन्न होती है। [[कम्प्यूटेशनल ज्यामिति]] में, [[टेलर बहुपद|टेलर बहुपदों]] का उपयोग करके फ़ंक्शन सन्निकटन की गणना करने के लिए बहुपदों का उपयोग किया जाता है। [[क्रिप्टोग्राफी]] और [[हैश तालिका]] में, [[के-स्वतंत्र हैशिंग|k-स्वतंत्र हैशिंग]] की गणना करने के लिए बहुपद का उपयोग किया जाता है।
+अभ्यास में यह समस्या सामान्यतःः उत्पन्न होती है। [[कम्प्यूटेशनल ज्यामिति|न्यूनतम्प्यूटेशनल ज्यामिति]] में, [[टेलर बहुपद|टेलर बहुपदों]] का उपयोग करके फ़ंक्शन सन्निकटन की गणना करने के लिए बहुपदों का उपयोग किया जाता है। [[क्रिप्टोग्राफी]] और [[हैश तालिका]] में, [[के-स्वतंत्र हैशिंग|k-स्वतंत्र हैशिंग]] की गणना करने के लिए बहुपद का उपयोग किया जाता है।
-पूर्व स्थिति में, फ्लोटिंग-पॉइंट अंकगणित का उपयोग करके बहुपदों का मूल्यांकन किया जाता है, जो सटीक नहीं है। इस प्रकार, मूल्यांकन के लिए भिन्न-भिन्न योजनाएँ, सामान्य तौर पर, थोड़ा विभिन्न उत्तर देंगी। उपरांत वाले स्थिति में, बहुपदों का मूल्यांकन सामान्यत पर [[परिमित क्षेत्र]] में किया जाता है, इस स्थिति में उत्तर सदैव सटीक होते हैं।
+पूर्व स्थिति में, फ्लोटिंग-पॉइंट अंकगणित का उपयोग करके बहुपदों का मूल्यांकन किया जाता है, जो सटीक नहीं है। इस प्रकार, मूल्यांकन के लिए भिन्न-भिन्न योजनाएँ, सामान्य तौर पर, थोड़ा विभिन्न उत्तर देंगी। उपरांत वाले स्थिति में, बहुपदों का मूल्यांकन सामान्यतः [[परिमित क्षेत्र]] में किया जाता है, इस स्थिति में उत्तर सदैव सटीक होते हैं।
 == सामान्य विधि ==
@@ Line 15: / Line 15: @@
 {{see also|हॉर्नर की विधि}}
-हॉर्नर की विधि बार-बार ब्रैकेटिंग का उपयोग करके बहुपद का मूल्यांकन करती है:
+हॉर्नर विधि बार-बार ब्रैकेटिंग का उपयोग करके बहुपद का मूल्यांकन करती है:
 <math display="block">\begin{align}
 a_0 + &a_1x + a_2x^2 + a_3x^3 + \cdots + a_nx^n \\
   &= a_0 + x \bigg(a_1 + x \Big(a_2 + x \big(a_3 + \cdots + x(a_{n-1} + x\,a_n) \cdots \big) \Big) \bigg).
 \end{align}</math>
-यह विधि गुणन और जोड़ की संख्या को घटाकर केवल कर देती है <math>n</math>
+यह विधि गुणन और जोड़ की संख्या को घटाकर केवल <math>n</math> कर देती है ,
-हॉर्नर की विधि इतनी सामान्य है कि कई कंप्यूटर प्रोसेसर में एक कंप्यूटर निर्देश गुणा-जमा ऑपरेशन जोड़ा गया है, जो एक संयुक्त चरण में जोड़ और गुणा संचालन करने की अनुमति देता है।
+हॉर्नर विधि इतनी सामान्य है,कि कई कंप्यूटर प्रोसेसर में एक कंप्यूटर निर्देश गुणा-संचय ऑपरेशन जोड़ा गया है, जो एक संयुक्त चरण में जोड़ और गुणा ऑपरेशन करने की अनुमति देता है।
 ==== बहुभिन्नरूपी ====
-यदि बहुपद बहुभिन्नरूपी है, तो हॉर्नर के नियम को चर के कुछ क्रम पर पुनरावर्ती रूप से लागू किया जा सकता है।
+यदि बहुपद बहुभिन्नरूपी है, तो हॉर्नर के नियम को चर के कुछ क्रम पर पुनरावर्ती रूप से प्रारंभ किया जा सकता है।
-उदा.
+उदाहरण.
 :<math>P(x, y) = 4 + x + 2 x y + 2 x^2 y + x^2 y^2</math>
-रूप में लिखा जा सकता है
+के रूप में लिखा जा सकता है
 :<math>\begin{align}
 P(x, y) &= 4 + x (1 + y(2) + x (y(2 + y)))
@@ Line 38: / Line 40: @@
 ==== एस्ट्रिन की योजना ====
-{{see also|Estrin's scheme}}
+{{see also|एस्ट्रिन की योजना}}
-हालांकि हॉर्नर के नियम (प्रीप्रोसेसिंग के बिना) की तुलना में कम संगणना करना संभव नहीं है, आधुनिक कंप्यूटरों पर मूल्यांकन का क्रम कम्प्यूटेशनल दक्षता के लिए बहुत मायने रख सकता है।
+यद्यपि  हॉर्नर के नियम की सापेक्ष में न्यूनतम संगणना करना संभव नहीं है, आधुनिक कंप्यूटरों पर मूल्यांकन का क्रम न्यूनतम्प्यूटेशनल दक्षता के लिए बहुत मायने रख सकता है।
-एस्ट्रिन की योजना के रूप में जाना जाने वाला एक तरीका पेड़ जैसे पैटर्न में एक (एकल भिन्न) बहुपद की गणना करता है:
+एस्ट्रिन की योजना के रूप में जाना जाने वाला एक विधि पेड़ जैसे पैटर्न में एक बहुपद की गणना करता है:
 <math display="block">\begin{align}
 P(x) = (a_0 + a_1 x) + (a_2 + a_3 x) x^2 + ((a_4 + a_5 x) + (a_6 + a_7 x) x^2)x^4.
 \end{align}</math>
-वर्ग द्वारा घातांक द्वारा संयुक्त, यह संगणना को समानांतर करने की अनुमति देता है।
+वर्ग और घातांक द्वारा संयुक्त संगणना को समानांतर करने की अनुमति देता है।
-=== प्रीप्रोसेसिंग के साथ मूल्यांकन ===
+=== प्रीप्रोसेसिंग के सापेक्ष मूल्यांकन ===
-मनमाने बहुपदों का मूल्यांकन कम के साथ किया जा सकता है
+मनमाने बहुपदों का मूल्यांकन न्यूनतम के सापेक्ष किया जा सकता है अगर हम पहले प्रीप्रोसेस करते हैं तो हॉर्नर के नियम की सापेक्ष में संचालन की आवश्यकता होती है गुणांक <math>a_n, \dots, a_0</math>.
-अगर हम पहले प्रीप्रोसेस करते हैं तो हॉर्नर के नियम की तुलना में संचालन की आवश्यकता होती है
-गुणांक <math>a_n, \dots, a_0</math>.
-एक उदाहरण सबसे पहले Motzkin ने दिया था<ref>{{Cite journal|last=Motzkin|first=T. S.|date=1955|title=बहुपदों का मूल्यांकन और तर्कसंगत कार्यों का मूल्यांकन|journal=[[Bulletin of the American Mathematical Society]]|volume=61|issue=163|pages=10|issn=}}</ref> जिसने नोट किया
+एक उदाहरण सबसे पहले मोट्ज़किन ने दिया था<ref>{{Cite journal|last=Motzkin|first=T. S.|date=1955|title=बहुपदों का मूल्यांकन और तर्कसंगत कार्यों का मूल्यांकन|journal=[[Bulletin of the American Mathematical Society]]|volume=61|issue=163|pages=10|issn=}}</ref> जिन्होंने यह नोट किया था
 :<math>P(x)=x^4 + a_3 x^3 + a_2 x^2 + a_1 x + a_0</math>
-रूप में लिखा जा सकता है
+के रूप में लिखा जा सकता है
 :<math>y = (x+\beta_0)x+\beta_1,\quad P(x)=(y+x+\beta_2)y+\beta_3,</math>
-जहां मान <math>\beta_0, \dots, \beta_3</math> के आधार पर अग्रिम गणना की जाती है <math>a_0, \dots, a_3</math>.
+जहां मान <math>\beta_0, \dots, \beta_3</math> के आधार पर अग्रिम गणना की जाती है <math>a_0, \dots, a_3</math>.हॉर्नर के 4 के सापेक्ष में मोट्ज़किन की विधि केवल 3 गुणन का उपयोग करती है।
-हॉर्नर के 4 की तुलना में मोट्ज़किन की विधि केवल 3 गुणन का उपयोग करती है।
-प्रत्येक के लिए मान <math>\beta_i</math> विस्तार करके आसानी से परिकलित किया जा सकता है <math>P(x)</math> और गुणांकों की बराबरी करना:
+प्रत्येक के लिए मान <math>\beta_i</math> विस्तार करके आसानी से परिकलित किया जा सकता है <math>P(x)</math> और गुणांकों की समान करना:
 :<math>\begin{align}
 \beta_0&=\tfrac12(a_3-1),\quad
@@ Line 72: / Line 71: @@
 ==== उदाहरण ====
-[[टेलर विस्तार]] की गणना करने के लिए <math>\exp(x) \approx 1+x+x^2/2+x^3/6+x^4/24</math>,
+[[टेलर विस्तार]] की गणना करने के लिए <math>\exp(x) \approx 1+x+x^2/2+x^3/6+x^4/24</math>, हम एक कारक को 24 तक बढ़ा सकते हैं, उपरोक्त चरणों को प्रारंभ कर सकते हैं, और स्केल वापस कर सकते हैं।यह हमें तीन बार गुणन संगणना देता है
-हम एक कारक 24 तक बढ़ा सकते हैं, उपरोक्त चरणों को लागू कर सकते हैं, और वापस स्केल कर सकते हैं।
-यह हमें तीन गुणन संगणना देता है
 :<math>y = (x+1.5)x+11.625,\quad P(x)=(y+x-15)y/24+2.63477.</math>
 समतुल्य हॉर्नर फॉर्म में सुधार (यानी <math>P(x) = 1 + x (1 + x (1/2 + x(1/6 + x/24)))</math>) 1 गुणन द्वारा।
-कुछ सामान्य विधियों में [[नुथ-ईव एल्गोरिथम]] और [[राबिन-विनोग्राद एल्गोरिथम]] समिम्लितहैं।
+कुछ सामान्य विधियों में [[नुथ-ईव एल्गोरिथम]] और [[राबिन-विनोग्राद एल्गोरिथम]] समिम्लित हैं।
 === बहु बिंदु मूल्यांकन ===
-ए का मूल्यांकन करें <math>n</math>-डिग्री बहुपद <math>P(x)</math> कई बिंदुओं में <math>x_1, \dots, x_m</math> से किया जा सकता है <math>mn</math> हॉर्नर की विधि का उपयोग करके गुणन <math>m</math> बार। उपरोक्त प्रीप्रोसेसिंग दृष्टिकोण का उपयोग करके, इसे दो के कारक से कम किया जा सकता है, अर्थात <math>mn/2</math> गुणन। हालांकि, बेहतर करना संभव है।
+एक  <math>n</math>-डिग्री बहुपद  और <math>P(x)</math>  तथा कई बिंदुओं का मूल्यांकन  <math>x_1, \dots, x_m</math> से किया जा सकता है  हॉर्नर  विधि का उपयोग करके <math>mn</math> का गुणन <math>m</math> बार किया जाता हैं। प्रीप्रोसेसिंग दृष्टिकोण का  उपरोक्त उपयोग करके, इसे दो के कारक से न्यूनतम, अर्थात <math>mn/2</math> गुणन किया जा सकता है। यद्यपि , बेहतर करना संभव है।
-समय की आवश्यकता को कम करना संभव है <math>O\big((n + m) \log^2(n + m)\big)</math>.<ref>{{cite book |last1=Von Zur Gathen |first1=Joachim |title=आधुनिक कंप्यूटर बीजगणित|last2=Jürgen |first2=Gerhard |publisher=[[Cambridge University Press]] |year=2013 |isbn=9781139856065 |at=Chapter 10 |author-link=Joachim von zur Gathen}}</ref>
-विचार दो बहुपदों को परिभाषित करना है जो क्रमशः पहले और दूसरे भाग में शून्य हैं: <math>m_0(x)=(x-x_1)\cdots(x-x_{n/2})</math> और <math>m_1(x)=(x-x_{n/2+1})\cdots(x-x_{n})</math>.
+समय की आवश्यकता को न्यूनतम करना संभव है <math>O\big((n + m) \log^2(n + m)\big)</math>.<ref>{{cite book |last1=Von Zur Gathen |first1=Joachim |title=आधुनिक कंप्यूटर बीजगणित|last2=Jürgen |first2=Gerhard |publisher=[[Cambridge University Press]] |year=2013 |isbn=9781139856065 |at=Chapter 10 |author-link=Joachim von zur Gathen}}</ref>वो सिद्धांत जो दो बहुपदों को परिभाषित करता है तथा जो क्रमशः पहले और दूसरे भाग में शून्य हैं:<math>m_0(x)=(x-x_1)\cdots(x-x_{n/2})</math> और <math>m_1(x)=(x-x_{n/2+1})\cdots(x-x_{n})</math>.हम पुनः गणना करते हैं <math>R_0 = P \bmod m_0</math> और <math>R_1 = P \bmod m_1</math> [[बहुपद विभाजन]] का उपयोग करके, जो में किया जा सकता है <math>O(n\log n)</math> एक तीव्र फूरियर रूपांतरण का उपयोग करते समय हुए। इसका मतलब यह है <math>P(x) = Q(x)m_0(x) + R_0(x)</math> और <math>P(x) = Q(x)m_1(x) + R_1(x)</math> निर्माण द्वारा, कहाँ <math>R_0</math> और <math>R_1</math> अधिक से अधिक डिग्री के बहुपद हैं <math>n/2</math>.किसका कारण <math>m_0</math> और <math>m_1</math> परिभाषित किया गया था, और हमारे पास है
-हम फिर गणना करते हैं <math>R_0 = P \bmod m_0</math> और <math>R_1 = P \bmod m_1</math> [[बहुपद विभाजन]] का उपयोग करके, जो में किया जा सकता है <math>O(n\log n)</math> एक तेज फूरियर रूपांतरण का उपयोग करते हुए समय।
-इसका मतलब यह है <math>P(x) = Q(x)m_0(x) + R_0(x)</math> और <math>P(x) = Q(x)m_1(x) + R_1(x)</math> निर्माण द्वारा, कहाँ <math>R_0</math> और <math>R_1</math> अधिक से अधिक डिग्री के बहुपद हैं <math>n/2</math>.
-कैसे के कारण <math>m_0</math> और <math>m_1</math> परिभाषित किया गया था, हमारे पास है
 :<math>\begin{align}
 R_0(x_i) &= P(x_i) \quad\text{for } i \le n/2 \quad\text{and}\\
@@ Line 94: / Line 88: @@
 इस प्रकार गणना करने के लिए <math>P</math> सब पर <math>n</math> की <math>x_i</math>, यह छोटे बहुपदों की गणना करने के लिए पर्याप्त है <math>R_0</math> और <math>R_1</math> प्रत्येक आधे अंक पर।
 यह हमें एक फूट डालो और जीतो एल्गोरिथम देता है <math>T(n) = 2T(n/2) + n\log n</math>, जो ये दर्शाता हे <math>T(n)=O(n(\log n)^2)</math> [[मास्टर प्रमेय (एल्गोरिदम का विश्लेषण)]] द्वारा।
@@ Line 110: / Line 105: @@
 विचार रूपांतरित करना है <math>P(x)</math> डिग्री का <math>n</math> एक [[बहुभिन्नरूपी बहुपद]] में <math>f(x_1, x_2, \dots, x_m)</math>, ऐसा है कि <math>P(x) = f(x, x^d, x^{d^2}, \dots, x^{d^m})</math> और व्यक्तिगत डिग्री <math>f</math> अधिक से अधिक है <math>d</math>.
 चूंकि यह खत्म हो गया है <math>\bmod q</math>, सबसे बड़ा मूल्य <math>f</math> ले सकता है (ओवर <math>\mathbb Z</math>) है <math>M = d^m (q-1)^{dm}</math>.
-[[चीनी शेष प्रमेय]] का उपयोग करना, यह मूल्यांकन करने के लिए पर्याप्त है <math>f</math> मॉड्यूलो विभिन्न प्राइम्स <math>p_1, \dots, p_\ell</math> एक उत्पाद के साथ कम से कम <math>M</math>.
+[[चीनी शेष प्रमेय]] का उपयोग करना, यह मूल्यांकन करने के लिए पर्याप्त है <math>f</math> मॉड्यूलो विभिन्न प्राइम्स <math>p_1, \dots, p_\ell</math> एक उत्पाद के सापेक्ष न्यूनतम से न्यूनतम <math>M</math>.
 प्रत्येक प्रधान को मोटे तौर पर लिया जा सकता है <math>\log M = O(dm\log q)</math>, और आवश्यक अभाज्य संख्याओं की संख्या, <math>\ell</math>, लगभग समान है।
 इस प्रक्रिया को पुनरावर्ती रूप से करते हुए, हम अभाज्य संख्या जितनी छोटी प्राप्त कर सकते हैं <math>\log\log q</math>.
 इसका मतलब है कि हम गणना और स्टोर कर सकते हैं <math>f</math> में सभी संभावित मूल्यों पर <math>T = (\log\log q)^m</math> समय और स्थान।
 अगर हम लेते हैं <math>d = \log q</math>, हम पाते हैं <math>m = \tfrac{\log n}{\log\log q}</math>, इसलिए समय/स्थान की आवश्यकता उचित है <math>n^\frac{\log\log q}{\log\log\log q}.</math>
-Kedlaya और Umans आगे दिखाते हैं कि इस प्रीप्रोसेसिंग को तेज़ (FFT) मल्टीपॉइंट मूल्यांकन के साथ कैसे जोड़ा जाए।
+Kedlaya और Umans आगे दिखाते हैं कि इस प्रीप्रोसेसिंग को तीव्ऱ (FFT) मल्टीपॉइंट मूल्यांकन के सापेक्ष कैसे जोड़ा जाए।
 यह बहुपद [[मॉड्यूलर रचना]] जैसे कई महत्वपूर्ण बीजगणितीय समस्याओं के लिए इष्टतम एल्गोरिदम की अनुमति देता है।
 == विशिष्ट बहुपद ==
-जबकि सामान्य बहुपदों की आवश्यकता होती है <math>\Omega(n)</math> संचालन का मूल्यांकन करने के लिए, कुछ बहुपदों की गणना बहुत तेजी से की जा सकती है।
+जबकि सामान्य बहुपदों की आवश्यकता होती है <math>\Omega(n)</math> संचालन का मूल्यांकन करने के लिए, कुछ बहुपदों की गणना बहुत तीव्री से की जा सकती है।
 उदाहरण के लिए, बहुपद <math>P(x)=x^2+2x+1</math> केवल एक गुणन और एक जोड़ का उपयोग करके गणना की जा सकती है <math>P(x)=(x+1)^2</math>
 === शक्तियों का मूल्यांकन ===
-{{main|Exponentiation by squaring|Addition-chain exponentiation}}
+{{main|वर्ग करके घातांक|जोड़-श्रृंखला घातांक}}
-एक विशेष रूप से दिलचस्प प्रकार का बहुपद घात है <math>x^n</math>.
+एक विशेष रूप से दिलचस्प प्रकार का बहुपद घात <math>x^n</math> है .ऐसे बहुपदों की सदैव गणना  <math>O(\log n)</math>  संचालन की जा सकती है।मान लीजिए, उदाहरण के लिए, हमें <math>x^{16}</math> गणना करने की आवश्यकता है ; हम बस <math>x</math> और गुणा करें <math>x</math> प्राप्त करने <math>x^2</math>. के सापेक्ष प्रारंभ कर सकते हैं इसके उपरांत हम <math>x^4</math>से  केवल चार गुणा में <math>x^8</math> और <math>x^{16}</math>  को प्राप्त करने के लिए उसी से गुणा कर सकते हैं ।अन्य घातांक जैसे <math>x^5</math> इसी तरह पहली कंप्यूटिंग द्वारा <math>x^4</math> 2 गुणा करके और पुनः गुणा करके <math>x</math>. कुशलतापूर्वक गणना की जा सकती है।
-ऐसे बहुपदों की गणना सदैव की जा सकती है <math>O(\log n)</math> संचालन।
-मान लीजिए, उदाहरण के लिए, हमें गणना करने की आवश्यकता है <math>x^{16}</math>; हम बस के साथ शुरू कर सकते हैं <math>x</math> और गुणा करें <math>x</math> पाने के <math>x^2</math>.
-इसके बाद हम उसे प्राप्त करने के लिए उसी से गुणा कर सकते हैं <math>x^4</math> और इतने पर पाने के लिए <math>x^8</math> और <math>x^{16}</math> केवल चार गुणा में।
-अन्य शक्तियां जैसे <math>x^5</math> इसी तरह पहली कंप्यूटिंग द्वारा कुशलतापूर्वक गणना की जा सकती है <math>x^4</math> 2 गुणा करके और फिर गुणा करके <math>x</math>.
-किसी दी गई शक्ति की गणना करने का सबसे कुशल तरीका <math>x^n</math> अतिरिक्त-श्रृंखला घातांक द्वारा प्रदान किया जाता है। हालांकि, इसके लिए प्रत्येक प्रतिपादक के लिए एक विशिष्ट एल्गोरिदम डिजाइन करने की आवश्यकता होती है, और इन एल्गोरिदम को डिजाइन करने के लिए आवश्यक गणना कठिन (एनपी-पूर्ण) होती है, इसलिए प्रभावी संगणनाओं के लिए सामान्यत पर वर्ग द्वारा घातांक को प्राथमिकता दी जाती है।
+किसी दी गई घातांक की गणना करने का सबसे कुशल विधि <math>x^n</math> अतिरिक्त-श्रृंखला घातांक द्वारा प्रदान किया जाता है। यद्यपि , इसके लिए प्रत्येक प्रतिपादक के लिए एक विशिष्ट एल्गोरिदम प्रारूपित करने की आवश्यकता होती है, और इन एल्गोरिदम को प्रारूपित करने के लिए आवश्यक गणना कठिन होती है, इसलिए प्रभावी संगणनाओं के लिए सामान्यतःः पर वर्ग द्वारा घातांक को प्राथमिकता दी जाती है।
 === बहुपद परिवार ===
-सामान्यतया बहुपद प्रसिद्ध से भिन्न रूप में दिखाई देते हैं <math>a_n x^n + \dots + a_1 x + a_0</math>.
+सामान्यतः  बहुपद प्रसिद्ध रूप से  <math>a_n x^n + \dots + a_1 x + a_0</math> भिन्न रूप में दिखाई देते हैं .[[चेबिशेव रूप]] में बहुपदों के लिए हम [[क्लेंशॉ एल्गोरिथम]] का उपयोग कर सकते हैं।बेजियर रूप में बहुपदों के लिए हम डी कास्टलजौ के एल्गोरिदम का उपयोग कर सकते हैं,और [[B-spline|बी-स्प्लिंस]] के लिए डी बूर का एल्गोरिदम है।
-[[चेबिशेव रूप]] में बहुपदों के लिए हम [[क्लेंशॉ एल्गोरिथम]] का उपयोग कर सकते हैं।
-बेजियर रूप में बहुपदों के लिए हम डी कास्टलजौ के एल्गोरिदम का उपयोग कर सकते हैं,
-और [[B-spline]]s के लिए De Boor's एल्गोरिथम है।
 === कठिन बहुपद ===
-तथ्य यह है कि कुछ बहुपदों की गणना सामान्य बहुपदों की तुलना में काफी तेजी से की जा सकती है, यह प्रश्न सुझाता है: क्या हम एक साधारण बहुपद का उदाहरण दे सकते हैं जिसकी गणना इसकी डिग्री से बहुत कम समय में नहीं की जा सकती है?
+तथ्य यह है कि कुछ बहुपदों की गणना सामान्य बहुपदों की सापेक्ष में काफी तीव्रता से की जा सकती है, यह प्रश्न सुझाता है: क्या हम एक साधारण बहुपद का उदाहरण दे सकते हैं जिसकी गणना इसकी डिग्री से बहुत न्यूनतम समय में नहीं की जा सकती है? [[वोल्कर स्ट्रास]] ने दर्शाया है<ref>{{Cite journal|last=Strassen|first=Volker|author-link=Volker Strassen|date=1974|title=परिमेय गुणांक वाले बहुपद जिनकी गणना करना कठिन है|url=|journal=[[SIAM Journal on Computing]]|language=en|volume=3|issue=2|pages=128–149|doi=10.1137/0203010|issn=}}</ref> कि बहुपद
-[[वोल्कर स्ट्रास]] ने दिखाया है<ref>{{Cite journal|last=Strassen|first=Volker|author-link=Volker Strassen|date=1974|title=परिमेय गुणांक वाले बहुपद जिनकी गणना करना कठिन है|url=|journal=[[SIAM Journal on Computing]]|language=en|volume=3|issue=2|pages=128–149|doi=10.1137/0203010|issn=}}</ref> वह बहुपद
 :<math>P(x)=\sum_{k=0}^n 2^{2^{kn^3}}x^k</math>
-से कम के द्वारा मूल्यांकन नहीं किया जा सकता है <math>\tfrac12 n - 2</math> गुणन और <math>n - 4</math> जोड़।
+से न्यूनतम के द्वारा <math>\tfrac12 n - 2</math> गुणन और <math>n - 4</math> जोड़ का मूल्यांकन नहीं किया जा सकता है ।न्यूनतम से न्यूनतम यह बाध्यता धारण करती है यदि केवल <math><n^2/\log n</math>. प्रकार के संचालन की अनुमति दी जाती है, जो लंबाई की तथाकथित बहुपद श्रृंखला को जन्म देती है
-कम से कम यह बाध्यता धारण करती है यदि केवल उन प्रकार के संचालन की अनुमति दी जाती है, जो लंबाई की तथाकथित बहुपद श्रृंखला को जन्म देती है <math><n^2/\log n</math>.
+स्ट्रैसन द्वारा दिए गए बहुपद में बहुत बड़े गुणांक हैं, परंतु संभाव्य विधियों से कि केवल 0 और 1 के गुणांक वाले बहुपदों का अस्तित्व होना चाहिए, जो कोई भी दर्शा सकता है जैसे कि मूल्यांकन के लिए न्यूनतम से न्यूनतम आवश्यकता होती है <math>\Omega(n/\log n)</math> गुणन की।<ref>{{Citation|last=Schnorr|first=C. P.|title=On the additive complexity of polynomials and some new lower bounds|date=1979|url=|work=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]|volume=67|pages=286–297|editor-last=|editor-first=|place=|publisher=[[Springer Publishing|Springer]]|doi=10.1007/3-540-09118-1_30|isbn=|access-date=|author-link=Claus P. Schnorr}}</ref>
+अन्य साधारण बहुपदों के लिए, जटिलता अज्ञात है।बहुपद <math>(x+1)(x+2)\cdots(x+n)</math> समय <math>(\log n)^{c}</math> किसी के लिए <math>c</math>. पर गणना करने योग्य नहीं होने का अनुमान है यह इस तथ्य से समर्थित है, कि यदि इसकी तीव्रता से गणना की जा सकती है, तो RSA (क्रिप्टोसिस्टम) को तोड़ते हुए बहुपद समय में पूर्णांक गुणनखंड की गणना की जा सकती है।<ref>Chen, Xi, Neeraj Kayal, and Avi Wigderson. Partial derivatives in arithmetic complexity and beyond. Now Publishers Inc, 2011.</ref>
-स्ट्रैसन द्वारा दिए गए बहुपद में बहुत बड़े गुणांक हैं, लेकिन संभाव्य विधियों से, कोई दिखा सकता है कि केवल 0 और 1 के गुणांक वाले बहुपदों का अस्तित्व होना चाहिए, जैसे कि मूल्यांकन के लिए कम से कम आवश्यकता होती है <math>\Omega(n/\log n)</math> गुणन।<ref>{{Citation|last=Schnorr|first=C. P.|title=On the additive complexity of polynomials and some new lower bounds|date=1979|url=|work=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]|volume=67|pages=286–297|editor-last=|editor-first=|place=|publisher=[[Springer Publishing|Springer]]|doi=10.1007/3-540-09118-1_30|isbn=|access-date=|author-link=Claus P. Schnorr}}</ref>
-अन्य साधारण बहुपदों के लिए, जटिलता अज्ञात है।
-बहुपद <math>(x+1)(x+2)\cdots(x+n)</math> समय पर गणना करने योग्य नहीं होने का अनुमान है <math>(\log n)^{c}</math> किसी के लिए <math>c</math>.
-यह इस तथ्य से समर्थित है, कि यदि इसकी तेजी से गणना की जा सकती है, तो RSA (क्रिप्टोसिस्टम) को तोड़ते हुए बहुपद समय में पूर्णांक गुणनखंड की गणना की जा सकती है।<ref>Chen, Xi, Neeraj Kayal, and Avi Wigderson. Partial derivatives in arithmetic complexity and beyond. Now Publishers Inc, 2011.</ref>
 == मैट्रिक्स बहुपद ==
-कभी-कभी अदिश गुणन की कम्प्यूटेशनल लागत (जैसे <math>ax</math>) गैर अदिश गुणन की कम्प्यूटेशनल लागत से कम है (जैसे <math>x^2</math>).
+कभी-कभी अदिश गुणन की न्यूनतम कम्प्यूटेशनल लागत (जैसे <math>ax</math>)गैर अदिश गुणन की न्यूनतम कम्प्यूटेशनल  लागत से न्यूनतम है (जैसे <math>x^2</math>).इसका विशिष्ट उदाहरण मैट्रिसेस है। <math>M</math> एक <math>m\times m</math> मैट्रिक्स में, एक अदिश गुणन लगभग <math>aM</math> और <math>m^2</math> गणना करते समय <math>M^2</math> अंकगणितीय संचालन लगभग <math>m^3</math>लगते हैं
-इसका विशिष्ट उदाहरण मैट्रिसेस है।
-अगर <math>M</math> एक <math>m\times m</math> मैट्रिक्स, एक अदिश गुणन <math>aM</math> लगभग लगते हैं <math>m^2</math> गणना करते समय अंकगणितीय संचालन <math>M^2</math> लगभग लगते हैं <math>m^3</math> (या <math>m^{2.3}</math> तेजी से मैट्रिक्स गुणन का उपयोग करके)।
-मैट्रिक्स बहुपद महत्वपूर्ण हैं उदाहरण के लिए मैट्रिक्स एक्सपोनेंशियल # मैट्रिक्स एक्सपोनेंशियल कंप्यूटिंग।
+उदाहरण के लिए मैट्रिक्स घातांक की गणना के लिए मैट्रिक्स बहुपद महत्वपूर्ण हैं।
-पैटर्सन और स्टॉकमेयर <ref>{{Cite journal|last=Paterson|first=Michael S.|author-link=Mike Paterson|last2=Stockmeyer|first2=Larry J.|author-link2=Larry J. Stockmeyer|date=1973|title=बहुपदों का मूल्यांकन करने के लिए आवश्यक नॉनस्केलर गुणन की संख्या पर|url=|journal=[[SIAM Journal on Computing]]|language=en|volume=2|issue=1|pages=60–66|doi=10.1137/0202007|issn=}}</ref>
+पैटर्सन और स्टॉन्यूनतमेयर <ref>{{Cite journal|last=Paterson|first=Michael S.|author-link=Mike Paterson|last2=Stockmeyer|first2=Larry J.|author-link2=Larry J. Stockmeyer|date=1973|title=बहुपदों का मूल्यांकन करने के लिए आवश्यक नॉनस्केलर गुणन की संख्या पर|url=|journal=[[SIAM Journal on Computing]]|language=en|volume=2|issue=1|pages=60–66|doi=10.1137/0202007|issn=}}</ref> ने  दर्शाया की डिग्री की गणना कैसे की जाती हैं  <math>O(\sqrt n)</math> गैर अदिश गुणन और <math>O(n)</math> अदिश गुणन केवल <math>n</math> बहुपद का उपयोग करती हैं।इस प्रकार डिग्री {{mvar|n}} के एक [[मैट्रिक्स बहुपद]]  <math>O(m^{2.3}\sqrt{n} + m^2n)</math> का समय मूल्यांकन किया जा सकता है। अगर <math>m=n</math> से  <math>O(n^3)</math> न्यूनतम है ,तो मानक एल्गोरिथम के सापेक्ष एकल मैट्रिक्स गुणन से तीव्र हैं।
-डिग्री की गणना करने का तरीका दिखाया <math>n</math> बहुपद केवल का उपयोग कर <math>O(\sqrt n)</math> गैर अदिश गुणन और <math>O(n)</math> अदिश गुणन।
-इस प्रकार डिग्री का एक [[मैट्रिक्स बहुपद]] {{mvar|n}} में मूल्यांकन किया जा सकता है <math>O(m^{2.3}\sqrt{n} + m^2n)</math> समय। अगर <math>m=n</math> यह इससे कम है <math>O(n^3);</math> वह है, मानक एल्गोरिथम के साथ एकल मैट्रिक्स गुणन से तेज़।
 यह विधि इस प्रकार काम करती है: एक बहुपद के लिए
 :<math>P(M)=a_{n-1} M^{n-1} + \dots + a_{1}M + a_0 I,</math>
-होने देना {{mvar|k}} सबसे छोटा पूर्णांक हो जो इससे छोटा न हो <math>\sqrt{n}.</math>
+मान लीजिए {{mvar|k}} सबसे छोटा पूर्णांक है जो इससे <math>\sqrt{n}.</math> छोटा नही है ,<math>M, M^2, \dots, M^k</math> घातांक के सापेक्ष गणना की जाती है <math>k</math> मैट्रिक्स गुणन, और   <math>M^k.</math> द्वारा <math>M^{2k}, M^{3k}, \dots, M^{k^2-k}</math> की बार-बार गुणा करके  गणना की जाती है अब,
-शक्तियाँ <math>M, M^2, \dots, M^k</math> के साथ गणना की जाती है <math>k</math> मैट्रिक्स गुणन, और <math>M^{2k}, M^{3k}, \dots, M^{k^2-k}</math> द्वारा बार-बार गुणा करके गणना की जाती है <math>M^k.</math>
-अब,
 :<math>\begin{align}P(M) =
 &\,(a_0 I + a_1 M + \dots + a_{k-1}M^{k-1})
@@ Line 179: / Line 159: @@
 \\+&\,(a_{n-k} I + a_{n-k+1} M + \dots + a_{n-1}M^{k-1})M^{k^2-k},
 \end{align}</math>,
-कहाँ <math>a_i=0</math> के लिए {{math|''i'' ≥ ''n''}}.
+जहाँ <math>a_i=0</math> के लिए {{math|''i'' ≥ ''n''}} है.इसके लिए बस <math>k</math> अधिक गैर-अदिश गुणन की आवश्यकता है।
-इसके लिए बस आवश्यकता है <math>k</math> अधिक गैर-अदिश गुणन।
 [[क्रोनकर उत्पाद]] का उपयोग करके हम इसे संक्षेप में लिख सकते हैं:
@@ Line 193: / Line 172: @@
 </math>.
-इस पद्धति का प्रत्यक्ष अनुप्रयोग उपयोग करता है <math>2\sqrt{n}</math> गैर-अदिश गुणन, लेकिन इसे बहुपद_मूल्यांकन#Evaluation_with_preprocessing के साथ जोड़कर, पैटर्सन और स्टॉकमेयर दिखाते हैं कि आप इसे कम कर सकते हैं <math>\sqrt{2n}</math>.
+इस पद्धति का प्रत्यक्ष अनुप्रयोग का उपयोग <math>2\sqrt{n}</math> गैर-अदिश गुणन करता है , परंतु इसे बहुपद मूल्यांकन के सापेक्ष जोड़कर, पैटर्सन और स्टॉन्यूनतमेयर को दर्शाते हैं कि आप <math>\sqrt{2n}</math> को न्यूनतम कर सकते हैं
 == यह भी देखें ==
-*एस्ट्रिन की योजना आधुनिक कंप्यूटर आर्किटेक्चर पर समानांतरकरण की सुविधा के लिए
+*एस्ट्रिन की योजना आधुनिक कंप्यूटर आर्किटेक्चर पर समानांतरकरण की सुविधा के लिए हैं।
-*अंकगणित सर्किट जटिलता सिद्धांत विभिन्न बहुपदों के मूल्यांकन के [[कम्प्यूटेशनल जटिलता सिद्धांत]] का अध्ययन करता है।
+*अंकगणित सर्किट जटिलता सिद्धांत विभिन्न बहुपदों के मूल्यांकन के [[कम्प्यूटेशनल जटिलता सिद्धांत|न्यूनतम्प्यूटेशनल जटिलता सिद्धांत]] का अध्ययन करता है।
 ==संदर्भ==

Anonymous

Search

बहुपद मूल्यांकन: Difference between revisions

Namespaces

More

Page actions

Revision as of 01:36, 16 March 2023

Contents

पृष्ठभूमि