Polynomial long division: Difference between revisions
Content added Content deleted
(→{{header|Ruby}}: ++ R) |
(→E: new example) |
||
Line 228: | Line 228: | ||
return 0; |
return 0; |
||
}</lang> |
}</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}}== |
=={{header|Fortran}}== |