Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A C++ Program for Differentiating a Function: Is this a Good Start?

  1. May 10, 2014 #1
    Here's what I have so far:

    Code (Text):


    std::string CalculusWizard::derivative(std::string& fx, const char & x, unsigned & n = 1)
    {

        if (n == 0)
        {
            return fx;
        }
        else if (n > 1)
        {
            while (n-- > 1)
                fx = derivative(fx, x);
        }

        // If here, find and return the derivative of fx ...
    }

     
    Is that a good start???

    Now onto the tricky stuff .....
     
  2. jcsd
  3. May 10, 2014 #2

    jedishrfu

    Staff: Mentor

    I'd say no as it doesn't do anything useful yet. Its like designing the doors of house that hasn't been built yet. However, I'm sure you knew that and are providing some humor to the arduous task of commenting on PF threads.

    First question is are you planning to numerically differentiate the function or symbolically differentiate it?

    Numerical differentiation is the simpler task

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

    and the much harder task is to symbolically differentiate:

    http://en.wikipedia.org/wiki/Symbolic_differentiation
     
  4. May 10, 2014 #3

    I wasn't trying to provide any humor .....

    And I'm trying to symbolically differentiate it. I don't need no Wikis.

    Here's what I have so far:

    Code (Text):

    /*
    Returns the n-th derivative of f with respect to x
    */
    std::string CalculusWizard::derivative(std::string& fx, const char & x, unsigned & n = 1)
    {

        if (n == 0)
        {
            return fx;
        }
        else if (n > 1)
        {
            while (n-- > 1)
                fx = derivative(fx, x);
        }

         
        /*
            Partition fx as
                 fx = gx op gx
            where op is either +, -, *, / or composition then
            return f'x according to rules of calculus:
            op = +   ----> f'x = g'x + h'x
            op = -   ----> f'x = g'x - h'x
            op = *   ----> f'x = gx * h'x + hx * g'x
            op = /   ----> f'x = (g'x * hx - gx * h'x)/[(hx)^2]
            op = composition, i.e. fx = g(hx) ----> f'x = g'(hx) * h'x
            If there is no op
        */
        std::string gx(""), hx("");
        functop op = NONE;

        if (fx.size() == 0)
        {
            throw ("ERROR: Attempted to find derivative of empty function.");
            // Need to create different type of error
        }

        // .... Partition fx here  .....

        if (hx.size() == 0)
        {
            return derivative(gx);
        }

        switch (op)
        {
            case PLUS:
                // ...
                break;
            case MINUS:
                // ...
                break;
            case TIMES:
                // ...
                break;
            case DIVIDE:
                // ...
                break;
            case COMPOSITION:
                // ...
                break;
            case NONE:
                // ...
                break;
            default: // never happens
                break;
        }


    }
     
    Obviously that's incomplete .... Lots of holes that need to be patched up already.
     
  5. May 10, 2014 #4

    jedishrfu

    Staff: Mentor

    Sorry, if I offended you but your original post was very sparse if you had posted the second listing I would've responded differently.

    So the first thing you need to do is parse the expression into an abstract syntax tree that you can manipulate in your program. You need to consider that someone might type in an invalid expression and you need to know that upfront.

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

    Wikipedia is good in that it gives you a summary and some further references to follow but you must decide if its useful or not.

    Also there may be some yacc files that generate code for parsing an expression into an ABS that you could use:

    http://en.wikipedia.org/wiki/Yacc
     
  6. May 10, 2014 #5
    MathParseKit is the answer

    Why do always reinvent the wheel?

    There are already libraries that does that.
    In particular MathParseKit gives you both the interpreter and the derivate function.

    Mod note: deleted link to this member's site.

    What do you think about?
     
    Last edited by a moderator: May 11, 2014
  7. May 10, 2014 #6

    Mark44

    Staff: Mentor

    Sometimes it's good practice to reinvent the wheel, especially if you're learning how to do something (like creating a wheel).
     
    Last edited: May 11, 2014
  8. May 10, 2014 #7
    What about whatching wheel makers while working? The "do all from scratch" era is gone. This is a part of the OpenSource movement. Do not build it again and again, find the nearest thing, evaluate it and add what is missing in order to reach your goal.

    I know that reading someone else code is not easy, but sometimes gives you more than you expect.
     
  9. May 10, 2014 #8

    jedishrfu

    Staff: Mentor

    There is an old Confucian proverb that says:

     
  10. May 10, 2014 #9

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    There is also a proverb that says, "when a new member joins PF and his/her first post is to recommend a website with the same name, that probably isn't an impartial recommendation from a satisfied customer :smile:
     
  11. May 11, 2014 #10

    Mark44

    Staff: Mentor

    Addressed.
     
  12. May 11, 2014 #11
    Mmmmmm how can i post 100s of lines of code in a single post?
    So, if i cannot post it I'll just post a "suggestion" of solution.
    Are you OK with that?

    Do not go procedural, OOP is your friend.
    Build a Function class like this, it is a virtual class (abstract) so you cannot instantiate it, but it will be used as common interface for all the Others.
    Code (Text):
    /*!MFunction
         * Virtual class base for all functions
         */
        class MFunction{
            protected:
                /*! Function Type
                 *
                 * \sa  MF_NONE MF_CONST MF_VAR MF_OPP MF_ADD MF_SUB MF_MUL MF_DIV MF_LOG MF_LN MF_LOG10 MF_POW MF_EXP MF_SIN MF_COS MF_TAN MF_COTAN MF_ASIN MF_ACOS MF_ATAN MF_ACOTAN MF_ABS MF_SIGN MF_SINH MF_COSH MF_TANH MF_COTANH MF_SQRT MF_USER
                 */
                int m_type;

            public:
            /*! Clone this function and all the child recursively
             *
             * It needs to be reimplemented in child classes
             *
             *
             * \return Returns a clone of this function (recursive).
             */
            virtual MFunction* Clone() const=0;
           
            /*! Are there any problems?
             *
             * It needs to be reimplemented in child classes
             *
             * \return Returns true if there are no errors (recursive).
             */
            virtual bool IsOk() const=0;
           
            /*! This function is constant relativelly to this list of variables
             *
             * It needs to be reimplemented in child classes
             *
             * \param variables Variables respect with control the constantness (recursive).
             * \return Returns true if it is constant.
             */
            virtual bool IsConstant(MVariablesList* variables) const=0;
           
            /*! Solve this function with respect to this variables
             *
             * If not all the variables defined in the function tree are presente in the list the function may return another tree
             * It needs to be reimplemented in child classes
             *
             * \param variables Variables that are used during resolution (recursive).
             * \return Returns the solution respect to the variables values.
             */
            virtual MFunction* Solve(MVariablesList* variables) const=0;
           
            /*! Derivate this function with respect to this variables (generally 1)
             *
             * It needs to be reimplemented in child classes
             *
             * \param variables Variables respect with derivate (recursive).
             * \return Returns the derivate of this function.
             */
            virtual MFunction* Derivate(MVariablesList *variables) const=0;
           
            /*! Get all the variables defined in the function tree recursivelly
             *
             * It needs to be reimplemented in child classes
             *
             * \param list Optional pointer to an existing variable list (if NULL a new one is created).
             * \return Returns the variable list (if list is NULL you need to delete it at the end, if not it is equal to list).
             */
            virtual MVariablesList* GetVariablesList(MVariablesList *list=NULL) const=0;
           
            /*! Return the function as a string
             *
             * \Return function as a string
             */
            virtual std::wstring ToString() const=0;

            /*! Return the dominium of the function as a system
             *
             * It needs to be reimplemented in child classes
             *
             * \param update Optional pointer to an existing system (if NULL a new one is created).
             * \return Returns the domain of this function (if update is NULL you need to delete it at the end, if not it is equal to update).
             */
            virtual MSistem* GetDomain(MSistem *update) const=0;
           
            /*! Get the type of the function
             *
             * \return Return the type of the function
             */
            int GetType() const{
                return m_type;
            };
           
            /*! Release this function and all the children
             *
             * It needs to be reimplemented in child classes
             */
            virtual void Release()=0;
        };
    Then pick up a good algebra book and start defining rools:
    Like for sum
    Code (Text):
    MFunction* MFAdd::Derivate(MVariablesList *variables) const{
        if (!m_lhs || !m_rhs) return NULL;
        if (m_lhs->IsConstant(variables)){
            if (m_rhs->IsConstant(variables)){
                return new MFConst(0.0);
            }else{
                return m_rhs->Derivate(variables);
            }
        }else{
            if (m_rhs->IsConstant(variables)){
                return m_lhs->Derivate(variables);
            }else{
                MFunction *lhs=m_lhs->Derivate(variables);
                if (!lhs) return NULL;
                MFunction *rhs=m_rhs->Derivate(variables);
                if (!rhs) return NULL;
                MFAdd *ret=new MFAdd();
                ret->SetLhs(lhs);
                ret->SetRhs(rhs);
                return ret;
            }
        }
    }
    or sin
    Code (Text):

    MFunction* MFSin::Derivate(MVariablesList *variables) const{
        if (!m_argument) return NULL;
        if (m_argument->IsConstant(variables)) return new MFConst(0.0);
        MFunction *fn=m_argument->Derivate(variables);
        if (!fn) return NULL;
        MFMul *ret= new MFMul();
        ret->SetRhs(fn);
        MFCos *arg= new MFCos(m_argument);
        ret->SetLhs(arg);
        return ret;
    }
    You can do the same thing even for the solve.
    A lot of persons when they see this kind of code say: is it fast? it seams too complex to be fast.
    It is fast, it is like "compiling" when you get to that tree of functions you do not have to bother about syntactics check so you gain a lot of speed.
    I've used it for a 3D function visualizer (I would post the link but i can't ;-)) that for every point computes the solution of the function and both the derivatives and is very fast.

    for the parser thing go recursive.
    One function that manages sequences (+,-,*,/,^) and one function for "functions" (sin, cos, tan,...). They call each other.
    Doing this it will become more readable and less error prone.

    Big suggestion, comments, comments, comments.
    This are complex structures, they are clear now, but in few months you will not remember every single decision.

    I hope this post will be OK.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: A C++ Program for Differentiating a Function: Is this a Good Start?
Loading...