Symbiotic differentiation using recursion for c++.

[Wafflecone67]

I was given an assignment by my professor and I still don't have any idea where to start or how to get started. Here are the prerequisites https://i.imgur.com/ixLwvuG.png. Any help would be appreciated.

[Duthomhas]

That assignment simply lists the basic rules of differentiation and gives an example.

What year level are you? Have you taken any Calculus at all?


For this assignment you don’t actually need anything from <cmath> — you are not expected to compute any numbers (beyond basic operations). What you are expected to do is take a polynomial (as text!) and produce another (as text!).

For example, given

    2x^3

you should be able to produce

    6x^2

That is because

    (2x³)′ = 6x²


However you decide to represent stuff in text is not given in the assignment. I presume your professor will expect you to use ^ to represent exponentiation.


Your number one goal, right now, should be the ability to read a polynomial from text and represent it as a structure (or class) in your program.

Hint: organize it in terms of operators.


I would not consider this an intro-to-CS project.

[ne555]

about the examples, if you are goint to say that y and x are independente, just make y a named constant and save a couple steps.


> I still don't have any idea where to start or how to get started
draw a skeleton.
you are giving four cases, at the very least you need some way to identify which case are you working on.


I suppose that you do have a parser and a equation class. ¿what operations does it support?

[dhayden]

The key here is to represent an expression in a tree structure. An expression is:
- an operand and some number of operators, which are themselves expressions, or
- a variable, or
- a constant

Once you have this, then symbolic differentiation involves recursively descending the expression and differentiating it along the way.

Note that when you differentiate an expression, you differentiate it with respect to a specific variable.

I'd start by writing code to parse a polynomial expression into an expression tree and to print out an expression tree. Make sure this works and then add code to do the rules one by one.

[jonnin]

I cant click the link but you may find it easier to translate polynomial fractions and use multiplication rules instead of trying to code up the division rule, but its up to you (or your prof).

[Duthomhas]

@jonnin
That will make his assignment more difficult. Remember the meme about premature optimization.

He first has to manage either a recursive descent parser or a multi-pass (tokens→polynomial) transformation.

Once he gets that, he needs to apply the differentiation rules as a multi-pass transformation.


If he is taking a 100–200 level course, his professor just screwed him with this assignment.

[Wafflecone67]

@Duthomhas

Sorry I haven't responded. No, I haven't taken calculus and yes this is comp sci 3. Honestly, this feels like Power Creep(if that's the correct phrasing).

[Duthomhas]

Hmm, well, what you are being asked to do is some pretty basic transformations.

  • First you must transform a line of text (given to you by the user) into a tree structure.
  • Then you must transform that tree structure to apply some calculus to it.
  • Finally you must transform the tree structure back to a textual string and print it for the user.


Example Time

Given an input stream containing the following tokens (this is your example problem):

    5 * x ^ 2 + 6 * x / y - 10 * x ^ 2 * y + 100

You must transform that into something that you can manipulate. We have all recommended a basic binary tree.

In the following, I am going to reorganize the equation by wrapping it in parentheses (). When a change is made, I will use square brackets [] to highlight what has changed. The basic structure is this:

    (operation left-operand right-operand)

For example, (+ 5 7) means add five and seven. This is the basis of our binary tree.

Let’s transform the equation:

Given

  5 * x ^ 2 + 6 * x / y - 10 * x ^ 2 * y + 100

First, handle exponents, left to right

  5 * x ^ 2 + 6 * x / y - 10 * x ^ 2 * y + 100
        ↑  

  5 * [^ x 2] + 6 * x / y - 10 * x ^ 2 * y + 100
                                   ↑

  5 * (^ x 2) + 6 * x / y - 10 * [^ x 2] * y + 100

Next, handle multiplication and division, left to right

  5 * (^ x 2) + 6 * x / y - 10 * (^ x 2) * y + 100
    ↑

  [* 5 (^ x 2)] + 6 * x / y - 10 * (^ x 2) * y + 100
                    ↑

  (* 5 (^ x 2)) + [* 6 x] / y - 10 * (^ x 2) * y + 100
                          ↑

  (* 5 (^ x 2)) + [/ (* 6 x) y] - 10 * (^ x 2) * y + 100
                                     ↑

  (* 5 (^ x 2)) + (/ (* 6 x) y) - [* 10 (^ x 2)] * y + 100
                                                 ↑

  (* 5 (^ x 2)) + (/ (* 6 x) y) - [* (* 10 (^ x 2)) y] + 100

Finally, handle addition and subtraction, left to right

  (* 5 (^ x 2)) + (/ (* 6 x) y) - (* (* 10 (^ x 2)) y) + 100
                ↑

  [+ (* 5 (^ x 2)) (/ (* 6 x) y)] - (* (* 10 (^ x 2)) y) + 100
                                  ↑

  [- (+ (* 5 (^ x 2)) (/ (* 6 x) y)) (* (* 10 (^ x 2)) y)] + 100
                                                           ↑

  [+ (- (+ (* 5 (^ x 2)) (/ (* 6 x) y)) (* (* 10 (^ x 2)) y)) 100]

We can see this is correct with a little pretty-printing:

(+ 
   (- 
      (+ 
         (* 
            5 
            (^ x 2)) 
         (/ 
            (* 6 x) 
            y)) 
      (* 
         (* 
            10 
            (^ x 2)) 
         y)) 
   100)

The outermost operation is an addition, which is applied after evaluating both operands — Visually, you can see that the 100 is added after everything else is computed.


Turning that into Code
In code, you must represent this binary tree in some way. Here is an easy one that knows how to take care of its own memory (no pointers necessary):

struct Node
{
  enum { Constant, Variable, Operator } type;
  std::string                           value;
  std::vector <Node>                    operands;
};

So, I can create a node that represents, say, a coefficient:

  Node coef;
  coef.type = Constant;
  coef.value = "7";

Or a node that represents a variable:

  Node var;
  var.type = Variable;
  var.value = "x";

Or a node that represents a binary operation, like multiplication:

  Node mul;
  mul.type = Operator;
  mul.value = "*";
  mul.operands.push_back( coef );
  mul.operands.push_back( var );

This last node is the same as (* 7 x), which is the same as "7 * x".


Review
So, the first thing you need to do is:

  • Tokenize a text stream into a binary tree
  • Print the binary tree

Unless you want to get deep into recursive-descent parsing, I recommend you use the binary tree as your basis for tokens, then modify the tree until it is properly transformed.

This means cheating a little with the pieces of your structure. Start with a flat list, using operands for the list of tokens.

struct Node
{
  enum { Tokens, Constant, Variable, Operator } type;
  std::string                                   value;
  std::vector <Node>                            operands;

  Node( int type, std::string value ): type(type), value(value) { }
};

bool get_token( const std::string& s, int& n, Node& token )
{
  ...
}

Node read_tokens( const std::string& s )
{
  int  n = 0;
  Node result;
  Node token;
  while (get_token( s, n, token ))
    result.operands.push_back( token );
  return result;
}

So, at this point you have a flat list of tokens, which you must build into a tree. It works just like the example above — keep making passes over the tree and combining elements of the token list into proper nodes, starting with exponents, until all you have left is a proper tree.

Well, I’m off to eat dinner.

Hope this helps get you started.

[Wafflecone67]

Wow @Duthomhas thanks.

[dutch]

"Symbiotic" should be "symbolic".

Could the shunting yard algorithm be used here?

The assignment is underspecified. What is the exact form of the input?

[Duthomhas]

The assignment is underspecified
Underspecified and overworked. Better be worth 60–70% of the course grade for the kind of effort required to build a symbolic algebraic expression simplifier and apply derivative transformations to it. The assignment makes it look very simple, but it can get nasty, very quickly.

For example, the assignment says, paraphrasing, “oh, by the way, add the ability to handle logarithms”. Unless that means only handling log x → 1 / x, it also implies being able to handle the chain rule, which requires a significantly more sophisticated analysis of the polynomial than the simple transform filters implied by the assignment.

Not even mentioned are all the standard algebraic transforms that need to be used. The example uses five applications of four unmentioned transforms on the second term alone:

    1x = x
    0x = 0
    x - 0 = x
    y/(y^2) = 1/y

Of course, we only have an image of one piece of the instructions that come with the course. There might be a whole lot more that we are not privy to.


Shunting Yard
Don’t waste your time with Shunting Yard. Getting a proper tree is easy enough without it. That is, it could be used... if you hate yourself.


What is the exact form of the input?
Again, we don’t know if OP has more instruction elsewhere. I have presumed the usual C/C++ convention. It is also possible (likely even) that implied multiplications may be used, which is an additional transformation step that must be applied at some point. Because it quickly becomes overload, I have used examples where multiplication must be explicit.

If OP has to deal with it, he will hopefully post about it.

I’ve been having fun with this at home. Rather than mix it into the string_to_tokens or tokens_to_polynomial steps, I just apply a transform that fixes the token stream between the two steps.


"Symbiotic" should be "symbolic"
I’ve been laughing at that. Autocorrect, maybe?
Maybe my wife and I should explore a little symbiotic differentiation later...

[dutch]

Is there a name for the algorithm you would use instead of the shunting-yard algorithm? Is it recursive decent parser (or something I see in wikipedia called an operator precedence parser, which may be about the same thing)?

[Duthomhas]

“Sequential reduction”?

The algorithm I suggest is demonstrated in my post example above.

I suggested this algorithm because:

  • it is simple
  • the assignment is complex

Recursive descent ≠ Shunting yard. They are both for a similar parsing issue, but the constraints on them are different, and they are used in slightly different contexts. But yes, either can be massaged for use in place of the other, with the only costs being increased complexity and decreased sanity.

In any case, though, I would prefer to see OP working with the kind of basic tree manipulation he will use throughout the assignment right at the start, instead of spending time and energy on a specialized strategy that is only applicable to one part of the assignment.

Remember, he doesn’t have to evaluate the polynomial, or even verify that it makes much sense. Just apply some simple transforms.

The whole concept of dealing with transforms over subtrees is already a huge conceptual leap that a lot of people never quite get in CS studies.

We haven’t even got to the part where we are marking subtrees as needing differentiation with respect to a single variable, let alone the possibility of having to repeat the process with each supplied variable.

(The given example is computed with respect to x. But it is a multi-variable polynomial. Does OP have to also compute d/dy? The wording of the assignment leads me to think it is a likely possibility.)

[Duthomhas]

I take it you are looking at playing with this at home too?

It’s fuuun! :O)

[dutch]

I knew shunting-yard wasn't recursive descent but was wondering if maybe "operator-precedence parser" is the same as "recursive descent parser". But reading the first paragraph on wikipedia shows the rdp to be "top-down" whereas the opp is "bottom-up". Interesting.

https://en.wikipedia.org/wiki/Recursive_descent_parser
https://en.wikipedia.org/wiki/Operator-precedence_parser

I want to work on it but a friend is dropping by so I won't be able to start for a few hours. :-(
I already started some shunting yard work but since I've done that before I think I'll try your "sequential reduction" (your name?) technique, which seems to deal with precedence by doing multiple passes over the string and handling the operators in order from highest to lowest precedence. That's a nice simple idea. But what about parentheses? Might they need some recursion?

[jonnin]

@jonnin
That will make his assignment more difficult. Remember the meme about premature optimization.

I was not trying to make it faster. I was trying to simplify the problem (code effort) but it may, as you said, have actually made it worse. It makes it easier on paper... but I see what you mean. Overlooked the 'human can do it' vs 'make the computer do it' factor.

[Duthomhas]

Heh, yeah.

The multiple passes technique is a powerful one. It is, in fact, the same technique applied when compiling C++ code, called “optimization passes”.

A reduction is a transformation over data that makes it “simpler”. (By “simpler” we mean it is easier to reason about in the next pass.)

An example of a simple algebraic reduction:

    3x + x     ↔     x(3 + 1)     ↔     4x

Obviously, the direction you are going has impact on what you plan to try next.


@dutch re: parentheses

Parentheses are a special case. (Because they are not a binary operator.) And yes, you are right: recursion is part of it.

Binary operators are easy: find an operator, then combine the elements to the immediate left and immediate right into the operator tree.

(7)→(*)→(3)→(+)→(4)
     ↑
     higher precendence operator

        lower precedence operator
        ↓
   (*)→(+)→(4)
   / \
 (7) (3)

       (+)
       / \
     (*) (4)
     / \
   (7) (3)

Or, using the S-expression syntax I have been employing:

(7) (*) (3) (+) (4)
     ↑
     higher precedence operator

(* (7) (3)) (+) (4)
             ↑
             lower precedence operator

(+ (* (7) (3)) (4))

Parentheses do something similar, but to an entire range of things — AND this is where you apply some recursion.

(4)→(*)→[(]→(3)→(+)→(2)→[)]
         ↑             ↑
         Matching parentheses

Recurse on the stuff between parentheses:

            (3)→(+)→(2)

                (+)
                / \
              (3) (2)

Now replace all the parenthesized stuff (including the parentheses) with the new tree:

(4)→(*)→(+)
        / \
      (3) (2)

After all parentheses have been reduced, we can move down to exponents and then to multiplication:

    (*)
    / \
  (4) (+)
      / \
    (3) (2)

 
I’ll skip the s-expression syntax this time...

The concept is very similar. You just need an extra function to do parentheses since you have to find a variable-length subsequence to work on.

Hint: find the first ), then search backward for the closest (. This will find you the leftmost innermost parenthetical pair.

After processing all those, give a single search for a stray unmatch (.


Heh...

[Duthomhas]

I just clicked this to see if anyone else has posted something, and —since no on has— glanced at my last post, and realized I may have left something important out of the reductions.

Notice that the reduction ONLY works on objects that have not already been reduced.

Hence, I can take a line like 3 ^ x ^ 2

and perform two reductions:

(^ 3 x) ^ 2
(^ (^ 3 x) 2)

We didn’t try to reduce the (^ 3 x) again.

[dutch]

I've got a sequential reduction program working. One thing I noticed is that for right-to-left associativity you need to go through the tokens backwards (like for ^). And it seems that the parens don't need recursion.
I don't know if I should post the code, though.

[Duthomhas]

Um, what operators are you using that are not left-associative?

I also don’t know how you are getting around the need for recursion on parentheses.

[edit]
Maybe we should make this a challenge in the Lounge. `:^J