1/*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements.  See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License.  You may obtain a copy of the License at
8 *
9 *      http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17package org.apache.commons.math.analysis.solvers;
18
19import org.apache.commons.math.FunctionEvaluationException;
20import org.apache.commons.math.MaxIterationsExceededException;
21import org.apache.commons.math.analysis.UnivariateRealFunction;
22import org.apache.commons.math.util.FastMath;
23
24/**
25 * Implements the <a href="http://mathworld.wolfram.com/Bisection.html">
26 * bisection algorithm</a> for finding zeros of univariate real functions.
27 * <p>
28 * The function should be continuous but not necessarily smooth.</p>
29 *
30 * @version $Revision: 1070725 $ $Date: 2011-02-15 02:31:12 +0100 (mar. 15 févr. 2011) $
31 */
32public class BisectionSolver extends UnivariateRealSolverImpl {
33
34    /**
35     * Construct a solver for the given function.
36     *
37     * @param f function to solve.
38     * @deprecated as of 2.0 the function to solve is passed as an argument
39     * to the {@link #solve(UnivariateRealFunction, double, double)} or
40     * {@link UnivariateRealSolverImpl#solve(UnivariateRealFunction, double, double, double)}
41     * method.
42     */
43    @Deprecated
44    public BisectionSolver(UnivariateRealFunction f) {
45        super(f, 100, 1E-6);
46    }
47
48    /**
49     * Construct a solver.
50     *
51     */
52    public BisectionSolver() {
53        super(100, 1E-6);
54    }
55
56    /** {@inheritDoc} */
57    @Deprecated
58    public double solve(double min, double max, double initial)
59        throws MaxIterationsExceededException, FunctionEvaluationException {
60        return solve(f, min, max);
61    }
62
63    /** {@inheritDoc} */
64    @Deprecated
65    public double solve(double min, double max)
66        throws MaxIterationsExceededException, FunctionEvaluationException {
67        return solve(f, min, max);
68    }
69
70    /**
71     * {@inheritDoc}
72     * @deprecated in 2.2 (to be removed in 3.0).
73     */
74    @Deprecated
75    public double solve(final UnivariateRealFunction f, double min, double max, double initial)
76        throws MaxIterationsExceededException, FunctionEvaluationException {
77        return solve(f, min, max);
78    }
79
80    /** {@inheritDoc} */
81    @Override
82    public double solve(int maxEval, final UnivariateRealFunction f, double min, double max, double initial)
83        throws MaxIterationsExceededException, FunctionEvaluationException {
84        return solve(maxEval, f, min, max);
85    }
86
87    /** {@inheritDoc} */
88    @Override
89    public double solve(int maxEval, final UnivariateRealFunction f, double min, double max)
90        throws MaxIterationsExceededException, FunctionEvaluationException {
91        setMaximalIterationCount(maxEval);
92        return solve(f, min, max);
93    }
94
95    /**
96     * {@inheritDoc}
97     * @deprecated in 2.2 (to be removed in 3.0).
98     */
99    @Deprecated
100    public double solve(final UnivariateRealFunction f, double min, double max)
101        throws MaxIterationsExceededException, FunctionEvaluationException {
102
103        clearResult();
104        verifyInterval(min,max);
105        double m;
106        double fm;
107        double fmin;
108
109        int i = 0;
110        while (i < maximalIterationCount) {
111            m = UnivariateRealSolverUtils.midpoint(min, max);
112           fmin = f.value(min);
113           fm = f.value(m);
114
115            if (fm * fmin > 0.0) {
116                // max and m bracket the root.
117                min = m;
118            } else {
119                // min and m bracket the root.
120                max = m;
121            }
122
123            if (FastMath.abs(max - min) <= absoluteAccuracy) {
124                m = UnivariateRealSolverUtils.midpoint(min, max);
125                setResult(m, i);
126                return m;
127            }
128            ++i;
129        }
130
131        throw new MaxIterationsExceededException(maximalIterationCount);
132    }
133}
134