// Arup Guha
// 1/27/2012
// Example of Newton's Algorithm

#include <math.h>

double f(double x);
double fprime(double x);
double bisectionGetRoot(double low, double high, int maxiter);

int main() {

    printf("root is %.9lf\n", bisectionGetRoot(-1,0,100));
    return 0;
}

// The specific function to test the algorithm.
double f(double x) {
    return -x*x*x - cos(x);
}


// Root must lie in [p0, p1] and function must be increasing
// or decreasing in that range.
double bisectionGetRoot(double p0, double p1, int maxiter) {

    int i=1;

    // Figures out if the function is increasing or decreasing on
    // this interval.
    int up = 0;
    if (f(p0) < f(p1))
        up = 1;

    while (i <= maxiter) {

        double p2 = (p0+p1)/2;
        printf("Iter %d: %.9lf\n", i, p2);

        if (fabs(p2 - p1) < 0.000000001)
            return p2;

        i++;

        // Adjust low or high based on (a) which direction the function is moving
        // and (b) whether or not our new guess is more or less than 0.
        if (up) {
            if (f(p2) < 0)
                p0 = p2;
            else
                p1 = p2;
        }
        else {
            if (f(p2) > 0)
                p0 = p2;
            else
                p1 = p2;
        }
    }

    // Algorithm Failed.
    return -1;

}