Differentiate any function
I am trying to construct some simple code to find the derivative
for any function. So far I have come up with what can be read below.
However, I ran into some problems when the expression is growing
like nothing else. Does anyone have suggestions of simple ways to
simplify the function after or during the diff().
Removing terms when multiplied by zero is one, but if done by hand
there are a lot more that can be done.
import java.math.*;
publicclass MathUtility{
publicstaticvoid main(String[] args){
// f(x) = -x^2
Function x2 =new Product(new Constant(-1),new Polynomial(2.0));
// f(x) = e^(-x^2)
Function norm =new Composite(new Exp(), x2);
// deriving it lots of times
System.out.println("f(x) = "+norm.toString("x"));
for (int i=0;i<Integer.parseInt(args[0]);i++){
norm = norm.diff();
System.out.println("d^"+(i+1)+"/dx f(x) = "+norm.toString("x"));
}
}
// any continous function
publicstaticinterface Function{
publicdouble compute(double x);
public Function diff();
public String toString(String x);
}
// abstract function using two parts
publicstaticabstractclass FandGimplements Function{
private Function _f;
private Function _g;
public FandG(Function f, Function g){
_f = f;
_g = g;
}
public Function f(){
return _f;
}
public Function g(){
return _g;
}
}
// ( f(x) + g(x) )' = f'(x) + g'(x)
publicstaticclass Sumextends FandG{
public Sum(Function f, Function g){
super(f, g);
}
publicdouble compute(double x){
return f().compute(x)+g().compute(x);
}
public Function diff(){
returnnew Sum(f().diff(), g().diff());
}
public String toString(String x){
return f().toString(x)+"+"+g().toString(x);
}
}
// ( f(x) * g(x) )' = f'(x)*g(x) + f(x)*g'(x)
publicstaticclass Productextends FandG{
public Product(Function f, Function g){
super(f, g);
}
publicdouble compute(double x){
return f().compute(x)*g().compute(x);
}
public Function diff(){
returnnew Sum(new Product(f().diff(), g()),
new Product(f(), g().diff()));
}
public String toString(String x){
return f().toString(x)+"*"+g().toString(x);
}
}
// ( f(g(x)) )' = f'(g(x)) * g'(x)
publicstaticclass Compositeextends FandG{
public Composite(Function f, Function g){
super(f, g);
}
publicdouble compute(double x){
return f().compute(g().compute(x));
}
public Function diff(){
returnnew Product(new Composite(f().diff(), g()), g().diff());
}
public String toString(String x){
return f().toString(g().toString(x));
}
}
// constant
publicstaticclass Constantimplements Function{
privatedouble _constant = 0;
public Constant(double constant){
_constant = constant;
}
publicdouble compute(double x){
return _constant;
}
public Function diff(){
returnnew Constant(0.0);
}
public String toString(String x){
returnnew Double(_constant).toString();
}
}
// polynomial x^k
publicstaticclass Polynomialimplements Function{
privatedouble _exp = 0;
public Polynomial(double exp){
_exp = exp;
}
publicdouble compute(double x){
return Math.pow(x, _exp);
}
public Function diff(){
returnnew Product(new Constant(_exp),new Polynomial(_exp-1.0));
}
public String toString(String x){
return"("+x+")^"+_exp;
}
}
// e^(x)
publicstaticclass Expimplements Function{
publicdouble compute(double x){
return Math.pow(Math.E, x);
}
public Function diff(){
returnthis;
}
public String toString(String x){
return"e^("+x+")";
}
}
}
>
[11039 byte] By [
parza] at [2007-10-2 8:11:27]
Correction. The method toString for the Sum must be
public String toString(String x) {
return "("+f().toString(x)+"+"+g().toString(x)+")";
}
parza at 2007-7-16 22:07:37 >
In symbolic algebra, it's generally a good idea to use canonical forms. If you didn't have Exp I would say that you should just ditch Sum, Product and Composite. I've never tried to design a canonical form for expressions which include exponentiation, but I think I would probably treat them as mixed multibasic polynomials (i.e. polynomials in x, e^x, e^(e^x), etc.).
I do not think canonical form is possible for what I am trying
to do.
It is well known that a neural network can adapt to any continues
function given enough neurons and synapses and all functions in
a NN are continues. So why not differentiate it. Here is an example.
Let f(x) be a NN and g(x),h(x),j(x) be given functions. We want to
solve following equation
g(x)*f''(x) + h(x)*f'(x) + f(x) = j(x)
It would be useful to be able to just construct f(x), g(x), h(x),
j(x), differentiate f(x) twice, and finally construct the equation
above. Then genetic programing could be used to adjust the synapses
in f(x) such that the equation above is valid for a set of points.
This would in some since solve the equation symbolically, or at least
find one solution.
Bottom line is that f(x) will be far to complicated to find a
canonical form, so I need algorithms for simplifying f''(x), or?
parza at 2007-7-16 22:07:37 >
Or, if it would be possible to differentiate these complex functions it would be possible to compute the Hessian matrix for the equation in respect to the synapses and then use it in a gradient method to find the optimum.
parza at 2007-7-16 22:07:37 >
I haven't worked through a complete design, but here's a sketch.
Expression ::= d [d in Double]
| x
| e ^ (Expression)
| (Expression) ^ d [d in Double]
| (Expression) (Expression)
| (Expression) + (Expression)
Basic components:
Constant: 1
Variable: x
Exponentials: e ^ (SimpleExpression[1])
Composition:
Polynomial in basic component E : SUM over i of E2 * E^k_i
where k_i is a double, E2 is an expression not containing E; if E is 1 then there is only one element.
[1] A SimpleExpression is a constant, a variable, an exponential, or a polynomial with one element.
That's the basis of a canonical representation. You need to define (recursively) a total ordering on expressions. Then you want to arrange polynomials such that E2 is before E in the ordering.
Use methods rather than constructors to do addition and multiplication of expressions. If you define your representation to only work with polynomials (since basic component E can be treated as polynomial 1 * E^1), you only have to handle addition, multiplication and differentiation of polynomials.
Addition (A + B) is easy: if A < B then switch them, so wlog B <= A. Then do component-wise addition treating both as polynomials in the E of A.
Multiplication is easy: split each polynomial A and B into monomials, do all pairwise multiplications, and add the results. Multiplication of monomials M and N: if they have the same expression E then double k_i and multiply their E2s: otherwise take the one with the smaller E and multiply it into the E2 of the other.
Differentiation is roughly as you currently have it.
> Composition:
> Polynomial in basic component E : SUM over i of E2 * E^k_i
> where k_i is a double, E2 is an expression not containing E;
> if E is 1 then there is only one element.
Please elaborate, I do not understand.
> Use methods rather than constructors to do addition and multiplication
> of expressions.
Constructors are only used when creating new functions, not when computing
a value. Computations are done through the method compute(double x) which
will not create any new instances.
parza at 2007-7-16 22:07:37 >
> Please elaborate, I do not understand.
I'm violating naming standards for consistency with the description. Something along the lines of public class Polynomial implements Function
{
/**
* The expression over which this is taken.
*/
private final Function E;
/**
* Preferably sorted by exponent for canonicity
*/
private List<Monomial> monomials;
// Constructor etc. left as exercise to the reader.
public double compute(double d)
{
double x = E.compute(d);
int sum = 0;
for (Monomial monomial : monomials)
{
sum += monomial.E2.compute(d) * Math.pow(x, monomial.k_i);
}
return sum;
}
private static class Monomial
{
public final Function E2;
public final double k_i;
// Constructor again left to the reader.
}
}
(NB you might want to consider making your Polynomial / my Monomial use integer rather than double for the exponent, because otherwise compute(-1) could throw an exception).
> Constructors are only used when creating new functions, not when computing a value.
I understand that. My point is that if you want compact representations (let alone canonical ones) you're far better off having new Constant(1.0).add(new Constant(2.0))
return a single Constant(3.0) rather than a Sum of a Constant(1.0) and a Constant(2.0). Your system of using a constructor every time you want to combine two expressions is in large part responsible for the size of the expressions you get.
Ok, then I see what you mean. They are good points. Thanks.
Using dynamic programming would probably also make it a lot faster.
// f(g(x))
public static class Composite extends FandG {
private double _value = Double.MAX_VALUE;
public Composite(Function f, Function g) {
super(f, g);
}
public void reset() {
_value = Double.MAX_VALUE;
}
public double compute(double x) {
if (_value==Double.MAX_VALUE) {
_value = f().compute(g().compute(x));
}
return _value;
}
public Function diff() {
Function newF = new Product(new Composite(f().diff(), g()),
g().diff());
// looks for an exact the same function and returns it,
// else this one is added to the map and returned.
return MathUtility.getSingleton(newF);
}
public String toString(String x) {
return f().toString(g().toString(x));
}
}
I think it will become a lot faster because the result from
differentiating products and compositions produce subparts which
are the same and can be reused.
parza at 2007-7-16 22:07:37 >
Correction.
public Function diff() {
// MathUtility.getSingleton(...) look for an exact the same
// function and return it, else this one is added to the map
// and returned.
Function df = MathUtility.getSingleton(f().diff());
Function dg = MathUtility.getSingleton(g().diff());
Function dfg = MathUtility.getSingleton(new Composite(df, g()));
return MathUtility.getSingleton(new Product(dfg, dg));
}
public boolean equals(Object obj) {
if (!(obj instanceof Composite)) {
return false;
}
FandG o = (FandG)obj;
return (o.f().equals(f()) && o.g().equals(g())) ||
(o.f().equals(g()) && o.g().equals(f()));
}
public int hashCode() {
...
}
parza at 2007-7-16 22:07:37 >
> Using dynamic programming would probably also make it a lot faster.Possibly, but you really want to make it map from input values to output values rather than assume that compute will always be passed the same input value.
> ...rather than assume that compute will always be passed the same
> input value.
True. So if value listeners are used and variables are introduced
(see below), we get following benefits.
1. Enables dynamic programming without relying on any assumptions.
2. The functions can contain any number of variables. This is needed
in order to optimize using gradient methods, and much more.
3. We can change a variable and only those functions dependent on
this variable will be recomputed.
Any drawbacks?
public interface Function {
public double compute();
public Function diff(Variable var);
}
public interface ValueListener {
public void valueChanged(Function f);
}
public abstract AbstractFunction implements Function, ValueListener {
private double _value = Double.MAX_VALUE;
private List _valueListeners = new Vector();
public void addValueListener(ValueListener listener) {
_valueListeners.add(listener);
}
public void valueChanged(Function f) {
if (_value!=Double.MAX_VALUE) {
_value = Double.MAX_VALUE;
notifyListeners();
}
}
protected void notifyListeners() {
for (Iterator i = _valueListeners.iterator();i.hasNext();) {
((ValueListener)i.next()).valueChanged(this);
}
}
public double compute() {
if (_value==Double.MAX_VALUE) {
_value = computeNow();
}
return _value;
}
public abstract double computeNow();
}
public class Variable extends AbstractFunction {
private String _name;
private double _varValue;
public Variable(String name, double varValue) {
_name = name;
_varValue = varValue;
}
public void setVariableValue(double value) {
if (_varValue!=value) {
_varValue = value;
notifyListeners();
}
}
public double computeNow() {
return _varValue;
}
public Function diff(Variable var) {
if (this.equals(var)) {
return Constant.ONE;
} else {
return Constant.ZERO;
}
}
public boolean equals(Object obj) {
return obj instanceof Variable &&
_name.equals(((Variable)obj)._name);
}
}
parza at 2007-7-16 22:07:37 >
Interesting topic ... allow me to briefly explain how I attempt to simplify
expressions in my little pet CAS project: every expression is represented
by its expression tree (similar to your representation). I implemented an
expression matcher, which crawls over an expression tree attempting to
find a 'match' which is defined by another expression tree where the
atoms/leaves have a special meaning, e.g. for the expression tree:
(a+b)-sin(x)-(a+b)
and the meta-expression:
x+y-x
the atoms x and y match the sub-expressions:
x:: (a+b)
y:: sin(x)
... and a simple symbol table stores the association for later use.
Next to the matcher I implemented a 'manipulator' that, given a symbol
table and onother meta-expression tree, substitutes the associated
symbols in the latter, e.g. given the example above and the meta-expression:
y
... the resulting expression after manipulation becomes:
sin(x)
Last but not least a third tools is implemented: an expression 'unraveler',
i.e. given an expression and an operatorpair , an expression is unraveled
into two list of sub-expressions. Here's a small example:
a+b-a+d+e*f/f
... and the operator pair + and -, the expression is unraveled into:
+:: a b d e f/f
-:: a
Given a pair of meta-expressions (one for each list of sub-expressions)
and a substitution pattern (see above), the two lists can be simplified,
e.g. the meta-expressions:
x,x and nil,nil
... simplifies the lists above to:
+:: b d e f/f
-::
... finally a simple 'expression assembler' is able to build a new expression:
b+d+e+f//f
...out of the two lists again. Given an operator pair *,/ and the following
meta-expressions:
x,x 1,nil
... are able to remove the 'f/f' sub-expression and simplify it to 1 (one).
Repeatedly applying the matcher and/or the unraveler and manipulator
until no more changes can be made (and a set of expression rules),
all take care of the expression simplification process.
As a side effect this simplification process handles differentiation
w.r.t. any variable by itself, i.e. there's no Java code needed for the
differentiation of the expression/function. The following rules in my
rule base take care of it:
delta=((x) delta x)(1)
deltaadd=((y+z) delta x)(y delta x + z delta x)
deltamin=((y-z) delta x)(y delta x - z delta x)
deltamul=((y*z) delta x)((y delta x) * z + (z delta x)*y)
deltadiv=((y/z) delta x)((z*y delta x-y*z delta x)/(z*z))
deltaconst=(c delta x)(0)
deltasine=(sin(y) delta x)(cos(y)*(y delta x))
deltacosine=(cos(y) delta x)(-sin(y)*(y delta x))
deltatangent=(tan(y) delta x)(1/(cos(y)*cos(y))*y delta x)
deltalog=(log(y) delta x)((1/y) * y delta x)
deltaexp=(exp(y) delta x)(exp(y) * y delta x)
kind regards,
Jos
JosAHa at 2007-7-16 22:07:37 >
Sorry for not responding until now. Lack of time (as always).
Sound like a good idea and I will look into using it. The only
drawback I can think about is that when the functions becomes
too complicated, there will be no rules matching it. However,
I think that this idea will take care of a lot of simplifications and
will therefore take me a step closer to the goal.
When I have time to test it, I will write about the result to this thread.
Thanks.
parza at 2007-7-16 22:07:37 >
>> I am trying to construct some simple code to find the derivative
for any function.
I solved similar kind of problem that involves the integration of any function. But if you consider 'Integration by Parts' then you will find that , it is derived from the product formula for derivatives.
However, I used Numerical Integration based on Riemann Sums algorithm. My program was 2 pages long, where similar Fortran code was 11 pages long. I would recommend you to use Numerical technique to find the derivatives of a function. If it is possible, try 'Maple'first, then convert the 'Maple' concept into Java or try google to find the Numerical Technique for Derivative .
If you end up with any solution, please post it on the forum.
Thank You!
