Anonymous user
Polynomial long division: Difference between revisions
→{{header|Nim}}
Alextretyak (talk | contribs) (Added 11l) |
|||
Line 2,460:
output:
<pre>{-27 - 9 x + x^2, -123}</pre>
=={{header|Nim}}==
<lang Nim>const MinusInfinity = -1
type
Polynomial = seq[int]
Term = tuple[coeff, exp: int]
func degree(p: Polynomial): int =
## Return the degree of a polynomial.
## "p" is supposed to be normalized.
result = if p.len > 0: p.len - 1 else: MinusInfinity
func normalize(p: var Polynomial) =
## Normalize a polynomial, removing useless zeroes.
while p[^1] == 0: discard p.pop()
func `shr`(p: Polynomial; n: int): Polynomial =
## Shift a polynomial of "n" positions to the right.
result.setLen(p.len + n)
result[n..^1] = p
func `*=`(p: var Polynomial; n: int) =
## Multiply in place a polynomial by an integer.
for item in p.mitems: item *= n
p.normalize()
func `-=`(a: var Polynomial; b: Polynomial) =
## Substract in place a polynomial from another polynomial.
for i, val in b: a[i] -= val
a.normalize()
func longdiv(a, b: Polynomial): tuple[q, r: Polynomial] =
## Compute the long division of a polynomial by another.
## Return the quotient and the remainder as polynomials.
result.r = a
if b.degree < 0: raise newException(DivByZeroDefect, "divisor cannot be zero.")
result.q.setLen(a.len)
while (let k = result.r.degree - b.degree; k >= 0):
var d = b shr k
result.q[k] = result.r[^1] div d[^1]
d *= result.q[k]
result.r -= d
result.q.normalize()
const Superscripts: array['0'..'9', string] = ["⁰", "¹", "²", "³", "⁴", "⁵", "⁶", "⁷", "⁸", "⁹"]
func superscript(n: Natural): string =
## Return the Unicode string to use to represent an exponent.
if n == 1:
return ""
for d in $n:
result.add(Superscripts[d])
func `$`(term: Term): string =
## Return the string representation of a term.
if term.coeff == 0: "0"
elif term.exp == 0: $term.coeff
else:
let base = 'x' & superscript(term.exp)
if term.coeff == 1: base
elif term.coeff == -1: '-' & base
else: $term.coeff & base
func `$`(poly: Polynomial): string =
## return the string representation of a polynomial.
for idx in countdown(poly.high, 0):
let coeff = poly[idx]
var term: Term = (coeff: coeff, exp: idx)
if result.len == 0:
result.add $term
else:
if coeff > 0:
result.add '+'
result.add $term
elif coeff < 0:
term.coeff = -term.coeff
result.add '-'
result.add $term
const
N = @[-42, 0, -12, 1]
D = @[-3, 1]
let (q, r) = longdiv(N, D)
echo "N = ", N
echo "D = ", D
echo "q = ", q
echo "r = ", r</lang>
{{out}}
<pre>N = x³-12x²-42
D = x-3
q = x²-9x-27
r = -123</pre>
=={{header|OCaml}}==
| |||