commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Brent Worden" <brent.wor...@perficient.com>
Subject Re: [math][functor] More Design Concerns
Date Tue, 01 Jul 2003 17:05:46 GMT
I've been playing around with the Functor library a little and I reworked
the bisection routine to be functorfied.  With the addition of functors, the
algorithm has become totally agnostic to its input allowing it to be used in
an endless number of settings.  The code goes as follows:

//=================== BEGIN BisectionSolver.java ===================
package org.apache.commons.math.analysis;

import org.apache.commons.functor.BinaryFunction;
import org.apache.commons.functor.BinaryPredicate;
import org.apache.commons.functor.UnaryFunction;

/**
 * This solver applies the bisection root finding method to the given
 * functor input.
 * @author Brent Worden
 */
public class BisectionSolver {
    /** function used to evaluate potential roots. */
    private UnaryFunction function;

    /** function used to compute the midpoint of two potential roots. */
    private BinaryFunction midpoint;

    /** predicate used to determine if two potential roots are equal.
stopping condition. */
    private BinaryPredicate areEqual;

    /** predicate used to determine if two potential roots bracket the
actual root. */
    private BinaryPredicate equalSign;

    /**
     *
     */
    public BisectionSolver(UnaryFunction function, BinaryFunction midpoint,
BinaryPredicate areEqual, BinaryPredicate equalSign) {
        super();

        this.function = function;
        this.midpoint = midpoint;
        this.areEqual = areEqual;
        this.equalSign = equalSign;
    }

    /**
     *
     */
    public Object solve(Object a, Object b) {
        Object m;
        Object fm;
        Object fa;

        fa = function.evaluate(a);

        while (!areEqual.test(a, b)) {
            m = midpoint.evaluate(a, b);
            fm = function.evaluate(m);

            if (equalSign.test(fm, fa)) {
                // b and m bracket the root.
                a = m;
                fa = fm;
            } else {
                // a and m bracket the root.
                b = m;
            }
        }

        return midpoint.evaluate(a, b);
    }
}
//=================== END BisectionSolver.java ===================

//=================== BEGIN UnivariateRealSolverFactory .java
===================
package org.apache.commons.math.analysis;

import java.lang.reflect.InvocationTargetException;

import org.apache.commons.functor.BinaryFunction;
import org.apache.commons.functor.BinaryPredicate;
import org.apache.commons.functor.UnaryFunction;
import org.apache.commons.math.MathConfigurationException;
import org.apache.commons.math.MathException;

/**
 *
 */
public class UnivariateRealSolverFactory {
    protected UnivariateRealSolverFactory() {
    }

    /**
     * create a bisection solver for the given function.  If we envision
allowing different inputs,
     * such as Tim's bean driven approach, construction of the solver could
be contained in another
     * factory method.
     */
    public static BisectionSolver newBisectionSolver(final
UnivariateRealFunction f){
        UnaryFunction function = new UnaryFunction() {
            public Object evaluate(Object x) {
                try {
                    return new Double(f.value(((Number)x).doubleValue()));
                } catch(MathException ex) {
                    return new Double(Double.NaN);
                }
            }
        };

        BinaryFunction midpoint = new BinaryFunction() {
            public Object evaluate(Object a, Object b) {
                double x = ((Number)a).doubleValue();
                double y = ((Number)b).doubleValue();
                return new Double(x + ((y - x) * .5));
            }
        };

        BinaryPredicate areEqual = new BinaryPredicate() {
            public boolean test(Object a, Object b) {
                double x = ((Number)a).doubleValue();
                double y = ((Number)b).doubleValue();
                return Math.abs(x - y) <= 10e-9;
            }
        };

        BinaryPredicate equalSign = new BinaryPredicate() {
            public boolean test(Object a, Object b) {
                double x = ((Number)a).doubleValue();
                double y = ((Number)b).doubleValue();
                return x * y >= 0.0;
            }
        };

        return new BisectionSolver(function, midpoint, areEqual, equalSign);
    }

    /**
     * Convenience method to apply the bisection method to a function.
     * This is synonymous with the textbook application of the bisection
method.
     * Again, if we envision allowing different inputs, more convenience
methods could be added.
     */
    public static double solveUsingBisection(UnivariateRealFunction f,
double x0, double x1) {
        BisectionSolver solver = newBisectionSolver(f);
        return ((Number)solver.solve(new Double(x0), new
Double(x1))).doubleValue();
    }
}
//=================== END UnivariateRealSolverFactory .java
===================

//=================== BEGIN RealSolverTest.java ===================
package org.apache.commons.math.analysis;

import org.apache.commons.functor.BinaryFunction;
import org.apache.commons.functor.BinaryPredicate;
import org.apache.commons.functor.UnaryFunction;
import org.apache.commons.math.MathException;

import junit.framework.Assert;
import junit.framework.Test;
import junit.framework.TestCase;
import junit.framework.TestSuite;

/**
 *
 */
public final class RealSolverTest extends TestCase {

    public RealSolverTest(String name) {
        super(name);
    }

    private void assertEquals(double[] expected, double[] actual, double
tolerance) {
        for(int i = 0; i < actual.length; ++i) {
            assertEquals(expected[i], actual[i], tolerance);
        }
    }

    public void testBisectionSolverTraditional(){
        // traditional root finding
        double pi = UnivariateRealSolverFactory.solveUsingBisection(new
SinFunction(), 1, 4);
        assertEquals("Did not get pi.", pi, Math.PI, 10e-9);
    }

    public void testBisectionSolverThinkingOutOfTheBox(){
        // example of solver's newfound flexibility
        // find the unit vector for a given vector

        // computes the length of a vector
        final UnaryFunction length = new UnaryFunction() {
            public Object evaluate(Object input) {
                double[] x = (double[])input;
                double len = x[0] * x[0];
                for(int i = 1; i < x.length; ++i) {
                    len += x[i] * x[i];
                }
                return new Double(len);
            }
        };

        // computes the midpoint of two vectors
        BinaryFunction midpoint = new BinaryFunction() {
            public Object evaluate(Object a, Object b) {
                double[] x = (double[])a;
                double[] y = (double[])b;
                double[] z = new double[x.length];
                for(int i = 0; i < x.length; ++i) {
                    z[i] = x[i] + ((y[i] - x[i]) * .5);
                }
                return z;
            }
        };

        // determine if two vectors are within tolerance
        BinaryPredicate equalVectors = new BinaryPredicate() {
            public boolean test(Object a, Object b){
                Double x = (Double)(length.evaluate(a));
                Double y = (Double)(length.evaluate(b));
                return Math.abs(x.doubleValue() - y.doubleValue()) <= 10e-9;
            }
        };

        // determine if two vectors lengths are both less than 1.0 or are
both greater than 1.0
        BinaryPredicate equalSign = new BinaryPredicate() {
            public boolean test(Object a, Object b) {
                Double x = (Double)a;
                Double y = (Double)b;
                return (x.doubleValue() - 1.0) * (y.doubleValue() - 1.0) >=
0.0;
            }
        };

        BisectionSolver solver = new BisectionSolver(length, midpoint,
equalVectors, equalSign);
        double[] origin = {0.0, 0.0, 0.0, 0.0};
        double[] vector = {10.0, 20.0, 30.0, 40.0};
        double len = Math.sqrt(3000.0);
        double[] expected = {10.0 / len, 20.0 / len, 30.0 / len, 40.0 /
len};
        double[] normal = (double[])(solver.solve(origin, vector));

        assertEquals(((Double)length.evaluate(normal)).doubleValue(), 1.0,
10e-9);
        assertEquals(expected, normal, 10e-9);
    }
}
//=================== END RealSolverTest.java ===================

This example also helps illustrate what I would like the design of the
library to proceed:
1) There are a collection of utility objects to perform standard operations
on standard input.  StatUtils is a good example of this.
2) Factories to create operation objects that perform the same operations on
both standard input and non-standard input.
3) Operational objects which allow open-ended input thus becoming reusable
in all kinds of environments.  This also prevents the need to implemented
more than once for the various inputs.


Brent Worden
Senior Technical Consultant
Perficient, Inc. - Minneapolis
D: (612) 752-1625


---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message