Rosetta Code

Polynomial synthetic division: Difference between revisions

Page Discussion

Polynomial synthetic division (view source)

Revision as of 18:20, 23 March 2022

9,532 bytes added ,  2 years ago
m
→‎{{header|Phix}}: syntax coloured, made p2js compatible
(→‎{{header|Haskell}}: changed to less cryptic non-monadic solution)
m (→‎{{header|Phix}}: syntax coloured, made p2js compatible)
Line 595:
=={{header|Phix}}==
{{trans|Kotlin}}
<!--<lang Phix>(phixonline)-->
<lang Phix>function extendedSyntheticDivision(sequence dividend, divisor)
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
sequence out = dividend
<span style="color: #008080;">function</span> <span style="color: #000000;">extendedSyntheticDivision</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">dividend</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">divisor</span><span style="color: #0000FF;">)</span>
integer normalizer = divisor[1]
<span style="color: #004080;">sequence</span> <span style="color: #000000;">out</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dividend</span><span style="color: #0000FF;">)</span>
integer separator = length(dividend) - length(divisor) + 1
<span style="color: #004080;">integer</span> <span style="color: #000000;">normalizer</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">divisor</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span>
for i=1 to separator do
<span style="color: #000000;">separator</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dividend</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">-</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">divisor</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span>
out[i] /= normalizer
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">separator</span> <span style="color: #008080;">do</span>
integer coef = out[i]
<span style="color: #000000;">out</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">/=</span> <span style="color: #000000;">normalizer</span>
if (coef != 0) then
<span style="color: #004080;">integer</span> <span style="color: #000000;">coef</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">out</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
for j=2 to length(divisor) do out[i+j-1] += -divisor[j] * coef end for
<span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">coef</span> <span style="color: #0000FF;">!=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
end if
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">divisor</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
end for
<span style="color: #004080;">integer</span> <span style="color: #000000;">odx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
return {out[1..separator],out[separator+1..$]}
<span style="color: #000000;">out</span><span style="color: #0000FF;">[</span><span style="color: #000000;">odx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">divisor</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">coef</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
constant tests = {{{1, -12, 0, -42},{1, -3}},
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
{{1, 0, 0, 0, -2},{1, 1, 1, 1}}}
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">out</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">separator</span><span style="color: #0000FF;">],</span><span style="color: #000000;">out</span><span style="color: #0000FF;">[</span><span style="color: #000000;">separator</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$]}</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
printf(1,"Polynomial synthetic division\n")
for t=1 to length(tests) do
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">42</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">3</span><span style="color: #0000FF;">}},</span>
sequence {n,d} = tests[t],
<span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">42</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">3</span><span style="color: #0000FF;">}},</span>
{q,r} = extendedSyntheticDivision(n, d)
<span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span>
printf(1,"%v / %v = %v, remainder %v\n",{n,d,q,r})
<span style="color: #0000FF;">{{</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">7</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}}}</span>
end for</lang>▼
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Polynomial synthetic division\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">],</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">extendedSyntheticDivision</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%v / %v = %v, remainder %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
▲end for<!--</lang>-->
{{out}}
<pre>
Polynomial synthetic division
Polynomial synthetic division
{1,-12,0,-42}  /  {1,-3}   =   {1,-9,-27}, remainder  remainder {-123}
{1,0,0-12,0,-242}  /  {1,1,1,1-3}   =   {1,-113}, remainder  remainder {0,016,-181}
{1,0,0,0,-2} / {1,1,1,1}  =  {1,-1}, remainder {0,0,-1}
{6,5,0,-7} / {3,-2,-1}  =  {2,3}, remainder {8,-4}
</pre>
 
Petelomax
7,820

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/258835"