वर्गमूल विस्तार द्वारा बहुमान फलनों का मूल्यांकन

Last updated on Nov 12, 2025

Image Preservation of Multivalued Functions पर पिछले अध्याय में हमने देखा कि $k$ -th roots of unity पर $f(x)$ का मूल्यांकन करने के बजाय, हम $f(x)$ को एक multivalued function में बदल सकते हैं और domain $\set{1}$ पर इसका मूल्यांकन कर सकते हैं।

Square Roots को Unwrap करना

1 के 8-th root को nested square roots के रूप में सोचना बहुत आसान है:

\sqrt[8]{x}=\sqrt{\sqrt{\sqrt{x}}}

अब हम दिखाएंगे कि इसका मूल्यांकन कैसे करें:

\sqrt{\sqrt{\sqrt{1}}}

square root expansion का उपयोग करके।

हम जानते हैं कि $\sqrt{1}$ का मूल्यांकन $\set{1,-1}$ होता है, इसलिए हम 1 के inner-most square root को इसके मूल्यांकनों से बदल देते हैं:

यह square roots की एक परत (layer) को “हटा” देता है। इसके बाद, हम $\sqrt{1}$ और $\sqrt{-1}$ का मूल्यांकन करते हैं। चूँकि हम 8-th roots of unity के साथ काम कर रहे हैं, $-1\equiv\omega^4$ इसलिए $\sqrt{-1}=\{\omega^2,-\omega^2\}$

फिर, हम शेष बचे प्रत्येक square roots का मूल्यांकन करते हैं:

ध्यान दें कि evaluation tree की “पत्तियां (leaves)” बिल्कुल 8-th root of unity पर मूल्यांकित $f$ हैं।

8-th roots of unity पर $f(x)=x^2$ का मूल्यांकन

Square root expansion के बारे में अच्छी बात यह है कि $x$ की अधिकांश powers के लिए, square roots “जल्दी गायब” हो जाते हैं जैसा कि यह उदाहरण दिखाता है। हम $x$ को $\sqrt[8]{x}$ से बदलते हैं, लेकिन चूँकि $x$ squared है, इसलिए अंत में हमारे पास $\sqrt[4]{x}$ बचता है या

\sqrt{\sqrt{x}}

यहाँ square roots को बार-बार expand करने से प्राप्त evaluation tree दिया गया है जब तक कि हमारे पास आठ मूल्यांकन न हो जाएं। अंतिम पंक्ति में, जब कोई square roots नहीं होते हैं, तो हम केवल values को नीचे कॉपी कर लेते हैं।

अब ध्यान दें कि यदि हम 8-th roots of unity $\set{1,...,\omega^7}$ का मूल्यांकन सीधे $f(x)=x^2$ पर करते हैं तो क्या होता है — परिणाम बिल्कुल समान होता है।

\begin{align*} f(1)&=(1)^2&=1\\ f(-1)&=(-1)^2&=1\\ f(\omega^2)&=(\omega^2)^2&=-1\\ f(-\omega^2)&=(-\omega^2)^2&=-1\\ f(\omega)&=(\omega)^2&=\omega^2\\ f(-\omega)&=(-\omega)^2&=\omega^2\\ f(\omega^3)&=(\omega^3)^2&=-\omega^2\\ f(-\omega^3)&=(-\omega^3)^2&=-\omega^2\\ \end{align*}

8-th roots पर $f(x)=x^4$ का मूल्यांकन

फिर से, हम $x$ को $\sqrt[8]{x}$ से बदलते हैं जो हमें $\sqrt{x}$ देता है। चूँकि हमारे पास केवल एक square root है, हम square root को केवल एक बार expand करेंगे, और फिर बस परिणामों को नीचे कॉपी कर लेंगे।

हमने पहले के एक अध्याय में देखा था कि $x^{k/2}$ 1 होता है यदि इसका मूल्यांकन $\omega$ की सम (even) power पर किया जाता है और अन्यथा -1 होता है। यहाँ का परिणाम अपेक्षित परिणाम से मेल खाता है।

8-th roots of unity पर $f(x)=ax+bx^5$ का मूल्यांकन

यदि हम $x$ को $\sqrt[8]{x}$ से बदलते हैं, तो हमें थोड़ा अजीब परिणाम मिलता है:

f(x)=a\sqrt[8]{x}+bx^{5/8}

हालाँकि, यदि हम $f(x)$ को $f(x)=x(a+bx^4)$ में बदलने के लिए पहले $x$ को factor out करते हैं, तो नया रूप तब बहुत अधिक प्रबंधनीय (manageable) हो जाता है जब हम $x$ के लिए $\sqrt[8]{x}$ को substitute करते हैं:

g(x)=\sqrt[8]{x}(a+b\sqrt{x})

पहला square root पहले मूल्यांकन के बाद गायब हो जाएगा और $(a+b\sqrt{x})$ अधिकांश tree के लिए एक constant बन जाएगा।

नीचे square roots को expand करने का एक आरेख दिया गया है। प्रत्येक स्तर पर, हम एक square root को अनरैप (मूल्यांकित) करते हैं। नीले रंग में square roots उन roots को दर्शाते हैं जिनका मूल्यांकन प्रत्येक चरण में किया गया है। एक सामान्य नियम के रूप में, innermost square root का मूल्यांकन करें यदि वह nested है:

अब परिणाम की तुलना 8-th roots of unity पर $f(x)=ax+bx^5$ का एक-एक करके मूल्यांकन करने से करते हैं:

\begin{array}{rcll} f(1) &=& a(1) + b(1)^5 &= a + b\\[4pt] f(-1\equiv\omega^4) &=& a\omega^4 + b\omega^{20} = a(-1) + b(-1) &= -a - b\\[4pt] f(\omega^2) &=& a\omega^2 + b\omega^{10} = a\omega^2 + b\omega^2 &= (a + b)\omega^2\\[4pt] f(-\omega^{2}\equiv\omega^6) &=& a\omega^6 + b\omega^{30} = a(-\omega^2) + b(-\omega^2) &= -(a + b)\omega^2\\[4pt] f(\omega) &=& a\omega + b\omega^5 &= a\omega - b\omega \\[4pt] f(-\omega\equiv\omega^5) &=& a\omega^5 + b\omega^{25} = a(-\omega) + b\omega &= -a\omega + b\omega = (b - a)\omega\\[4pt] f(\omega^3) &=& a\omega^3 + b\omega^{15} = a\omega^3 + b\omega^7 &= a\omega^3 - b\omega^3 = (a - b)\omega^3\\[4pt] f(-\omega^3\equiv\omega^7) &=& a\omega^7 + b\omega^{35} = a(-\omega^3) + b(-\omega^3) &= -(a + b)\omega^3 \end{array}

उपरोक्त विधि का उपयोग करके terms का मूल्यांकन करने के लिए 8 additions और 16 multiplications की आवश्यकता होती है।

हालाँकि, square root expansion का उपयोग करते हुए, हमें केवल 2 additions और 10 multiplications की आवश्यकता होती है। जब भी किसी square root को उसके दो समाधानों (solutions) में expand किया जाता है, तो हम इसे आसन्न (adjacent) term से multiply करते हैं। इसलिए जब भी “अंतिम” square root अनरैप होता है, तो इसके परिणामस्वरूप दो multiplications होते हैं। इन्हें नीचे लाल रंग में हाइलाइट किया गया है। Additions को नीले रंग में हाइलाइट किया गया है।

ध्यान दें कि “square root की गणना करना” पूरी तरह से deterministic है। हम जानते हैं कि यह हमेशा $\set{1}$ , 2nd roots of unity, 4-th roots of unity, 8-th roots of unity आदि के पैटर्न का अनुसरण करता है। इस प्रकार, square roots की स्पष्ट रूप से गणना करने की कोई आवश्यकता नहीं है।

आसान terms और कठिन terms

हम देख सकते हैं कि terms $x^{k/2}$ का मूल्यांकन करना सबसे आसान है क्योंकि उन्हें केवल 1 मूल्यांकन की आवश्यकता होती है, और बाकी केवल tree में values को नीचे कॉपी करना होता है।

दूसरी ओर, बिना power वाले $x$ का मूल्यांकन करना सबसे “कठिन” है क्योंकि हमें tree में नीचे जाने वाले हर कदम पर square root expansion करने की आवश्यकता होती है।

Function $f(x)=a+bx^{k/2}$ , जो $k$ -th roots of unity पर multivalued function $g(x)=(a+b\sqrt{x})$ बन जाता है, के बारे में अच्छी बात यह है कि हम tree के दूसरे स्तर पर square root का पूरी तरह से मूल्यांकन कर लेते हैं, और बाकी मूल्यांकन के लिए बस $a+b$ के sum को नीचे कॉपी कर लेते हैं।

वास्तव में, किसी भी polynomial को $a+bx^{k/2}$ terms की मात्रा को “अधिकतम” करने और $x$ terms की मात्रा को “न्यूनतम” करने के लिए लिखा जा सकता है।

मान लीजिए कि हमारे पास 7-degree polynomial है जिसका मूल्यांकन हम 8-th roots of unity पर करना चाहते हैं।

f(x)= a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 + a_5x^5 + a_6x^6 + a_7x^7

$x^4$ terms की संख्या को अधिकतम करने और केवल एक $x$ term रखने के लिए, हम इसे निम्नानुसार factor करते हैं:

f(x)= a_0 + a_2x^2 + a_4x^4 + a_6x^6 + a_1x + a_5x^5 + a_3x^3+ a_7x^7

f(x)= a_0 + a_4x^4 + (a_2x^2 + a_6x^6) + (a_1x + a_5x^5) + (a_3x^3+ a_7x^7)

f(x)= a_0 + a_4x^4 + x^2(a_2 + a_6x^4) + x(a_1 + a_5x^4) + x^3(a_3x+ a_7x^4)

f(x)= a_0 + a_4x^4 + x^2(a_2 + a_6x^4) + x((a_1 + a_5x^4) + x^2(a_3x+ a_7x^4))

अभ्यास: 4th roots of unity पर मूल्यांकित polynomial $f(x)=a_0+a_1x+a_2x^2+a_3x^3$ को किस प्रकार factor किया जाना चाहिए ताकि इसमें केवल एक $x$ term और यथासंभव अधिक $x^2$ terms हों? याद रखें, इस मामले में $x^{k/2}$ , $x^2$ है।

अगले अध्याय में, हम दिखाएंगे कि square root expansion का उपयोग करके general degree 4 और degree 8 polynomial का मूल्यांकन कैसे किया जाता है, जो कि वास्तव में NTT algorithm भी होता है।