a00109.html

This library defines basic operation on polynomials, and contains also 3 different roots (zeroes)-fi

<a name="l00437"></a>00437     }
<a name="l00438"></a>00438 
<a name="l00451"></a><a class="code" href="a00090.html#b2f6bf0ca6914dfcfb6e03862d162c7e">00451</a>     <span class="keyword">const</span> Polynomial&lt;T&gt;&amp; <a class="code" href="a00090.html#9c6951d37215e36ec4d171d26f90f487">operator*= </a>(<span class="keyword">const</span> T&amp; f) {
<a name="l00452"></a>00452         <a class="code" href="a00102.html#g4db05aa06bba6b0f29a0c2608a479ec1">mul</a>(*<span class="keyword">this</span>, f);
<a name="l00453"></a>00453         <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00454"></a>00454     }
<a name="l00455"></a>00455 
<a name="l00468"></a><a class="code" href="a00090.html#11458f42a6275e6c384467ca5c398e95">00468</a>     Polynomial&lt;T&gt;&amp; <a class="code" href="a00090.html#11458f42a6275e6c384467ca5c398e95">operator/= </a>(<span class="keyword">const</span> T&amp; s) {
<a name="l00469"></a>00469         <a class="code" href="a00102.html#g4db05aa06bba6b0f29a0c2608a479ec1">mul</a>(*<span class="keyword">this</span>, T(1) / s);
<a name="l00470"></a>00470         <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00471"></a>00471     }
<a name="l00489"></a><a class="code" href="a00090.html#b6cb5632c793b07705ce488ac0fab8eb">00489</a>     <span class="keyword">friend</span> <span class="keyword">inline</span> Polynomial&lt;T&gt; <a class="code" href="a00090.html#b6cb5632c793b07705ce488ac0fab8eb">operator+ </a>(<span class="keyword">const</span> Polynomial&lt;T&gt;&amp; p, <span class="keyword">const</span> Polynomial&lt;T&gt;&amp; q) {
<a name="l00490"></a>00490         Polynomial&lt;T&gt; r;
<a name="l00491"></a>00491         <a class="code" href="a00102.html#g93873480bca596f74ff9b07f75c78103">add</a>(r, p, q);
<a name="l00492"></a>00492         <span class="keywordflow">return</span> r;
<a name="l00493"></a>00493     }
<a name="l00494"></a>00494 
<a name="l00509"></a><a class="code" href="a00090.html#6c43bbb2372812f10b97bb365f482a24">00509</a>     <span class="keyword">friend</span> <span class="keyword">inline</span> Polynomial&lt;T&gt; <a class="code" href="a00090.html#6c43bbb2372812f10b97bb365f482a24">operator- </a>(<span class="keyword">const</span> Polynomial&lt;T&gt;&amp; p, <span class="keyword">const</span> Polynomial&lt;T&gt;&amp; q) {
<a name="l00510"></a>00510         Polynomial&lt;T&gt; r;
<a name="l00511"></a>00511         <a class="code" href="a00102.html#g5a0e286e83d54485e6f4ef4cb0e04f51">sub</a>(r, a, b);
<a name="l00512"></a>00512         <span class="keywordflow">return</span> r;
<a name="l00513"></a>00513     }
<a name="l00514"></a>00514 
<a name="l00530"></a><a class="code" href="a00090.html#cd642f1b8ab48b8b99394fffc24727d6">00530</a>     <span class="keyword">friend</span> <span class="keyword">inline</span> Polynomial&lt;T&gt; <a class="code" href="a00090.html#cd642f1b8ab48b8b99394fffc24727d6">operator* </a>(<span class="keyword">const</span> Polynomial&lt;T&gt;&amp; p, <span class="keyword">const</span> Polynomial&lt;T&gt;&amp; q) {
<a name="l00531"></a>00531         Polynomial&lt;T&gt; r;
<a name="l00532"></a>00532         <a class="code" href="a00102.html#g4db05aa06bba6b0f29a0c2608a479ec1">mul</a>(r, p, q);
<a name="l00533"></a>00533         <span class="keywordflow">return</span> r;
<a name="l00534"></a>00534     }
<a name="l00535"></a>00535 
<a name="l00548"></a><a class="code" href="a00090.html#955b65f7ae51e1a45bcf985c738640eb">00548</a>     <span class="keyword">friend</span> <span class="keyword">inline</span> Polynomial&lt;T&gt; <a class="code" href="a00090.html#cd642f1b8ab48b8b99394fffc24727d6">operator* </a>(<span class="keyword">const</span> T&amp; s, <span class="keyword">const</span> Polynomial&lt;T&gt;&amp; p) {
<a name="l00549"></a>00549         Polynomial&lt;T&gt; r;
<a name="l00550"></a>00550         <a class="code" href="a00102.html#g4db05aa06bba6b0f29a0c2608a479ec1">mul</a>(r, s, p);
<a name="l00551"></a>00551         <span class="keywordflow">return</span> r;
<a name="l00552"></a>00552     }
<a name="l00553"></a>00553 
<a name="l00566"></a><a class="code" href="a00090.html#fedcfef27cf2f0a1f0075272a849b951">00566</a>     <span class="keyword">friend</span> Polynomial&lt;T&gt; <a class="code" href="a00090.html#fedcfef27cf2f0a1f0075272a849b951">operator/ </a>(<span class="keyword">const</span> Polynomial&lt;T&gt;&amp; p, <span class="keyword">const</span> T&amp; s) {
<a name="l00567"></a>00567         Polynomial&lt;T&gt; r;
<a name="l00568"></a>00568         <a class="code" href="a00102.html#g4db05aa06bba6b0f29a0c2608a479ec1">mul</a>(r, T(1) / f, p);
<a name="l00569"></a>00569         <span class="keywordflow">return</span> r;
<a name="l00570"></a>00570     }
<a name="l00572"></a>00572 };
<a name="l00573"></a>00573 
<a name="l00589"></a>00589 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
<a name="l00590"></a><a class="code" href="a00102.html#g93873480bca596f74ff9b07f75c78103">00590</a> <span class="keywordtype">void</span> <a class="code" href="a00102.html#g93873480bca596f74ff9b07f75c78103">add</a>(Polynomial&lt;T&gt;&amp; r, <span class="keyword">const</span> Polynomial&lt;T&gt;&amp; p, <span class="keyword">const</span> Polynomial&lt;T&gt;&amp; q) {
<a name="l00591"></a>00591     <span class="keywordtype">int</span> i, m, n;
<a name="l00592"></a>00592     m = p.<a class="code" href="a00090.html#b433e0edb11b32a205a9d07b89aefa8f">degree</a>();
<a name="l00593"></a>00593     n = q.<a class="code" href="a00090.html#b433e0edb11b32a205a9d07b89aefa8f">degree</a>();
<a name="l00594"></a>00594     <span class="keywordflow">if</span> (m &lt;= n) {
<a name="l00595"></a>00595         r.resize(n + 1);
<a name="l00596"></a>00596         <span class="keywordflow">for</span> (i = 0; i &lt;= m; ++i)
<a name="l00597"></a>00597             r[i] = p[i] + q[i];
<a name="l00598"></a>00598         <span class="keywordflow">for</span> ( ; i &lt;= n; ++i)
<a name="l00599"></a>00599             r[i] = q[i];
<a name="l00600"></a>00600     }
<a name="l00601"></a>00601     <span class="keywordflow">else</span> {
<a name="l00602"></a>00602         r.resize(m + 1);
<a name="l00603"></a>00603         <span class="keywordflow">for</span> (i = 0; i &lt;= n; ++i)
<a name="l00604"></a>00604             r[i] = p[i] + q[i];
<a name="l00605"></a>00605         <span class="keywordflow">for</span> ( ; i &lt;= m; ++i)
<a name="l00606"></a>00606             r[i] = p[i];
<a name="l00607"></a>00607     }
<a name="l00608"></a>00608     r.<a class="code" href="a00090.html#7d71a634b3ab7d5071c031633b9614d5">compact</a>();
<a name="l00609"></a>00609 }
<a name="l00610"></a>00610 
<a name="l00624"></a>00624 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
<a name="l00625"></a><a class="code" href="a00102.html#g1fb458a7c3a7a5993ec815e6422236ed">00625</a> <span class="keywordtype">void</span> <a class="code" href="a00102.html#g93873480bca596f74ff9b07f75c78103">add</a>(Polynomial&lt;T&gt;&amp; p, <span class="keyword">const</span> Polynomial&lt;T&gt;&amp; q) {
<a name="l00626"></a>00626     <span class="keywordtype">int</span> m = p.<a class="code" href="a00090.html#b433e0edb11b32a205a9d07b89aefa8f">degree</a>();
<a name="l00627"></a>00627     <span class="keywordtype">int</span> n = q.<a class="code" href="a00090.html#b433e0edb11b32a205a9d07b89aefa8f">degree</a>();
<a name="l00628"></a>00628     <span class="keywordflow">if</span> (m &lt; n)
<a name="l00629"></a>00629         p.resize(n + 1, T(0));
<a name="l00630"></a>00630 
<a name="l00631"></a>00631     <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = 0; i &lt;= n; ++i)
<a name="l00632"></a>00632         p[i] += q[i];
<a name="l00633"></a>00633     p.<a class="code" href="a00090.html#7d71a634b3ab7d5071c031633b9614d5">compact</a>();
<a name="l00634"></a>00634 }
<a name="l00635"></a>00635 
<a name="l00649"></a>00649 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
<a name="l00650"></a><a class="code" href="a00102.html#g5a0e286e83d54485e6f4ef4cb0e04f51">00650</a> <span class="keywordtype">void</span> <a class="code" href="a00102.html#g5a0e286e83d54485e6f4ef4cb0e04f51">sub</a>(Polynomial&lt;T&gt;&amp; r, <span class="keyword">const</span> Polynomial&lt;T&gt;&amp; p, <span class="keyword">const</span> Polynomial&lt;T&gt;&amp; q) {
<a name="l00651"></a>00651     <span class="keywordtype">int</span> i;
<a name="l00652"></a>00652     <span class="keywordtype">int</span> m = p.<a class="code" href="a00090.html#b433e0edb11b32a205a9d07b89aefa8f">degree</a>();
<a name="l00653"></a>00653     <span class="keywordtype">int</span> n = q.<a class="code" href="a00090.html#b433e0edb11b32a205a9d07b89aefa8f">degree</a>();
<a name="l00654"></a>00654     <span class="keywordflow">if</span> (m &lt;= n) {
<a name="l00655"></a>00655         r.resize(n + 1);
<a name="l00656"></a>00656         <span class="keywordflow">for</span> (i = 0; i &lt;= m; ++i)
<a name="l00657"></a>00657             r[i] = p[i] - q[i];
<a name="l00658"></a>00658         <span class="keywordflow">for</span> ( ; i &lt;= n; ++i)
<a name="l00659"></a>00659             r[i] = -q[i];
<a name="l00660"></a>00660     }
<a name="l00661"></a>00661     <span class="keywordflow">else</span> {
<a name="l00662"></a>00662         r.resize(m + 1);
<a name="l00663"></a>00663         <span class="keywordflow">for</span> (i = 0; i &lt;= n; ++i)
<a name="l00664"></a>00664             r[i] = p[i] - q[i];
<a name="l00665"></a>00665         <span class="keywordflow">for</span> ( ; i &lt;= m; ++i)
<a name="l00666"></a>00666             r[i] = p[i];
<a name="l00667"></a>00667     }
<a name="l00668"></a>00668     r.<a class="code" href="a00090.html#7d71a634b3ab7d5071c031633b9614d5">compact</a>();
<a name="l00669"></a>00669 }
<a name="l00670"></a>00670 
<a name="l00682"></a>00682 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
<a name="l00683"></a><a class="code" href="a00102.html#gc692b059e9ef90e831249a8f94043ee3">00683</a> <span class="keywordtype">void</span> <a class="code" href="a00102.html#g5a0e286e83d54485e6f4ef4cb0e04f51">sub</a>(Polynomial&lt;T&gt;&amp; p, <span class="keyword">const</span> Polynomial&lt;T&gt;&amp; q) {
<a name="l00684"></a>00684     <span class="keywordtype">int</span> i;
<a name="l00685"></a>00685     <span class="keywordtype">int</span> m = p.<a class="code" href="a00090.html#b433e0edb11b32a205a9d07b89aefa8f">degree</a>();
<a name="l00686"></a>00686     <span class="keywordtype">int</span> n = q.<a class="code" href="a00090.html#b433e0edb11b32a205a9d07b89aefa8f">degree</a>();
<a name="l00687"></a>00687     <span class="keywordflow">if</span> (m &lt; n)
<a name="l00688"></a>00688         p.resize(n + 1, T(0));
<a name="l00689"></a>00689     <span class="keywordflow">for</span> (i = 0; i &lt;= n; ++i)
<a name="l00690"></a>00690         p[i] -= q[i];
<a name="l00691"></a>00691     p.<a class="code" href="a00090.html#7d71a634b3ab7d5071c031633b9614d5">compact</a>();
<a name="l00692"></a>00692 }
<a name="l00693"></a>00693 
<a name="l00710"></a>00710 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
<a name="l00711"></a><a class="code" href="a00102.html#g58e7f22c0b67bf90c4e433fe198035db">00711</a> <span class="keywordtype">void</span> <a class="code" href="a00102.html#g58e7f22c0b67bf90c4e433fe198035db">div</a>(Polynomial&lt;T&gt;&amp; q, Polynomial&lt;T&gt;&amp; r, <span class="keyword">const</span> Polynomial&lt;T&gt;&amp; u, <span class="keyword">const</span> Polynomial&lt;T&gt;&amp; v) {
<a name="l00712"></a>00712     <span class="keywordtype">int</span> na = u.<a class="code" href="a00090.html#b433e0edb11b32a205a9d07b89aefa8f">degree</a>();
<a name="l00713"></a>00713     <span class="keywordtype">int</span> nb = v.<a class="code" href="a00090.html#b433e0edb11b32a205a9d07b89aefa8f">degree</a>();
<a name="l00714"></a>00714     <span class="keywordflow">if</span> (na &gt;= nb) {
<a name="l00715"></a>00715         r = u;
<a name="l00716"></a>00716         T t;
<a name="l00717"></a>00717         q.resize(1 + na - nb);
<a name="l00718"></a>00718         std::fill(&amp;q[0], &amp;q[q.size()], T(0));
<a name="l00719"></a>00719         <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = na - nb; i &gt;= 0; --i) {
<a name="l00720"></a>00720             q[i] = r[nb + i] / v[nb];
<a name="l00721"></a>00721             r[nb + i] = T(0);
<a name="l00722"></a>00722             <span class="keywordflow">for</span> (<span class="keywordtype">int</span> j = nb + i - 1; j &gt;= i; --j) {
<a name="l00723"></a>00723                 r[j + 1] -= (q[i] * v[j - i]);
<a name="l00724"></a>00724             }
<a name="l00725"></a>00725             r[i + nb] = 0;
<a name="l00726"></a>00726         }
<a name="l00727"></a>00727         r.<a class="code" href="a00090.html#7d71a634b3ab7d5071c031633b9614d5">compact</a>();
<a name="l00728"></a>00728     }
<a name="l00729"></a>00729     <span class="keywordflow">else</span> {
<a name="l00730"></a>00730         r = u;
<a name="l00731"></a>00731         q.resize(1);
<a name="l00732"></a>00732         q[0] = T(0);
<a name="l00733"></a>00733     }
<a name="l00734"></a>00734 }
<a name="l00735"></a>00735 
<a name="l00751"></a>00751 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
<a name="l00752"></a><a class="code" href="a00102.html#ge76610399111a4dd1b9b920cda19100c">00752</a> <span class="keywordtype">void</span> <a class="code" href="a00102.html#g58e7f22c0b67bf90c4e433fe198035db">div</a>(Polynomial&lt;T&gt;&amp; u, Polynomial&lt;T&gt;&amp; r, <span class="keyword">const</span> Polynomial&lt;T&gt;&amp; v) {
<a name="l00753"></a>00753     <span class="keywordtype">int</span> na = u.<a class="code" href="a00090.html#b433e0edb11b32a205a9d07b89aefa8f">degree</a>();
<a name="l00754"></a>00754     <span class="keywordtype">int</span> nb = v.<a class="code" href="a00090.html#b433e0edb11b32a205a9d07b89aefa8f">degree</a>();
<a name="l00755"></a>00755     <span class="keywordflow">if</span> (na &gt;= nb) {
<a name="l00756"></a>00756         r = u;
<a name="l00757"></a>00757         u.resize(na - nb + 1);
<a name="l00758"></a>00758         <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = na - nb; i &gt;= 0; --i) {
<a name="l00759"></a>00759             u[i] = r[nb + i] / v[nb];
<a name="l00760"></a>00760             r[nb + i] = T(0);
<a name="l00761"></a>00761             <span class="keywordflow">for</span> (<span class="keywordtype">int</span> j = nb + i - 1; j &gt;= i; --j)
<a name="l00762"></a>00762                 r[j] -= (u[i] * v[j - i]);
<a name="l00763"></a>00763         }
<a name="l00764"></a>00764         r.<a class="code" href="a00090.html#7d71a634b3ab7d5071c031633b9614d5">compact</a>();
<a name="l00765"></a>00765     }
<a name="l00766"></a>00766     <span class="keywordflow">else</span> {
<a name="l00767"></a>00767         r = u;
<a name="l00768"></a>00768         u.resize(1);
<a name="l00769"></a>00769         u[0] = T(0);
<a name="l00770"></a>00770     }
<a name="l00771"></a>00771 }