Polynomial synthetic division: Difference between revisions
m
syntax highlighting fixup automation
m (→{{header|Phix}}: syntax coloured, made p2js compatible) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 9:
{{trans|Python}}
<
‘Fast polynomial division by using Extended Synthetic Division. Also works with non-monic polynomials.’
V out = copy(dividend)
Line 27:
print(‘ #. / #. =’.format(n, D), end' ‘ ’)
V (a, b) = extended_synthetic_division(n, D)
print(‘#. remainder #.’.format(a, b))</
{{out}}
Line 37:
=={{header|C++}}==
{{trans|Java}}
<
* C++ Polynomial Sythetic Division
* GNU Compile example for filename <synthdiv.cpp>
Line 163:
}
</syntaxhighlight>
=={{header|C sharp|C#}}==
{{trans|Java}}
<
using System.Collections.Generic;
using System.Linq;
Line 215:
}
}
</syntaxhighlight>
=={{header|Delphi}}==
Line 222:
{{Trans|Go}}
Thanks Rudy Velthuis for the [https://github.com/rvelthuis/DelphiBigNumbers Velthuis.BigRationals] library.<br>
<syntaxhighlight lang="delphi">
program Polynomial_synthetic_division;
Line 300:
writeln(result[0].ToString, ' remainder ', result[1].ToString);
readln;
end.</
{{out}}
<pre>[1 -12 0 -42 ] / [1 -3 ] = [1 -9 -27 ] remainder [-123 ]</pre>
Line 307:
=={{header|Go}}==
{{trans|Python}}
<
import (
Line 341:
Q, R := div(N, D)
fmt.Printf("%v / %v = %v remainder %v\n", N, D, Q, R)
}</
{{out}}
<pre>
Line 348:
=={{header|Haskell}}==
<
normalized :: (Eq a, Num a) => [a] -> [a]
Line 366:
k = length p1 - length as
a:as = normalized p2
ker = negate <$> (as ++ repeat 0)</
<pre>*Main> shortDiv [1,-12,0,-42] [1,1,-3]
Line 376:
For monic divisors it is possible to perform purely integral computations (without Fractional constraint):
<
isMonic = ([1] ==) . take 1 . normalized
Line 390:
k = length p1 - length as
_:as = normalized p2
ker = negate <$> as ++ repeat 0</
<pre>shortDivMonic [1,-12,0,-42] [1,1,-3 :: Int]
Line 399:
Solving this the easy way:
<
Task example:
<
┌────────┬────┐
│1 _9 _27│_123│
└────────┴────┘
</syntaxhighlight>
=={{header|Java}}==
{{trans|Python}}
<
public class Test {
Line 446:
};
}
}</
<pre>[1, -12, 0, -42] / [1, -3] = [[1, -9, -27], [-123]]</pre>
Line 452:
=={{header|Julia}}==
{{trans|Perl}}
<
result = copy(dividend)
quotientlen = length(divisor) - 1
Line 472:
println("[$n] / [$d] = [$quotient] with remainder [$remainder]")
end
</
<pre>
[[1, -12, 0, -42]] / [[1, -3]] = [[1, -9, -27]] with remainder [[-123]]
Line 480:
=={{header|Kotlin}}==
{{trans|Python}}
<
fun extendedSyntheticDivision(dividend: IntArray, divisor: IntArray): Pair<IntArray, IntArray> {
Line 509:
print("${n2.contentToString()} / ${d2.contentToString()} = ")
println("${q2.contentToString()}, remainder ${r2.contentToString()}")
}</
{{out}}
Line 520:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
num = MakePolynomial[{1, -12, 0, -42}, x];
den = MakePolynomial[{1, -3}, x];
PolynomialQuotient[num, den, x]
PolynomialRemainder[num, den, x]</
{{out}}
<pre>-27 - 9 x + x^2
Line 531:
=={{header|Nim}}==
{{trans|Kotlin}}
<
type Polynomial = seq[int]
Line 558:
let d2 = @[1, 1, 1, 1]
let (q2, r2) = extendedSyntheticDivision(n2, d2)
echo &"{n2} / {d2} = {q2}, remainder {r2}"</
{{out}}
Line 567:
=={{header|Perl}}==
{{trans|Raku}}
<
my($numerator,$denominator) = @_;
my @result = @$numerator;
Line 588:
print poly_divide([1, -12, 0, -42], [1, -3]);
print poly_divide([1, 0, 0, 0, -2], [1, 1, 1, 1]);</
{{out}}
<pre>[1 -12 0 -42] / [1 -3] = [1 -9 -27], remainder [-123]
Line 595:
=={{header|Phix}}==
{{trans|Kotlin}}
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">extendedSyntheticDivision</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">dividend</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">divisor</span><span style="color: #0000FF;">)</span>
Line 625:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%v / %v = %v, remainder %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
{{out}}
<pre>
Line 639:
{{works with|Python 2.7}}
{{works with|Python 3.x}}
<
from __future__ import division
Line 671:
D = [1, -3]
print(" %s / %s =" % (N,D), " %s remainder %s" % extended_synthetic_division(N, D))
</syntaxhighlight>
Sample output:
Line 682:
{{trans|Python}}
<
(require racket/list)
;; dividend and divisor are both polynomials, which are here simply lists of coefficients.
Line 715:
(define D '(1 -3))
(define-values (Q R) (extended-synthetic-division N D))
(printf "~a / ~a = ~a remainder ~a~%" N D Q R))</
{{out}}
Line 727:
{{works with|Rakudo|2018.09}}
<syntaxhighlight lang="raku"
my @result = @numerator;
my $end = @denominator.end;
Line 747:
my %result = synthetic-division( @n, @d );
say "[{@n}] / [{@d}] = [%result<quotient>], remainder [%result<remainder>]";
}</
{{out}}
<pre>[1 -12 0 -42] / [1 -3] = [1 -9 -27], remainder [-123]
Line 754:
=={{header|REXX}}==
<
/* extended to support order of divisor >1 */
call set_dd '1 0 0 0 -1'
Line 823:
Return list']'
</syntaxhighlight>
{{out}}
<pre>[1,-12,0,-42] / [1,-3]
Line 834:
===Java Interoperability===
{{Out}}Best seen running in your browser either by [https://scalafiddle.io/sf/59vpjcQ/0 ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/uUk8yRPnQdGdS1aAUFjhmA Scastie (remote JVM)].
<
object PolynomialSyntheticDivision extends App {
Line 862:
}%s")
}</
=={{header|Sidef}}==
{{trans|Python}}
<
var end = divisor.end
var out = dividend.clone
Line 889:
var (n, d) = ([1, -12, 0, -42], [1, -3])
print(" %s / %s =" % (n, d))
print(" %s remainder %s\n" % extended_synthetic_division(n, d))</
{{out}}
[1, -12, 0, -42] / [1, -3] = [1, -9, -27] remainder [-123]
Line 898:
This uses a common utility proc <tt>range</tt>, and a less common one called <tt>lincr</tt>, which increments elements of lists. The routine for polynomial division is placed in a namespace ensemble, such that it can be conveniently shared with other commands for polynomial arithmetic (eg <tt>polynomial multiply</tt>).
<
# start defaults to 0: [range 5] = {0 1 2 3 4}
proc range {a {b ""}} {
Line 947:
puts "$top / $btm = $div"
}
test</
{{out}}
Line 955:
{{trans|Kotlin}}
{{libheader|Wren-dynamic}}
<
var Solution = Tuple.create("Solution", ["quotient", "remainder"])
Line 984:
var sol2 = extendedSyntheticDivision.call(n2, d2)
System.write("%(n2) / %(d2) = ")
System.print("%(sol2.quotient), remainder %(sol2.remainder)")</
{{out}}
Line 996:
=={{header|zkl}}==
{{trans|Python}}
<
# Fast polynomial division by using Extended Synthetic Division. Also works with non-monic polynomials.
# dividend and divisor are both polynomials, which are here simply lists of coefficients. Eg: x^2 + 3x + 5 will be represented as [1, 3, 5]
Line 1,016:
separator := -(divisor.len() - 1);
return(out[0,separator], out[separator,*]) # return quotient, remainder.
}</
<
N,D := T(1, -12, 0, -42), T(1, -3);
print(" %s / %s =".fmt(N,D));
println(" %s remainder %s".fmt(extended_synthetic_division(N,D).xplode()));</
{{out}}
<pre>
|