As a personal exercise, I'm trying to write an algorithm to compute the n-th derivative of an ordered, simplified polynomial (i.e., all like terms have been combined). The polynomial is passed as an ordered list where the i-th index corresponds (though is not equivalent) to the coefficient of x
to the n-th power.
Example:
Take the derivative of: \$3x^3 + 5x^2 + 2x + 2\$ -> [3,5,2,2]
- 1st derivative: \$9x^2 + 10x + 2\$
- 2nd derivative: \$18x + 10\$
- 3rd derivative: \$18\$
- 4th...n-th derivative: \$0\$
Implementation in Python:
def poly_dev(poly, dev):
"""
:param poly: a polynomial
:param dev: derivative desired, e.g., 2nd
"""
c = 0 # correction
r = dev # to remove
while dev > 0:
for i in range(1, len(poly)-c):
poly[i-1] = (len(poly)-(i+c))*poly[i-1]
dev -= 1 # I suspect this
c += 1 # this can be simplified
return poly[:-r]
E.g., print(poly_dev(poly = [3,5,2,2], dev = 2))
I have a math background, but I'm only starting to learn about computer science concepts like Complexity Theory.
I've intentionally tried to avoid reversing a list, as I know that can be expensive. What other steps can I change to decrease this procedure's run time?