2

I'm trying to find the best method/algorithm for computing the derivative of a typed mathematical function in Javascript symbolically. Each equation will only have a single variable. I started with a typed expression which is then converted to RPN (reverse polish notation) using Dijkstra's shunting-yard algorithm to convert the infix equation into a postfix one. My next ideas was to use this to create an expression tree, which ends up looking something like this:

Equation: 25x^2 + 61x + 3

RPN: 25 x 2 ^ * 61 x * + 3 +

Expression tree: Expression tree

I looked at what the "solved" expression tree should look like to get an idea of what needed to be done: Solved tree

Derivative (without simplification): x^(2-1)*2*25+61

I was thinking I could recursively apply the differentiation rules (product, quotient, sum, difference, etc) using a postorder traversal and replace the "nodes" depending on the operator.

However, after looking at the derivative's expression tree, I realized that I couldn't easily apply something like the product rule to a node that still had children (ie. this)

So my primary question is: Are there any known algorithms similar to shunting-yard for efficiently computing symbolic derivatives programmatically?

kpjVideo
  • 413
  • 2
  • 6
  • 21

1 Answers1

0

The Shunting Yard algorithm is more about parsing than transformation, so it seems IMHO that it is better to traverse the resulting expression tree, building the derivative expression in a separate tree. For simple expressions the replace-in-place might appear to be the solution, but as the mathematical expressions become more complex, the differentiation rules (see https://en.wikipedia.org/wiki/Differentiation_rules) will make the tree operations complex, especially as the algorithm dives into the child nodes to further differentiate. For example...

  • The product rule is f(x) g(x) = f'(x) g(x) + f(x) g'(x)

...and thus, to differentiate the following...

  • x * ln( x )

...results in...

  • ( x )' * ln( x ) + x * ( ln( x ) )'
  • 1 * ln( x ) + x * 1/x

I think you will also find that once the derivative is created, that there will need to be some algebraic cleanup of the expression. Following the example, the algorithm will need a second pass to walk the derivative tree and simplify the expression based on algebraic rules, for example...

  • 1 * n = n
  • n * 1 / n = 1

...so the final result is...

  • ln( x ) + 1

There's actually a great resource at https://www.derivative-calculator.net/ that is an implementation of what you are seeking to do in code, and might be worthwhile experimenting with to get a feel for the logic involved. Additionally, there is an excellent implementation of the Shunting Yard algorithm at Calculate string value in javascript, not using eval.

Trentium
  • 3,419
  • 2
  • 12
  • 19