current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 7 down vote favorite

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?

share|improve this question
4  
Clearly the polynomial should be stored the other way round. – Gareth Rees 7 hours ago
up vote 4 down vote accepted

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.

share|improve this answer
    
1. I intentionally left out error handling, but thanks for including it in a final answer. 2. As this exercise is purely pedagogical, I'm rather curious as to why creating a copy of poly is not an expensive operation. I intentionally tried to avoid such a step, but that effort appears to have been in vain. Do you know why? Thanks. – lnNoam 4 hours ago
1  
If you're OK with messing up the original list, you can replace the creation of the new list poly = poly[:-dev] with removing the list's elements: poly[-dev:] = list(). – Vedran Šego 3 hours ago
up vote 1 down vote

I would use this function signature:

def poly_deriv(poly, nth=1):
    …

"dev" is too cryptic for my taste. The second parameter should default to 1, as I would expect it to be the common case.

Your code works on poly in place, rather than on a copy, and thus trashes the contents of the array. That's unacceptable, especially considering that the result is shorter than the input, so a copy is unavoidable.

It is not obvious to me what c and r represent.

Counting loops are usually done using for … in range(…). I think that it would be easier to work term by term, repeatedly differentiating it.

def poly_deriv(poly, nth=1):
    degree = len(poly) - 1
    if degree - nth < 0:
        return [0]   # or an empty list? Your decision.
    poly = poly[: -nth]
    for i in range(len(poly)):
        for exponent in range(degree - i, degree - i - nth, -1):
            poly[i] = exponent * poly[i]
    return poly

As @GarethRees has pointed out in a comment, the little-endian convention for representing polynomials is clearly technically superior, since the index of each element corresponds to the degree. The big-endian representation just happens to match the human writing convention.

share|improve this answer
up vote 1 down vote

Following @GarethRees' sound advice, I'll use reversed indexes in the polynomials. In programming, like in math, you take advantage of abstractions. Instead of a monolithic algorithm, you split it into meaningful functions. I'd write it a more functional style (no in-place updates, only expressions):

import functools
import operator

def mul(xs):
    return functools.reduce(operator.mul, xs, 1) 

def poly_derivative(poly, n):
    return [x * mul(range(i - n, i)) for (i, x) in enumerate(poly[n:], n + 1)]
share|improve this answer
up vote 0 down vote

I don't have much experience with it myself, but I would probably do something of this nature:

def poly_dev(poly, dev):
    for dev in xrange(dev):
        poly = poly[:-1]
        max_expo = len(poly)
        for i in xrange(max_expo):
            poly[i] *= (max_expo - i)
    return poly
share|improve this answer

We are looking for answers that provide insightful observations about the code in the question. Answers that consist of independent solutions with no justification do not constitute a code review, and may be removed.
2  
Welcome to Code Review. Please explain what you mean by "something of this nature", or why you think anything should be changed at all. Otherwise, it's a code dump, not a code review. – 200_success♦ 6 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.