finding the derivative of a polynomial

Question

I wondering symbolically how you would parse a polynomial into a function and return the derivative. What data structure would I use or method to parse the polynomial? Preferably without using any libraries, as this question could pop up in a technical interview.

polynomial-> of nth degree

def derivative(polynomial):
    return derivative

Example:

f(x)  = 2x^2+3x+1
f'(x) = 4x+3

I don't want a solution, this is not homework but a hint of where I would start.

Answer 1

If the polynomial equation is given as a list. For eg: p=[9,4,12,2] return value will be [27, 8, 12]

     def derivative(p):
        derv=[]
        for i in range(len(p)-1):
            derv.append((len(p)-i-1)*p[i])
        return derv

Answer 2

Lines 7 and 8 will extract coefficients and exponents in lists regardless of the sign. Lines 13 and 14 remove empty strings from lists. This is not perfect, but it is simpler:

import pdb;                                                                                                                                                                                                                                                                 
import re;                                                                      


poly = input("Input the polynomial you want to find its derivative : ")         

coefficients = re.split("x\^[+-]?[0-9]+",poly)                                  
exponents = re.split("[+-]?[0-9]+x\^",poly)                                     

print(coefficients)                                                            
print(exponents)                                                               

coefficients = [ i for i in coefficients if i !='']                             
exponents = [i for i in exponents if i !='']                                    

print(coefficients)                                                            
print(exponents)                                                               

derivative=""                                                                   
for i in range(len(coefficients)):                                              
    print(coefficients[i])                                                      
    print(exponents[i])                                                         
    coefficient = int(coefficients[i])*int(exponents[i])                        
    exponent = int(exponents[i]) - 1                                            
    if exponent == 0:                                                           
        derivative +=  str(coefficient)                                         
    else:                                                                       
        derivative +=  str(coefficient) + "x^" + str(exponent)                  

print("The original value is {0}".format(poly))                                 
print("The derivative is {0}".format(derivative))          

Answer 3

My solution uses iterables where the i-th element is the coefficient of x^i, so for p(x) = 3*x^5 + 2*x^3 + x^2 + 5 the input would be [5, 0, 1, 2, 0, 3]. The derivate is p'(x) = 15*x^4 + 6*x^2 + 2*x, so the expected result should be [0, 2, 6, 0, 15].

>>> import itertools, operator
>>> coeff = [5, 0, 1, 2, 0, 3]
>>> print list(itertools.imap(operator.mul, itertools.islice(coeff, 1, None), itertools.count(1)))
[0, 2, 6, 0, 15]

Update: I wanted to be really tricky here using iterators and all, but my solution turned out to be more than twice as slow as GregS's. Somebody could explain me from where it came this slowness?

>>> print timeit.repeat("poly(coeff)", "poly = lambda coeff: [coeff[i] * i for i in range(1, len(coeff))]; coeff = [1, 0, 0, 5, 0, -29]")
[1.7786244418210748, 1.7956598059847046, 1.7500179643792024]
>>> print timeit.repeat("poly(coeff)", "import operator, itertools; poly = lambda coeff: list(itertools.imap(operator.mul, itertools.islice(coeff, 1, None), itertools.count(1))); coeff = [1, 0, 0, 5, 0, -29]")
[4.01759841913463, 4.152715700867423, 5.195021813889031]

Answer 4

A polynomial in a single variable can be represented simply as an array containing the coefficients. So for example 1 + 5x³ - 29x⁵ can be expressed as [1, 0, 0, 5, 0, -29]. Expressed in this form the derivative is easy to compute.

suppose poly is a python list as above. Then

deriv_poly = [poly[i] * i for i in range(1, len(poly))]

For sparse polynomial other representations are relatively easy, such as a list of pairs (coefficient, exponent) or dictionary mapping exponents to coefficients.

Parsing the expression is more complicated but using various parsing frameworks should be easy because the grammar is comparatively simple.

Answer 5

I came up with this now. What you want is this:

1. Parse the polynomial: you need to have a predefined pattern. The more "untrusted" or "wild" the input is, the better you will have to parse it. You could use regular expressions.

2. Have the basic components of the equation (coeff, power_of_x) list.

3. Do the math (derivative formula)

4. Return an equation the way the input was given.

This gives you:

import re

def read(eq):
    terms = eq.split('+')
    equation = [re.split('x\^?', t) for t in terms]
    eq_map = []
    for e in equation:
        try:
            coeff = int(e[0])
        except ValueError:
            coeff = 1
        try:
            power = int(e[1])
        except ValueError:
            power = 1
        except IndexError:
            power = 0
        eq_map.append((coeff, power))
    return eq_map

def write(eq_map):
    def str_power(p):
        if p == 0:
            return ''
        elif p == 1:
            return 'x'
        else:
            return 'x^%d' % (p,)

    def str_coeff(c):
        return '' if c == 1 else str(c)
    str_terms = [(str_coeff(c) + str_power(p)) for c, p in eq_map]
    return "+".join(str_terms)

def derivative(eq):
    eq_map = read(eq)
    der_map = [(p*c, p-1) for c, p in eq_map[:-1]]
    return write(der_map)

def run(eq):
    print eq, '->', derivative(eq)

run("2x^2+3x+1")
run("x^3+2x^2+1")

This is very basic. For example: 2*x^3 will not work because of the "*". Of course there are many cases in which it won't work, but that's the basic idea.

Answer 6

Not a pretty or concrete solution, but you can improve it :) Used dictionary to store coefficients and their powers, with powers as keys.

import re
def polynomial(data):
    coeffs = {}
    splits = map(str.strip, re.split(r"([+ \-])",data))
    sign = 1
    for p in splits:
        if p in "+-":
            sign = 1 if p == '+' else -1
            continue
        s = re.split('[^0-9]+', p)
        coeff = int(s[0])
        if len(s) == 1:
            pow = 0
        elif s[1] == '':
            pow = 1
        else:
            pow = int(s[1])
        coeffs[pow] = sign * coeff
    return coeffs

def derive(poly):
    return dict([(p-1, p*c) for p,c in poly.items() if p != 0])

def print_poly(poly, var = 'x'):
    print(''.join(['{0}{1}{2}^{3}'.format('+-'[c<0],c,var,p) for p,c in sorted(poly.items(), reverse = True)]))

Answer 7

Well, I believe the starting point would be to define the basic components of the expression.

When you look at a function and want to process it like that, it's basically a grammar, it can be a bit complicated depending on how much detail you want to allow.

Your grammar has the form of EXPRESSION.

EXPRESSION can be either: TERM (where your function is basically something like nx^y) or TERM OPERATOR EXPRESSION

If you can parse a function like this, you simply need to define the rules for handling a TERM, and then recursively apply the same method for the rest of the expression.

Your polynomial will always have the form nx^y, with some simplifications for cases where y is 0 or 1, or when n is 1 and is omitted.

This is how I would approach it without using any additional libs. If you want, I can try and explain my point further.

By the way, I know my answer doesn't exactly address Python or the data structures to use, but it is one possible way of approaching this kind of problems.

Answer 8

In my experience matrices are often very useful in representing polynomials