Polynomial long division: Difference between revisions
→{{header|Phix}}
Line 1,838:
1x^2 + -6x + 17 , & -23x + -14 \\
\end{array}</math>
=={{header|Phix}}==
<lang Phix>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)
while length(d)<length(n) do d &=0 end while
integer dn = degree(n),
dd = degree(d)
if dd<0 then throw("divide by zero") end if
sequence quot = repeat(0,dn)
while dn>=dd do
integer k = dn-dd
integer qk = n[dn]/d[dd]
quot[k+1] = qk
sequence d2 = d[1..length(d)-k]
for i=1 to length(d2) do
n[-i] -= d2[-i]*qk
end for
dn = degree(n)
end while
return {quot,n} -- (n is now the remainder)
end function
function poly(sequence si)
-- display helper
string r = ""
for t=length(si) to 1 by -1 do
integer sit = si[t]
if sit!=0 then
if sit=1 and t>1 then
r &= iff(r=""? "":" + ")
elsif sit=-1 and t>1 then
r &= iff(r=""?"-":" - ")
else
if r!="" then
r &= iff(sit<0?" - ":" + ")
sit = abs(sit)
end if
r &= sprintf("%d",sit)
end if
r &= iff(t>1?"x"&iff(t>2?sprintf("^%d",t-1):""):"")
end if
end for
if r="" then r="0" end if
return r
end function
function polyn(sequence s)
for i=1 to length(s) do
s[i] = poly(s[i])
end for
return s
end function
constant tests = {{{-42,0,-12,1},{-3,1}},
{{-3,1},{-42,0,-12,1}},
{{-42,0,-12,1},{-3,1,1}},
{{2,3,1},{1,1}},
{{3,5,6,-4,1},{1,2,1}},
{{3,0,7,0,0,0,0,0,3,0,0,1},{1,0,0,5,0,0,0,1}},
{{-56,87,-94,-55,22,-7},{2,0,1}},
}
constant fmt = "%40s / %-16s = %25s rem %s\n"
for i=1 to length(tests) do
sequence {num,denom} = tests[i],
{quot,rmdr} = poly_div(num,denom)
printf(1,fmt,polyn({num,denom,quot,rmdr}))
end for</lang>
{{out}}
<pre>
x^3 - 12x^2 - 42 / x - 3 = x^2 - 9x - 27 rem -123
x - 3 / x^3 - 12x^2 - 42 = 0 rem x - 3
x^3 - 12x^2 - 42 / x^2 + x - 3 = x - 13 rem 16x - 81
x^2 + 3x + 2 / x + 1 = x + 2 rem 0
x^4 - 4x^3 + 6x^2 + 5x + 3 / x^2 + 2x + 1 = x^2 - 6x + 17 rem -23x - 14
x^11 + 3x^8 + 7x^2 + 3 / x^7 + 5x^3 + 1 = x^4 + 3x - 5 rem -16x^4 + 25x^3 + 7x^2 - 3x + 8
-7x^5 + 22x^4 - 55x^3 - 94x^2 + 87x - 56 / x^2 + 2 = -7x^3 + 22x^2 - 41x - 138 rem 169x + 220
</pre>
=={{header|PicoLisp}}==
| |||