74 lines
2 KiB
Text
74 lines
2 KiB
Text
-- demo/rosetta/Polynomial_long_division.exw
|
|
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
|