Anonymous user
Polynomial long division: Difference between revisions
→E: new example
(→{{header|Ruby}}: ++ R) |
(→E: new example) |
||
Line 228:
return 0;
}</lang>
=={{header|E}}==
This program has some unnecessary features contributing to its length:
* It creates polynomial objects rather than performing its operations directly on arrays.
* It includes code for printing polynomials nicely.
* It prints the intermediate steps of the division.
<pre>pragma.syntax("0.9")
pragma.enable("accumulator")
def superscript(x, out) {
if (x >= 10) { superscript(x // 10) }
out.print("⁰¹²³⁴⁵⁶⁷⁸⁹"[x %% 10])
}
def makePolynomial(initCoeffs :List) {
def degree := {
var i := initCoeffs.size() - 1
while (i >= 0 && initCoeffs[i] <=> 0) { i -= 1 }
if (i < 0) { -Infinity } else { i }
}
def coeffs := initCoeffs(0, degree + 1)
def polynomial {
/** Print the polynomial (not necessary for the task) */
to __printOn(out) {
out.print("(λx. ")
var first := true
for i in (0..!(coeffs.size())).descending() {
def coeff := coeffs[i]
if (coeff <=> 0) { continue }
if (!first) { out.print(" ") }
if (coeff <=> 1 && !(i <=> 0)) {
# no coefficient written if it's 1 and not the constant term
} else if (first) { out.print(coeff)
} else if (coeff > 0) { out.print("+ ", coeff)
} else { out.print("- ", -coeff)
}
if (i <=> 0) { # no x if it's the constant term
} else if (i <=> 1) { out.print("x")
} else { out.print("x"); superscript(i, out)
}
first := false
}
out.print(")")
}
/** Evaluate the polynomial (not necessary for the task) */
to run(x) {
return accum 0 for i => c in coeffs { _ + c * x**i }
}
to degree() { return degree }
to coeffs() { return coeffs }
to highestCoeff() { return coeffs[degree] }
/** Could support another polynomial, but not part of this task.
Computes this * x**power. */
to timesXToThe(power) {
return makePolynomial([0] * power + coeffs)
}
/** Multiply (by a scalar only). */
to multiply(scalar) {
return makePolynomial(accum [] for x in coeffs { _.with(x * scalar) })
}
/** Subtract (by another polynomial only). */
to subtract(other) {
def oc := other.coeffs() :List
return makePolynomial(accum [] for i in 0..(coeffs.size().max(oc.size())) { _.with(coeffs.fetch(i, fn{0}) - oc.fetch(i, fn{0})) })
}
/** Polynomial long division. */
to quotRem(denominator, trace) {
var numerator := polynomial
require(denominator.degree() >= 0)
if (numerator.degree() < denominator.degree()) {
return [makePolynomial([]), denominator]
} else {
var quotientCoeffs := [0] * (numerator.degree() - denominator.degree())
while (numerator.degree() >= denominator.degree()) {
trace.print(" ", numerator, "\n")
def qCoeff := numerator.highestCoeff() / denominator.highestCoeff()
def qPower := numerator.degree() - denominator.degree()
quotientCoeffs with= (qPower, qCoeff)
def d := denominator.timesXToThe(qPower) * qCoeff
trace.print("- ", d, " (= ", denominator, " * ", qCoeff, "x"); superscript(qPower, trace); trace.print(")\n")
numerator -= d
trace.print(" -------------------------- (Quotient so far: ", makePolynomial(quotientCoeffs), ")\n")
}
return [makePolynomial(quotientCoeffs), numerator]
}
}
}
return polynomial
}</pre>
<lang e>def n := makePolynomial([-42, 0, -12, 1])
def d := makePolynomial([-3, 1])
println("Numerator: ", n)
println("Denominator: ", d)
def [q, r] := n.quotRem(d, stdout)
println("Quotient: ", q)
println("Remainder: ", r)
</lang>
Output:
Numerator: (λx. x³ - 12x² - 42)
Denominator: (λx. x - 3)
(λx. x³ - 12x² - 42)
- (λx. x³ - 3.0x²) (= (λx. x - 3) * 1.0x²)
-------------------------- (Quotient so far: (λx. x²))
(λx. -9.0x² - 42.0)
- (λx. -9.0x² + 27.0x) (= (λx. x - 3) * -9.0x¹)
-------------------------- (Quotient so far: (λx. x² - 9.0x))
(λx. -27.0x - 42.0)
- (λx. -27.0x + 81.0) (= (λx. x - 3) * -27.0x⁰)
-------------------------- (Quotient so far: (λx. x² - 9.0x - 27.0))
Quotient: (λx. x² - 9.0x - 27.0)
Remainder: (λx. -123.0)
=={{header|Fortran}}==
| |||