Algorithm to compute the n-th derivative of a polynomial in Python

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?

You are going one by one derivative, when you could easily do them all at once. With a little multiply-and-divide trick, you could save on complexity.

Also, your function will return wrong results for negative dev (it should raise an exception instead).

Further, your function will mess up the original list:

>>> poly = [3, 5, 2, 2]
>>> print(poly_dev(poly, 2))
[18, 10]
>>> print(poly)
[18, 10, 2, 2]

Here is my take on it:

def poly_dev(poly, dev):
    if dev == 0:
        return poly[:]
    if dev > len(poly):
        return list()
    if dev < 0:
        raise ValueError("negative derivative")
    p = 1
    for k in range(2, dev+1):
        p *= k
    poly = poly[:-dev]
    n = len(poly)-1
    for i in range(len(poly)):
        poly[n-i] *= p
        p = p * (i+dev+1) // (i+1)
    return poly

So, the first thing I do after handling trivial cases is computing the multiplication factor for the first coefficient and take only a copy of the part of the list that I need (to avoid messing up the original).

Then I multiply each coefficient with the multiplication factor p, followed by computing the next one, meaning "divide by the smallest member of the product that defines p and multiply by the one bigger then the biggest one".

Notice that the division is //, which is integer division. That way you don't lose precision (and I think it's a bit quicker than the floating point one, but I'm not sure right now).

It may look redundant to multiply and later divide by the same number, but it's less work than multiplying dev numbers in each go.

Also, it would be more Pythonic to have enumerate(reversed(poly)) instead of range(len(poly)) in the for loop, but then we'd still need n-i somewhere, so this seemed cleaner to me for this particular case. Maybe I'm missing something obvious here.

StackExchange Code Review Q#131722, answer score: 5