71 lines
2 KiB
Text
71 lines
2 KiB
Text
-- 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)
|
|
d = deep_copy(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 quo = repeat(0,dn),
|
|
rem = deep_copy(n)
|
|
while dn>=dd do
|
|
integer k = dn-dd, qk = rem[dn]/d[dd]
|
|
sequence d2 = d[1..length(d)-k]
|
|
quo[k+1] = qk
|
|
for i=1 to length(d2) do
|
|
integer mi = -i
|
|
rem[mi] -= d2[mi]*qk
|
|
end for
|
|
dn = degree(rem)
|
|
end while
|
|
return {quo,rem}
|
|
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
|
|
|
|
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,den} = tests[i],
|
|
{quo,rem} = poly_div(num,den)
|
|
printf(1,fmt,apply({num,den,quo,rem},poly))
|
|
end for
|