Polynomial derivative
Given a polynomial, represented by an ordered list of its coefficients by increasing degree (e.g. [-1, 6, 5] represents 5x2+6x-1), calculate the polynomial representing the derivative. For example, the derivative of the aforementioned polynomial is 10x+6, represented by [6, 10]. Test cases: 5, -3x+4, 5x2+6x-1, x3-2x2+3x-4, -x4-x3+x+1
- Related task
ALGOL 68
<lang algol68>BEGIN # find the derivatives of polynominals, given their coefficients #
# returns the derivative polynominal of the polynominal defined by # # the array of coeficients, where the coefficients are in # # order of ioncreasing power of x # OP DERIVATIVE = ( []INT p )[]INT: BEGIN [ 1 : UPB p - 1 ]INT result; FOR i FROM 2 TO UPB p DO result[ i - 1 ] := ( i - 1 ) * p[ i ] OD; result END # DERIVATIVE # ; # prints the polynomial defined by the coefficients in p # OP SHOW = ( []INT p )VOID: BEGIN BOOL first := TRUE; FOR i FROM UPB p BY -1 TO LWB p DO IF p[ i ] /= 0 THEN IF first THEN IF p[ i ] < 0 THEN print( ( "-" ) ) FI ELSE IF p[ i ] < 0 THEN print( ( " - " ) ) ELSE print( ( " + " ) ) FI FI; first := FALSE; IF i = LWB p THEN print( ( whole( ABS p[ i ], 0 ) ) ) ELSE IF ABS p[ i ] > 1 THEN print( ( whole( ABS p[ i ], 0 ) ) ) FI; print( ( "x" ) ); IF i > LWB p + 1 THEN print( ( "^", whole( i - 1, 0 ) ) ) FI FI FI OD; IF first THEN # all coefficients were 0 # print( ( "0" ) ) FI END # SHOW # ; # task test cases # PROC test = ( []INT p )VOID: BEGIN SHOW p; print( ( " -> " ) ); SHOW DERIVATIVE p; print( ( newline ) ) END; test( ( 5 ) ); test( ( 4, -3 ) ); test( ( -1, 6, 5 ) ); test( ( -4, 3, -2, 1 ) ); test( ( 1, 1, 0, -1, -1 ) )
END</lang>
- Output:
5 -> 0 -3x + 4 -> -3 5x^2 + 6x - 1 -> 10x + 6 x^3 - 2x^2 + 3x - 4 -> 3x^2 - 4x + 3 -x^4 - x^3 + x + 1 -> -4x^3 - 3x^2 + 1
Factor
<lang factor>USING: generalizations kernel math.polynomials prettyprint ;
{ 5 } { 4 -3 } { -1 6 5 } { -4 3 -2 1 } { 1 1 0 -1 -1 }
[ pdiff ] 5 napply .s clear</lang>
- Output:
{ } { -3 } { 6 10 } { 3 -4 3 } { 1 0 -3 -4 }
The implementation of pdiff
:
<lang factor>USING: kernel math.vectors sequences ; IN: math.polynomials
- pdiff ( p -- p' ) dup length <iota> v* rest ;</lang>
FreeBASIC
<lang freebasic>sub polydiff( p() as integer )
'differentiates the polynomial 'p(0) + p(1)x + p(2)x^2 +... + p(n)x^n 'in place dim as integer i, n = ubound(p) if n=0 then p(0)=0 return end if for i = 0 to n - 1 p(i) = (i+1)*p(i+1) next i redim preserve p(0 to n-1) return
end sub
sub print_poly( p() as integer )
'quick and dirty display of the poly if ubound(p)=0 and p(0)=0 then print 0 return end if for i as integer = 0 to ubound(p) if i = 0 then print p(i);" "; if i = 1 and p(i)>0 then print using "+ #x";p(i); if i = 1 and p(i)<0 then print using "- #x";-p(i); if i > 1 and p(i)>0 then print using "+ #x^#";p(i);i; if i > 1 and p(i)<0 then print using "- #x^#";-p(i);i; next i print
end sub
'test cases redim as integer p(0) p(0) = 5 print_poly(p()) print "Differentiates to " polydiff(p()) print_poly(p()): print
redim as integer p(1) p(0) = 4 : p(1) = -3 print_poly(p()) print "Differentiates to " polydiff(p()) print_poly(p()): print
redim as integer p(2) p(0) = -1 : p(1) = 6 : p(2) = 5 print_poly(p()) print "Differentiates to " polydiff(p()) print_poly(p()): print
redim as integer p(3) p(0) = 4 : p(1) = 3 : p(2) = -2 : p(3) = 1 print_poly(p()) print "Differentiates to " polydiff(p()) print_poly(p()): print
redim as integer p(4) p(0) = 1 : p(1) = 1 : p(2) = 0 : p(3) = -1 : p(4) = -1 print_poly(p()) print "Differentiates to " polydiff(p()) print_poly(p()): print</lang>
- Output:
5 Differentiates to 0
4 - 3x Differentiates to -3
-1 + 6x+ 5x^2 Differentiates to 6 + %10x
4 + 3x- 2x^2+ 1x^3 Differentiates to 3 - 4x+ 3x^2
1 + 1x- 1x^3- 1x^4 Differentiates to
1 - 3x^2- 4x^3
Haskell
<lang haskell>deriv = zipWith (*) [1..] . tail
main = mapM_ (putStrLn . line) ps
where line p = "\np = " ++ show p ++ "\np' = " ++ show (deriv p) ps = [[5],[4,-3],[-1,6,5],[-4,3,-2,1],[1,1,0,-1,-1]]</lang>
main p = [5] p' = [] p = [4,-3] p' = [-3] p = [-1,6,5] p' = [6,10] p = [-4,3,-2,1] p' = [3,-4,3] p = [1,1,0,-1,-1] p' = [1,0,-3,-4]
With fancy output
<lang haskell>{-# language LambdaCase #-}
showPoly [] = "0" showPoly p = foldl1 (\r -> (r ++) . term) $
dropWhile null $ foldMap (\(c, n) -> [show c ++ expt n]) $ zip p [0..] where expt = \case 0 -> "" 1 -> "*x" n -> "*x^" ++ show n
term = \case [] -> "" '0':'*':t -> "" '-':'1':'*':t -> " - " ++ t '1':'*':t -> " + " ++ t '-':t -> " - " ++ t t -> " + " ++ t
main = mapM_ (putStrLn . line) ps
where line p = "\np = " ++ showPoly p ++ "\np' = " ++ showPoly (deriv p) ps = [[5],[4,-3],[-1,6,5],[-4,3,-2,1],[1,1,0,-1,-1]]</lang>
main p = 5 p' = 0 p = 4 - 3*x p' = -3 p = -1 + 6*x + 5*x^2 p' = 6 + 10*x p = -4 + 3*x - 2*x^2 + x^3 p' = 3 - 4*x + 3*x^2 p = 1 + 1*x - 1*x^3 - 1*x^4 p' = 1 - 3*x^2 - 4*x^
jq
Adapted from Wren (with corrections)
Works with gojq, the Go implementation of jq
The following definition of polyPrint has no restriction on the degree of the polynomial.
<lang jq># The input should be a non-empty array of integers representing a polynomial.
- The output likewise represents its derivative.
def derivative:
. as $p | if length == 1 then [0] else reduce range(0; length-1) as $i (.[1:]; .[$i] = $p[$i+1] * ($i + 1) ) end;
def polyPrint:
def ss: ["\u2070", "\u00b9", "\u00b2", "\u00b3", "\u2074", "\u2075", "\u2076", "\u2077", "\u2078", "\u2079"]; def digits: tostring | explode[] | [.] | implode | tonumber; ss as $ss | def superscript: if . <= 1 then "" else reduce digits as $d (""; . + $ss[$d] ) end;
. as $p | if length == 1 then .[0] | tostring else reduce range(0; length) as $i ([]; if $p[$i] != 0
then (if $i > 0 then "x" else "" end) as $x
| ( if $i > 0 and ($p[$i]|length) == 1
then (if $p[$i] == 1 then "" else "-" end) else ($p[$i]|tostring) end ) as $c | . + ["\($c)\($x)\($i|superscript)"]
else . end ) | reverse | join("+") | gsub("\\+-"; "-") end ;
def task:
def polys: [ [5], [4, -3], [-1, 6, 5], [-4, 3, -2, 1], [1, 1, 0, -1, -1] ];
"Example polynomials and their derivatives:\n", ( polys[] | "\(.) -> \(derivative)" ),
"\nOr in normal mathematical notation:\n", ( polys[] | "Polynomial : \(polyPrint)", "Derivative : \(derivative|polyPrint)\n" ) ;
task</lang>
- Output:
Example polynomials and their derivatives: [5] -> [0] [4,-3] -> [-3] [-1,6,5] -> [6,10] [-4,3,-2,1] -> [3,-4,3] [1,1,0,-1,-1] -> [1,0,-3,-4] Or in normal mathematical notation: Polynomial : 5 Derivative : 0 Polynomial : -3x+4 Derivative : -3 Polynomial : 5x²+6x-1 Derivative : 10x+6 Polynomial : x³-2x²+3x-4 Derivative : 3x²-4x+3 Polynomial : -x⁴-x³+x+1 Derivative : -4x³-3x²+1
Julia
<lang julia>using Polynomials
testcases = [
("5", [5]), ("-3x+4", [4, -3]), ("5x2+6x-1", [-1, 6, 5]), ("x3-2x2+3x-4", [-4, 3, -2, 1]), ("-x4-x3+x+1", [1, 1, 0, -1, -1]),
]
for (s, coef) in testcases
println("Derivative of $s: ", derivative(Polynomial(coef)))
end
</lang>
- Output:
Derivative of 5: 0 Derivative of -3x+4: -3 Derivative of 5x2+6x-1: 6 + 10*x Derivative of x3-2x2+3x-4: 3 - 4*x + 3*x^2 Derivative of -x4-x3+x+1: 1 - 3*x^2 - 4*x^3
Perl
<lang perl>use strict; use warnings; use feature 'say'; use utf8; binmode(STDOUT, ':utf8');
sub pp {
my(@p) = @_; return 0 unless @p; my @f = $p[0]; push @f, ($p[$_] != 1 and $p[$_]) . 'x' . ($_ != 1 and (qw<⁰ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹>)[$_]) for grep { $p[$_] != 0 } 1 .. $#p; ( join('+', reverse @f) =~ s/-1x/-x/gr ) =~ s/\+-/-/gr
}
for ([5], [4,-3], [-1,3,-2,1], [-1,6,5], [1,1,0,-1,-1]) {
my @poly = @$_; say 'Polynomial: ' . join(', ', @poly) . ' ==> ' . pp @poly; $poly[$_] *= $_ for 0 .. $#poly; shift @poly; say 'Derivative: ' . (@poly ? join', ', @poly : 0) . ' ==> ' . pp(@poly) . "\n";
}</lang>
- Output:
Polynomial: 5 ==> 5 Derivative: 0 ==> 0 Polynomial: 4, -3 ==> -3x+4 Derivative: -3 ==> -3 Polynomial: -1, 3, -2, 1 ==> x³-2x²+3x-1 Derivative: 3, -4, 3 ==> 3x²-4x+3 Polynomial: -1, 6, 5 ==> 5x²+6x-1 Derivative: 6, 10 ==> 10x+6 Polynomial: 1, 1, 0, -1, -1 ==> -x⁴-x³+x+1 Derivative: 1, 0, -3, -4 ==> -4x³-3x²+1
Phix
-- -- demo\rosetta\Polynomial_derivative.exw -- with javascript_semantics function derivative(sequence p) if p={} then return {} end if sequence r = repeat(0,length(p)-1) for i=1 to length(r) do r[i] = i*p[i+1] end for return r end function function poly(sequence si) -- display helper, copied from demo\rosetta\Polynomial_long_division.exw string r = "" for t=length(si) to 1 by -1 do integer sit = si[t] if sit!=0 then if sit=1 and t>1 then r &= iff(r=""? "":" + ") elsif sit=-1 and t>1 then r &= iff(r=""?"-":" - ") else if r!="" then r &= iff(sit<0?" - ":" + ") sit = abs(sit) end if r &= sprintf("%d",sit) end if r &= iff(t>1?"x"&iff(t>2?sprintf("^%d",t-1):""):"") end if end for if r="" then r="0" end if return r end function constant tests = {{5},{4,-3},{-1,6,5},{-4,3,-2,1},{1,1,0,-1,-1}} for i=1 to length(tests) do sequence t = tests[i], r = derivative(t) printf(1,"%20s ==> %16s (internally %V -> %V)\n",{poly(t),poly(r),t,r}) end for ?"done" {} = wait_key()
- Output:
5 ==> 0 (internally {5} -> {}) -3x + 4 ==> -3 (internally {4,-3} -> {-3}) 5x^2 + 6x - 1 ==> 10x + 6 (internally {-1,6,5} -> {6,10}) x^3 - 2x^2 + 3x - 4 ==> 3x^2 - 4x + 3 (internally {-4,3,-2,1} -> {3,-4,3}) -x^4 - x^3 + x + 1 ==> -4x^3 - 3x^2 + 1 (internally {1,1,0,-1,-1} -> {1,0,-3,-4})
Raku
<lang perl6>use Lingua::EN::Numbers:ver<2.8+>;
sub pretty (@poly) {
join( '+', (^@poly).reverse.map: { @poly[$_] ~ "x{.&super}" } )\ .subst(/['+'|'-']'0x'<[⁰¹²³⁴⁵⁶⁷⁸⁹]>*/, , :g).subst(/'x¹'<?before <-[⁰¹²³⁴⁵⁶⁷⁸⁹]>>/, 'x')\ .subst(/'x⁰'$/, ).subst(/'+-'/, '-', :g).subst(/(['+'|'-'|^])'1x'/, {"$0x"}, :g) || 0
}
for [5], [4,-3], [-1,3,-2,1], [-1,6,5], [1,1,0,-1,-1] -> $test {
say "Polynomial: " ~ "[{$test.join: ','}] ➡ " ~ pretty $test; my @poly = |$test; (^@poly).map: { @poly[$_] *= $_ }; shift @poly; say "Derivative: " ~ "[{@poly.join: ','}] ➡ " ~ pretty @poly; say ;
}</lang>
- Output:
Polynomial: [5] ➡ 5 Derivative: [] ➡ 0 Polynomial: [4,-3] ➡ -3x+4 Derivative: [-3] ➡ -3 Polynomial: [-1,3,-2,1] ➡ x³-2x²+3x-1 Derivative: [3,-4,3] ➡ 3x²-4x+3 Polynomial: [-1,6,5] ➡ 5x²+6x-1 Derivative: [6,10] ➡ 10x+6 Polynomial: [1,1,0,-1,-1] ➡ -x⁴-x³+x+1 Derivative: [1,0,-3,-4] ➡ -4x³-3x²+1
Sidef
<lang ruby>func derivative(f) {
Poly(f.coeffs.map_2d{|e,k| [e-1, k*e] }.flat...)
}
var coeffs = [
[5], [4,-3], [-1,6,5], [-4,3,-2,1], [-1, 6, 5], [1,1,0,-1,-1],
]
for c in (coeffs) {
var poly = Poly(c.flip) var derv = derivative(poly)
var d = { derv.coeff(_) }.map(0..derv.degree)
say "Polynomial : #{'%20s' % c} = #{poly}" say "Derivative : #{'%20s' % d} = #{derv || 0}\n"
}</lang>
- Output:
Polynomial : [5] = 5 Derivative : [0] = 0 Polynomial : [4, -3] = -3*x + 4 Derivative : [-3] = -3 Polynomial : [-1, 6, 5] = 5*x^2 + 6*x - 1 Derivative : [6, 10] = 10*x + 6 Polynomial : [-4, 3, -2, 1] = x^3 - 2*x^2 + 3*x - 4 Derivative : [3, -4, 3] = 3*x^2 - 4*x + 3 Polynomial : [-1, 6, 5] = 5*x^2 + 6*x - 1 Derivative : [6, 10] = 10*x + 6 Polynomial : [1, 1, 0, -1, -1] = -x^4 - x^3 + x + 1 Derivative : [1, 0, -3, -4] = -4*x^3 - 3*x^2 + 1
Wren
<lang ecmascript>var derivative = Fn.new { |p|
if (p.count == 1) return [0] var d = p[1..-1].toList for (i in 0...d.count) d[i] = p[i+1] * (i + 1) return d
}
var ss = ["", "", "\u00b2", "\u00b3", "\u2074", "\u2075", "\u2076", "\u2077", "\u2078", "\u2079"]
// for n <= 20 var superscript = Fn.new { |n| (n < 10) ? ss[n] : (n < 20) ? ss[1] + ss[n - 10] : ss[2] + ss[0] }
var polyPrint = Fn.new { |p|
if (p.count == 1) return p[0].toString var terms = [] for (i in 0...p.count) { if (p[i] == 0) continue var c = p[i].toString if (i > 0 && p[i].abs == 1) c = (p[i] == 1) ? "" : "-" var x = (i > 0) ? "x" : "" terms.add("%(c)%(x)%(superscript.call(i))") } return terms[-1..0].join("+").replace("+-", "-")
}
System.print("The derivatives of the following polynomials are:\n") var polys = [ [5], [4, -3], [-1, 6, 5], [-4, 3, -2, 1], [1, 1, 0, -1, -1] ] for (poly in polys) {
var deriv = derivative.call(poly) System.print("%(poly) -> %(deriv)")
} System.print("\nOr in normal mathematical notation:\n") for (poly in polys) {
var deriv = derivative.call(poly) System.print("Polynomial : %(polyPrint.call(poly))") System.print("Derivative : %(polyPrint.call(deriv))\n")
}</lang>
- Output:
The derivatives of the following polynomials are: [5] -> [0] [4, -3] -> [-3] [-1, 6, 5] -> [6, 10] [-4, 3, -2, 1] -> [3, -4, 3] [1, 1, 0, -1, -1] -> [1, 0, -3, -4] Or in normal mathematical notation: Polynomial : 5 Derivative : 0 Polynomial : -3x+4 Derivative : -3 Polynomial : 5x²+6x-1 Derivative : 10x+6 Polynomial : x³-2x²+3x-4 Derivative : 3x²-4x+3 Polynomial : -x⁴-x³+x+1 Derivative : -4x³-3x²+1
XPL0
<lang XPL0>int IntSize, Cases, Case, Len, Deg, Coef; [IntSize:= @Case - @Cases; Cases:=[[ 5],
[ 4, -3], [-1, 6, 5], [-4, 3, -2, 1], [ 1, 1, 0, -1, -1], [ 0]];
for Case:= 0 to 5-1 do
[Len:= (Cases(Case+1) - Cases(Case)) / IntSize; for Deg:= 0 to Len-1 do [Coef:= Cases(Case, Deg); if Deg = 0 then Text(0, "[") else [IntOut(0, Coef*Deg); if Deg < Len-1 then Text(0, ", "); ]; ]; Text(0, "]^M^J"); ];
]</lang>
- Output:
[] [-3] [6, 10] [3, -4, 3] [1, 0, -3, -4]