Higher Derivatives

[steelmanronald06]

Okay, I'm stumped.  I need to create a function to solve Higher Derivatives.  I don't even know where to start. I don't do much math based programming, so I don't even know how the pre-packaged functions in PHP work.  So, can someone help point me in the right direction?  Is this even possible? I would assume so, but I imagine it will require numerous switch/case, wouldn't it?  ???

[btherl]

Can you give an example of the kind of problem you want to solve?

[steelmanronald06]

Just derivatives in general. I mean, I want to make a form and the user enter the problem and it solve it.  I mean I don't support cheating, but something to check your answers.

[btherl]

A general solver will be very complex.. I think you'll need to limit what you want to solve somehow.  If you can limit it to expressions of the form c1x^n + c2x^(n-1) + ... then it's very simple.

 

How to implement it depends very much on what classes of problems you need to solve.  If you don't want to solve problems involving sin() then no need to implement sin().  Same for other functions like e^x, tan(), tanh(), etc etc.

 

Maybe you can make an extensible data structure so you can add other functions later on.  Something like

 

$equation = array(

  'type' => 'function',

  'name' => 'sin',

  'arguments' => array(

    array(

      'type' => 'var',

      'name' => 'x',

    ),

  ),

);

 

And there you have it, sin(x).  That structure can be extended to handle multiple arguments and can be nested as far as you want.

 

Going for lunch now   Will check for replies later.

[steelmanronald06]

Hmm..Well, i want to cover it a-z....so, I imagine i'll have to create functions inside a class for every possible outcome....which could be a lot unless I can find a way to call more than one function and have it work the problem and still give the correct answer. :-\  Derivatives are hard enough on paper, so I kind of figured it would be near impossible to make some php code to give ya the answer.

[cooldude832]

derivations are not something php is really meant to do (beyond basic power rule derivations such as y=x^2 dy/dx = x)  The problem is that derivation is not a clear cut processes (although simpler than integration) it requires a lot of complex analysis on a human level to generate solutions that a computer would be incapable of easily being told how to solve.  Not to mention the difficulties in coming up with an input system that creates a standard uniform system for anaylsis.  Also you run into issues when you try and get partials of equations with greater than 2 variables and more differential type situations.  Since your question is more or less about higher order differentials i.e dy^2/dx in my case above is 1, but for these basic equations (y=x^n+b) can easily be solved for higher order differentials because its a very simple pattern) but equations such as (y=ln(x^ln(z))) would be nearly impossible to solve for by a computer because it has to first read the highest power level and work in a top down fashion to develop an answer.  Then beyond that it would need to have a complex mathematics library to know how to simplify answers becuase we can look for dy/dz dy/dx dx/dz dz/dy all are possible solutions we might need.

[steelmanronald06]

I guess I could always make a calculator like thing that when "buttons" are pushed it will insert a php math function, and have them enter the problem exactly as written. would that work?

[ToonMariner]

this is actually fairly straight forward PROVIDED you have some control over the input.

 

y = ax^n + bx^m + c ..... adnausea...

 

if the user etnters that as a tring then you need to split the expression on the +( or -) elements AND REMEBER THEM!

 

then you need to extract the power vals (n,m) etc... and remeber which part of teh expression they belong to. Then teh multipliers....

 

the actual math is very simple...

 

y = ax^n + bx^m + cx

 

dy/dx = (a*n)x^(n-1) + (m*b)x^(m-1) + c

 

the rule is...

 

multiply by the old power and reduce the power by 1 - that is differentiation...

 

I would be more than happy to help out on this one steelman... if you want me too that is;)

 

the complexity comes in when you have expresions in the function that you need to differentiate like y = sin^3 x etc etc but they can be recognized and handled effectively I am sure....

 

 

Christ this brings back some math from my 6th form and degree courses!!!!

 

oh the days....

[akitchin]

just going to point out that the first derivative of x^2 is 2x, not x, and therefore the second derivative is 2, not 1.

 

you could make a series of cases; if a student needs a sheet of standard derivatives (trig functions, exponential functions, etc.) then it's likely that a program would too.  if you can standardize the input and expect only a function of a single variable, it shouldn't be too tough, as it's a matter of processing the expression consistently.  you'd need to ponder a bit about certain algorithms (product law, chain rule, etc.), but the basics are there.  forming higher-order derivatives is then merely a matter of passing the return from the first derivative back into the differentiation function.

 

even multiple variables shouldn't be too tough as long as you're calculating a partial derivative, because the unaffected variables can simply be treated as constants (given the definition of a partial).

 

keep in mind, there's a reason people pay lots of chedda for math programs (granted Maple is major overkill for a differentiation).

[akitchin]

functions i can think of that you might want (off the top of my head):

 

derivative() => calculates the derivative of an atomic expression

product_law() => rips an expression into its factor expressions, calculates the derivative

chain_rule() => works backward through a compound expression to calculate the derivative

 

that last one will be a bitch.  to be honest, you're probably better off verifying your work by asking someone better at math than you are.  you can only program math as well as you can do math.

[roopurt18]

I can't remember all of the rules for derivatives, but I don't think this problem is terribly complicated.  My recommendation is to take the input and build an expression tree out of it the same way that compilers do *hint* *hint*.

 

Some example expressions and their expression trees:

2x^3 + 5

    +-- 5           +-- 3
    |               |
+ --+       +-- ^ --+
    |       |       |
    +-- * --+       +-- x
            |
    +-- 2

*****************************
*****************************

3ln(1 / (2x^3 + 5))

                               +-- 5           +-- 3
                               |               |
                  +-- ( -- + --+       +-- ^ --+
                  |            |       |       |
    +-- ln -- / --+            +-- * --+       +-- x
    |             |                    |
* --+             +-- 1                +-- 2
    |
    +-- 3

 

So the first task is writing a parser that can take an expression as a string and convert it into such a tree.  You'll notice that orders of operation with high precedence are deeper in the tree; this gives us a hint with our next task.

 

From here, you need to create a function that takes this tree structure and creates a derivative string of it.  We'll call the function create_derivative_string(); it takes two parameters, the tree structure and the value we're solving for.

 

<?php
  $expression = "2x^3 + 5";
  $tree = parse_expression($expression);
  $dExpression = create_derivative_string($tree, "x");
  // $dExpression now contains: "3*2x^(3-1) + 0"
?>

 

You must now pass $dExpression into a regular expression parser that evaluates an expression:

<?php
  // cont'd from above
  $dTree = parse_expression($dExpression);
  $output = evaluate_expression($dTree);
  // $output now contains: "6x^2"
?>

 

The function that converts the input expression into a tree is nothing more than a finite state machine.  If you want to do individual research on this stuff, there is no better resource than "The Dragon Book":

http://en.wikipedia.org/wiki/Compilers:_Principles%2C_Techniques%2C_and_Tools

 

Otherwise, googling for "computer languages" or "computer grammars" might pull up some decent hits.

 

Also, feel free to PM me if you get stuck anywhere.  I've written a basic C compiler and I worked on another project where we were given a fake language and had to create a parser for it; that was a while ago though so I may be a bit rusty!

[emehrkay]

functions i can think of that you might want (off the top of my head):

 

derivative() => calculates the derivative of an atomic expression

product_law() => rips an expression into its factor expressions, calculates the derivative

chain_rule() => works backward through a compound expression to calculate the derivative

 

that last one will be a bitch.  to be honest, you're probably better off verifying your work by asking someone better at math than you are.  you can only program math as well as you can do math.

 

this would be pretty cool to program

[utexas_pjm]

The function that converts the input expression into a tree is nothing more than a finite state machine.

 

The function(s) will model an FSM but in less abstract terms you'll most likely be constructing a recursive descent parser.  There's a pretty good howto (complete with pseduo code) here: http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm, you'll want to focus on the "The classic solution" or "Precedence climbing" sections.

 

If you'd like to see a PHP implementation you can have a look here: http://junction.googlecode.com/svn/trunk/Junction/Expression/.  While this particular example does not construct a syntax tree, it could have (and actually used to). 

 

Best,

 

Patrick

[btherl]

Hmm..Well, i want to cover it a-z....so, I imagine i'll have to create functions inside a class for every possible outcome....which could be a lot unless I can find a way to call more than one function and have it work the problem and still give the correct answer. :-\  Derivatives are hard enough on paper, so I kind of figured it would be near impossible to make some php code to give ya the answer.

 

You want to cover EVERY possibility?  That's just not possible.  Even the most powerful software has limitations.  The first step is to decide what the scope of your program will be.  For example, year 12 derivatives (in my country that's the final year of school), 1st year applied maths derivatives.  What you need to cover then defines what your interface needs to be, and what your data structures need to cope with.

 

roopurt's approach is definitely the most flexible.  With that kind of structure, you just need to deal with simple rules at each node in the tree.  The data structure in my earlier post is an example implementation of such a tree.

[cooldude832]

that last one will be a bitch.  to be honest, you're probably better off verifying your work by asking someone better at math than you are.  you can only program math as well as you can do math.

 

I disagree with th at statement because much of calculus is basic programing ideas.  For example look at some infinite series/sums like the McLaren series .  Many of your favorite calculators like a Ti-81 Plus (and computer functions) use these to calculate complicated equations. Such as the fact that any square root can be rewritten as the sum of an infinite series.  I know the Ti series calculators take the first 20 summations of infinite series for functions such as Square roots and Powers.

 

As for finding out how to write this in script, look for some scripts written in C/C++ (probably more in C or even basic) and simply manually modify them to  PHP.  You could probably extract functions off a TI-81 or higher calculator if you have the USB version, or find the data on a website and modify a preexisting script to php.

 

Still the basic obsticle is coming over the fact that the chain rule is ever present in a derivative. I guess you can use some sort of array system like as an example

<?php
$equation = "ln(x^2)";
$derivatives = array();
$sub_count = 0;
//Some stuff to figure out inner most function is X^2 giving us 
$sub_equation[$sub_count]['eq'] = x^2;
$sub_count++;
//rewriting the main is ln($sub_equation);
//Now we can check if sub equation is in simplest form if it is we act upon it
$sub_equation[0]['derrivative'] = 2x;
//Now we know that we have a derrivative that is
//dx(ln($sub_equation))
//which we cna use from programing rules to be (1/$sub_equation)d$sub_equation
//we know d$sub_eqation is 2x as solved above so we know our derrivative is
$answer = (1/$sub_equation[0]['eq'])*($sub_equation[0]['derrivative']);
echo $answer;
//prints 2x(1/x^2) which is in simpliest form known at this point

[Barand]

Is that the McLaren series of Formula 1 cars?

[cooldude832]

okay so my spelling is off a tad.  Its a specific version of the taylor series based on a fixed intial value.

http://en.wikipedia.org/wiki/Taylor_series

 

its a good submation for values based on derrivations such as the submation on that article of sin(x)

Just another useful tool if a derrivation system can be found, especially since its core function is around  increasing order differentals

[steelmanronald06]

wow!  had lots of homework and i'm just now getting to read replies.  There are a lot of ideas here, some I think might really work with a bit of tweaking and tailoring.  I'm going to see what I can come up with. I think that I will be able to do it with a form, kind of like a calculator, and require little user input.

[cooldude832]

Like everyone has been saying you are going to need to focus on 3 key elements

1) Standardization of input.

2) Library of the differential rules

3) Figuring out how to handle the chain rule effect

 

once you get that you can actually apply your derivative to do talyor series for say and make your own calculator.

[roopurt18]

One more thing to consider, you might need to pass the initial user input through an expression simplifier.

 

For example, if the user enters: x * x + 5

 

You want to make sure that your program outputs 2x rather than 1

[akitchin]

well if he follows the proper rules of differentiation, he'll end up at 2x anyway [(f*g)' = f'*g + f*g'].  i actually really like that expression tree you mentioned roopurt, that's one hell of an effective way of turning it into something entirely manageable.

[roopurt18]

Well, what I mean is as an expression tree:

x * x
    +-- x
    |
* --+
    |
    +-- x

 

If you differentiate each branch of the tree separately it'll become:

    +-- 1
    |
* --+
    |
    +-- 1

 

Then when you evaluate that you arrive at 1, instead of 2x.

 

So I revise my approach to:

 

1)  Accept user's input

2)  Break into expression tree

3)  Simplify expression

4)  Break simplified expression into tree

5)  Create the derivative function of the tree

6)  Evaluate the derivative function

 

Steps 3 and 6 are really the same function, namely one that evaluates and simplifies the expression.  It should change things like 2 * (x + x)  into 4x

[btherl]

The problem there roopurt is that you differentiated the branches of the tree but not the "*" node.  The product rule gives:

 

  (x*x)'

= (x'x + xx')

= (x + x)

= 2x

[cooldude832]

So do we think object oreintation is the best method here treating the equation as an object with sub parts such as varibles who have sub parts of modifiers (ln, trig, e etc) and coiefecines (2x, 1.5x 3x2) and powers (1,2,x,4x)  and so forth and then sub dividng the sub divisions as needed?

[btherl]

I think there's some benefit to treating coefficients and powers specially.  But functions I would treat as first class objects rather than modifiers.  Things like e^x can get special treatment, as a first class function.  Eg

 

(ln(sin(x)))'

 

Is this x modified by sin modified by ln?  I think it's simpler to see it as ln of sin of x.  Then the chain rule can be applied as an operation on the tree rather than an operation on modifiers of an object.