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

गणित और कंप्यूटर विज्ञान में, बहुपद मूल्यांकन एक बहुपद के मूल्य की गणना को संदर्भित करता है तथा इसके अनिश्चित चर को कुछ मूल्यों के लिए प्रतिस्थापित किया जाता है। दूसरे शब्दों में, बहुपद के मूल्यांकन $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-स्वतंत्र हैशिंग की गणना करने के लिए बहुपद का उपयोग किया जाता है।

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

सामान्य विधि

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

See also: हॉर्नर की विधि

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

$${\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}}$

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

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

See also: Estrin's scheme

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

$${\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}$.

एक उदाहरण सबसे पहले Motzkin ने दिया था जिसने नोट किया

$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 )}$. विचार दो बहुपदों को परिभाषित करना है जो क्रमशः पहले और दूसरे भाग में शून्य हैं: $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.6.4 प्रकार के बहुपद मानों को सारणीबद्ध करने के लिए एक विधि देता है

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

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

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

विचार रूपांतरित करना है $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}$

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

Main articles: Exponentiation by squaring and Addition-chain exponentiation

एक विशेष रूप से दिलचस्प प्रकार का बहुपद घात है $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}$. चेबिशेव रूप में बहुपदों के लिए हम क्लेंशॉ एल्गोरिथम का उपयोग कर सकते हैं। बेजियर रूप में बहुपदों के लिए हम डी कास्टलजौ के एल्गोरिदम का उपयोग कर सकते हैं, और B-splines के लिए De Boor's एल्गोरिथम है।

कठिन बहुपद

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

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

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

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

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

पैटर्सन और स्टॉकमेयर डिग्री की गणना करने का तरीका दिखाया $n$ बहुपद केवल का उपयोग कर $O({\sqrt {n}})$ गैर अदिश गुणन और $O(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^{2k},M^{3k},\dots ,M^{k^{2}-k}$ द्वारा बार-बार गुणा करके गणना की जाती है $M^{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 ≥ 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}}$ गैर-अदिश गुणन, लेकिन इसे बहुपद_मूल्यांकन#Evaluation_with_preprocessing के साथ जोड़कर, पैटर्सन और स्टॉकमेयर दिखाते हैं कि आप इसे कम कर सकते हैं ${\sqrt {2n}}$.

यह भी देखें

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