views:

466

answers:

6

Hi! I'm interested in building a derivative calculator. I've racked my brains over solving the problem, but I haven't found a right solution at all. May you have a hint how to start? Thanks

I'm sorry! I clearly want to make symbolic differentiation.

Let's say you have the function f(x) = x^3 + 2x^2 + x

I want to display the derivative, in this case f'(x) = 3x^2 + 4x + 1

I'd like to implement it in objective-c for the iPhone.

+4  A: 

I assume that you're trying to find the exact derivative of a function. (Symbolic differentiation)

You need to parse the mathematical expression and store the individual operations in the function in a tree structure.

For example, x + sin²(x) would be stored as a + operation, applied to the expression x and a ^ (exponentiation) operation of sin(x) and 2.

You can then recursively differentiate the tree by applying the rules of differentiation to each node. For example, a + node would become the u' + v', and a * node would become uv' + vu'.

SLaks
+4  A: 

you need to remember your calculus. basically you need two things: table of derivatives of basic functions and rules of how to derivate compound expressions (like d(f + g)/dx = df/dx + dg/dx). Then take expressions parser and recursively go other the tree. (http://www.sosmath.com/tables/derivative/derivative.html)

Andrey
+1  A: 

For what kinds of operations are you wanting to compute a derivative? If you allow trigonometric functions like sine, cosine and tangent, these are probably best stored in a table while others like polynomials may be much easier to do. Are you allowing for functions to have multiple inputs,e.g. f(x,y) rather than just f(x)?

Polynomials in a single variable would be my suggestion and then consider adding in trigonometric, logarithmic, exponential and other advanced functions to compute derivatives which may be harder to do.

JB King
Just one variable, f(x).
burki
+3  A: 

Parse your string into an S-expression (even though this is usually taken in Lisp context, you can do an equivalent thing in pretty much any language), easiest with lex/yacc or equivalent, then write a recursive "derive" function. In OCaml-ish dialect, something like this:

let rec derive var = function
    | Const(_) -> Const(0)
    | Var(x) -> if x = var then Const(1) else Deriv(Var(x), Var(var))
    | Add(x, y) -> Add(derive var x, derive var y)
    | Mul(a, b) -> Add(Mul(a, derive var b), Mul(derive var a, b))
    ...

(If you don't know OCaml syntax - derive is two-parameter recursive function, with first parameter the variable name, and the second being mathched in successive lines; for example, if this parameter is a structure of form Add(x, y), return the structure Add built from two fields, with values of derived x and derived y; and similarly for other cases of what derive might receive as a parameter; _ in the first pattern means "match anything")

After this you might have some clean-up function to tidy up the resultant expression (reducing fractions etc.) but this gets complicated, and is not necessary for derivation itself (i.e. what you get without it is still a correct answer).

When your transformation of the s-exp is done, reconvert the resultant s-exp into string form, again with a recursive function

Amadan
F# is so beautiful
erikkallen
+2  A: 

SLaks already described the procedure for symbolic differentiation. I'd just like to add a few things:

  • Symbolic math is mostly parsing and tree transformations. ANTLR is a great tool for both. I'd suggest starting with this great book Language implementation patterns
  • There are open-source programs that do what you want (e.g. Maxima). Dissecting such a program might be interesting, too (but it's probably easier to understand what's going on if you tried to write it yourself, first)
  • Probably, you also want some kind of simplification for the output. For example, just applying the basic derivative rules to the expression 2 * x would yield 2 + 0*x. This can also be done by tree processing (e.g. by transforming 0 * [...] to 0 and [...] + 0 to [...] and so on)
nikie
+1  A: 

Symbolic differentiation over common functions (+, -, *, /, ^, sin, cos, etc.) ignoring regions where the function or its derivative is undefined is easy. What's difficult, perhaps counterintuitively, is simplifying the result afterward.

To do the differentiation, store the operations in a tree (or even just in Polish notation) and make a table of the derivative of each of the elementary operations. Then repeatedly apply the chain rule and the elementary derivatives, together with setting the derivative of a constant to 0. This is fast and easy to implement.

Charles