Algorithm for differentiation

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm

Algorithm for differentiation

Post by Faizur »

I want an algorithm to perform the Differentiation of any equation (not numerically) i.e if the input is y=x^2 then the desired output should be dy/dx=2*x .
Can some one provide me with such an algorithm or give any references related to that.
Thnx for your help in advance.

A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

It's not that hard, actually. Just parse the expression, build the parse tree, then apply the derivation rules you learned in school.

E.g. if the expression is E := (E1)*(E2) for some expressions E1,E2, so that the tree T for E looks like

Code: Select all

 / \
T1 T2
where T1 and T2 are the trees for E1 and E2. The tree T' for the derivative E' of E becomes

Code: Select all

      / \
     /   \
    /     \
   *       *
  / \     / \
T1' T2  T2' T1
Where T1' and T2' are the trees for the derivates of E1 and E2.

The only hard thing is to simplify the expression. E.g. the derivative of 5*x should be 5, not 0*x + 1*5 (of course, there are other expressions where it is not so obvious which form is the "simplest"). I doubt that there's a foolproof way of doing this, so after the trivial simplifications (eliminating zeros, etc), its more or less down to heuristics.

Post Reply

Return to “Algorithms”