Polynomial long division: Difference between revisions
Content added Content deleted
(Translate Ocaml into F#) |
(→{{header|Kotlin}}: replace code with more succinct code that provides an easy-to-use API) |
||
Line 2,388: | Line 2,388: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
<lang |
<lang kotlin>package de.roland_illig.poly |
||
class Polynom(private vararg val factors: Double) { |
|||
typealias IAE = IllegalArgumentException |
|||
operator fun div(divisor: Polynom): Pair<Polynom, Polynom> { |
|||
data class Solution(val quotient: DoubleArray, val remainder: DoubleArray) |
|||
var curr = canonical().factors |
|||
val right = divisor.canonical().factors |
|||
val result = mutableListOf<Double>() |
|||
fun polyDegree(p: DoubleArray): Int { |
|||
for ( |
for (base in curr.size - right.size downTo 0) { |
||
val res = curr.last() / right.last() |
|||
result += res |
|||
curr = curr.copyOfRange(0, curr.size - 1) |
|||
for (i in 0 until right.size - 1) |
|||
curr[base + i] -= res * right[i] |
|||
} |
|||
val quot = Polynom(*result.asReversed().toDoubleArray()) |
|||
val rem = Polynom(*curr).canonical() |
|||
return Pair(quot, rem) |
|||
} |
} |
||
return Int.MIN_VALUE |
|||
} |
|||
private fun canonical(): Polynom { |
|||
fun polyShiftRight(p: DoubleArray, places: Int): DoubleArray { |
|||
if ( |
if (factors.last() != 0.0) return this |
||
for (newLen in factors.size downTo 1) |
|||
val pd = polyDegree(p) |
|||
if ( |
if (factors[newLen - 1] != 0.0) |
||
return Polynom(*factors.copyOfRange(0, newLen)) |
|||
throw IAE("The number of places to be shifted is too large") |
|||
return Polynom(factors[0]) |
|||
} |
} |
||
val d = p.copyOf() |
|||
for (i in pd downTo 0) { |
|||
d[i + places] = d[i] |
|||
d[i] = 0.0 |
|||
} |
|||
return d |
|||
} |
|||
override fun toString() = "Polynom(${factors.joinToString(" ")})" |
|||
fun polyMultiply(p: DoubleArray, m: Double) { |
|||
for (i in 0 until p.size) p[i] *= m |
|||
} |
} |
||
fun main() { |
|||
fun polySubtract(p: DoubleArray, s: DoubleArray) { |
|||
val num = Polynom(-42.0, 0.0, -12.0, 1.0) |
|||
val den = Polynom(-3.0, 1.0, 0.0, 0.0) |
|||
} |
|||
val (quot, rem) = num / den |
|||
fun polyLongDiv(n: DoubleArray, d: DoubleArray): Solution { |
|||
if (n.size != d.size) { |
|||
throw IAE("Numerator and denominator vectors must have the same size") |
|||
} |
|||
var nd = polyDegree(n) |
|||
val dd = polyDegree(d) |
|||
if (dd < 0) { |
|||
throw IAE("Divisor must have at least one one-zero coefficient") |
|||
} |
|||
if (nd < dd) { |
|||
throw IAE("The degree of the divisor cannot exceed that of the numerator") |
|||
} |
|||
val n2 = n.copyOf() |
|||
val q = DoubleArray(n.size) // all elements zero by default |
|||
while (nd >= dd) { |
|||
val d2 = polyShiftRight(d, nd - dd) |
|||
q[nd - dd] = n2[nd] / d2[nd] |
|||
polyMultiply(d2, q[nd - dd]) |
|||
polySubtract(n2, d2) |
|||
nd = polyDegree(n2) |
|||
} |
|||
return Solution(q, n2) |
|||
} |
|||
fun polyShow(p: DoubleArray) { |
|||
val pd = polyDegree(p) |
|||
for (i in pd downTo 0) { |
|||
val coeff = p[i] |
|||
if (coeff == 0.0) continue |
|||
print (when { |
|||
coeff == 1.0 -> if (i < pd) " + " else "" |
|||
coeff == -1.0 -> if (i < pd) " - " else "-" |
|||
coeff < 0.0 -> if (i < pd) " - ${-coeff}" else "$coeff" |
|||
else -> if (i < pd) " + $coeff" else "$coeff" |
|||
}) |
|||
if (i > 1) print("x^$i") |
|||
else if (i == 1) print("x") |
|||
} |
|||
println() |
|||
} |
|||
print("$num / $den = $quot remainder $rem") |
|||
fun main(args: Array<String>) { |
|||
val n = doubleArrayOf(-42.0, 0.0, -12.0, 1.0) |
|||
val d = doubleArrayOf( -3.0, 1.0, 0.0, 0.0) |
|||
print("Numerator : ") |
|||
polyShow(n) |
|||
print("Denominator : ") |
|||
polyShow(d) |
|||
println("-------------------------------------") |
|||
val (q, r) = polyLongDiv(n, d) |
|||
print("Quotient : ") |
|||
polyShow(q) |
|||
print("Remainder : ") |
|||
polyShow(r) |
|||
}</lang> |
}</lang> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Polynom(-42.0 0.0 -12.0 1.0) / Polynom(-3.0 1.0 0.0 0.0) = Polynom(-27.0 -9.0 1.0) remainder Polynom(-123.0) |
|||
Numerator : x^3 - 12.0x^2 - 42.0 |
|||
Denominator : x - 3.0 |
|||
------------------------------------- |
|||
Quotient : x^2 - 9.0x - 27.0 |
|||
Remainder : -123.0 |
|||
</pre> |
</pre> |
||