Polynomial long division: Difference between revisions
Content added Content deleted
(added RPL) |
m (→{{header|Phix}}: use pygments) |
||
Line 2,875: | Line 2,875: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<syntaxhighlight lang="phix"> |
|||
-- demo\rosetta\Polynomial_long_division.exw |
|||
with javascript_semantics |
|||
function degree(sequence p) |
|||
for i=length(p) to 1 by -1 do |
|||
if p[i]!=0 then return i end if |
|||
end for |
|||
return -1 |
|||
end function |
|||
function poly_div(sequence n, d) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">degree</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> |
|||
d = deep_copy(d) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
while length(d)<length(n) do d &=0 end while |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">i</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
integer dn = degree(n), |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
dd = degree(d) |
|||
<span style="color: #008080;">return</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> |
|||
if dd<0 then throw("divide by zero") end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
sequence quo = repeat(0,dn), |
|||
rem = deep_copy(n) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">poly_div</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">)</span> |
|||
while dn>=dd do |
|||
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span> |
|||
integer k = dn-dd, qk = rem[dn]/d[dd] |
|||
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)<</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">&=</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
sequence d2 = d[1..length(d)-k] |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">dn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">degree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span> |
|||
quo[k+1] = qk |
|||
<span style="color: #000000;">dd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">degree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span> |
|||
for i=1 to length(d2) do |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">dd</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">throw</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"divide by zero"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
integer mi = -i |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">quo</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dn</span><span style="color: #0000FF;">),</span> |
|||
rem[mi] -= d2[mi]*qk |
|||
<span style="color: #000000;">rem</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">dn</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">dd</span> <span style="color: #008080;">do</span> |
|||
dn = degree(rem) |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dn</span><span style="color: #0000FF;">-</span><span style="color: #000000;">dd</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">qk</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rem</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dn</span><span style="color: #0000FF;">]/</span><span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dd</span><span style="color: #0000FF;">]</span> |
|||
end while |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">d2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> |
|||
return {quo,rem} |
|||
<span style="color: #000000;">quo</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</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;">qk</span> |
|||
end function |
|||
<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: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">mi</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">i</span> |
|||
function poly(sequence si) |
|||
<span style="color: #000000;">rem</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mi</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">d2</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mi</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">qk</span> |
|||
-- display helper |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
string r = "" |
|||
<span style="color: #000000;">dn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">degree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rem</span><span style="color: #0000FF;">)</span> |
|||
for t=length(si) to 1 by -1 do |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
integer sit = si[t] |
|||
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">quo</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rem</span><span style="color: #0000FF;">}</span> |
|||
if sit!=0 then |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
if sit=1 and t>1 then |
|||
r &= iff(r=""? "":" + ") |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">)</span> |
|||
elsif sit=-1 and t>1 then |
|||
<span style="color: #000080;font-style:italic;">-- display helper</span> |
|||
r &= iff(r=""?"-":" - ") |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span> |
|||
else |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">si</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
if r!="" then |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">sit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">]</span> |
|||
r &= iff(sit<0?" - ":" + ") |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">sit</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
sit = abs(sit) |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">sit</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> |
|||
end if |
|||
<span style="color: #000000;">r</span> <span style="color: #0000FF;">&=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #008000;">""</span><span style="color: #0000FF;">?</span> <span style="color: #008000;">""</span><span style="color: #0000FF;">:</span><span style="color: #008000;">" + "</span><span style="color: #0000FF;">)</span> |
|||
r &= sprintf("%d",sit) |
|||
<span style="color: #008080;">elsif</span> <span style="color: #000000;">sit</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> |
|||
end if |
|||
<span style="color: #000000;">r</span> <span style="color: #0000FF;">&=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #008000;">""</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"-"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">" - "</span><span style="color: #0000FF;">)</span> |
|||
r &= iff(t>1?"x"&iff(t>2?sprintf("^%d",t-1):""):"") |
|||
end if |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">!=</span><span style="color: #008000;">""</span> <span style="color: #008080;">then</span> |
|||
end for |
|||
<span style="color: #000000;">r</span> <span style="color: #0000FF;">&=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sit</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span><span style="color: #0000FF;">?</span><span style="color: #008000;">" - "</span><span style="color: #0000FF;">:</span><span style="color: #008000;">" + "</span><span style="color: #0000FF;">)</span> |
|||
if r="" then r="0" end if |
|||
<span style="color: #000000;">sit</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sit</span><span style="color: #0000FF;">)</span> |
|||
return r |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end function |
|||
<span style="color: #000000;">r</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sit</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
constant tests = {{{-42,0,-12,1},{-3,1}}, |
|||
<span style="color: #000000;">r</span> <span style="color: #0000FF;">&=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"x"</span><span style="color: #0000FF;">&</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">></span><span style="color: #000000;">2</span><span style="color: #0000FF;">?</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"^%d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">):</span><span style="color: #008000;">""</span><span style="color: #0000FF;">):</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span> |
|||
{{-3,1},{-42,0,-12,1}}, |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
{{-42,0,-12,1},{-3,1,1}}, |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
{{2,3,1},{1,1}}, |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #008000;">""</span> <span style="color: #008080;">then</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"0"</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
{{3,5,6,-4,1},{1,2,1}}, |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">r</span> |
|||
{{3,0,7,0,0,0,0,0,3,0,0,1},{1,0,0,5,0,0,0,1}}, |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
{{-56,87,-94,-55,22,-7},{2,0,1}}, |
|||
} |
|||
<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;">42</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">3</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><span style="color: #000000;">1</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">42</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span> |
|||
constant fmt = "%40s / %-16s = %25s rem %s\n" |
|||
<span style="color: #0000FF;">{{-</span><span style="color: #000000;">42</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">3</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;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</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> |
|||
for i=1 to length(tests) do |
|||
<span style="color: #0000FF;">{{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">4</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;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span> |
|||
sequence {num,den} = tests[i], |
|||
<span style="color: #0000FF;">{{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</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: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</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;">1</span><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;">5</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: #000000;">1</span><span style="color: #0000FF;">}},</span> |
|||
{quo,rem} = poly_div(num,den) |
|||
<span style="color: #0000FF;">{{-</span><span style="color: #000000;">56</span><span style="color: #0000FF;">,</span><span style="color: #000000;">87</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">94</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">55</span><span style="color: #0000FF;">,</span><span style="color: #000000;">22</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">7</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span> |
|||
printf(1,fmt,apply({num,den,quo,rem},poly)) |
|||
<span style="color: #0000FF;">}</span> |
|||
end for |
|||
</syntaxhighlight> |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">fmt</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"%40s / %-16s = %25s rem %s\n"</span> |
|||
<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: #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;">num</span><span style="color: #0000FF;">,</span><span style="color: #000000;">den</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;">i</span><span style="color: #0000FF;">],</span> |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">quo</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rem</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">poly_div</span><span style="color: #0000FF;">(</span><span style="color: #000000;">num</span><span style="color: #0000FF;">,</span><span style="color: #000000;">den</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: #000000;">fmt</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">({</span><span style="color: #000000;">num</span><span style="color: #0000FF;">,</span><span style="color: #000000;">den</span><span style="color: #0000FF;">,</span><span style="color: #000000;">quo</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rem</span><span style="color: #0000FF;">},</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |