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

[Jamin2112]

Here's what I have so far:

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 ...

 

[jedishrfu]

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

 

[Jamin2112]

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

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:

/*
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.

 

[jedishrfu]

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:

/*
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.

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

 

[B3rn475]

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?

 

[Mark44]

Why do always reinvent the wheel?

Sometimes it's good practice to reinvent the wheel, especially if you're learning how to do something (like creating a wheel).

There are already libraries that does that.
What do you think about?

 

[B3rn475]

Sometimes it's good practice to reinvent the wheel, especially if you're learning how to do something (like creating a wheel).

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.

 

[jedishrfu]

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.

There is an old Confucian proverb that says:

I hear and I forget. I see and I remember. I do and I understand.

Confucius

 

[AlephZero]

There is an old Confucian proverb that says:

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

 

[Mark44]

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

Addressed.

 

[B3rn475]

Addressed.

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.

/*!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

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

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.