//http://www.timestocome.com
//Linda Macphee-Cobb
//fall 99

//find the root of a function using a combination
//newton-ralphston method and bisection
//root is known to be between 'left' and 'right'
//if next n-r step is w/i the known area it is taken
//else the bisection method is used.


#include <stdio.h>
#include <math.h>

int main (void){

	double left, fLeft, right, fRight, best, fBest, derivative_best, delta;
	int tempRight, tempLeft;

	double tol = 0.00005;
	int		count = 0;
	left = 0.0;							//the left bound
	right = 3.0;						//the right bound

	//function to solve => f(x) = cos(x) - x;
	//derivative => f'(x) = -sin(x) - 1;

	fLeft = cos(left) - left;			//substitute x with left bound
	fRight = cos(right) - right;		//substitute x with right bound
	
	if((fLeft * fRight) > 0){			//verify root is bracketed	
		printf("\n root is not bracketed..!!");
		printf("\n enter a new left and right root seperated by a space.>  \n");
		scanf( "%d %d", &left, &right);
	}
 
	tempRight = sqrt(fRight*fRight);
	tempLeft = sqrt(fLeft*fLeft);
	
	if(tempLeft < tempRight){
		best = left;
		fBest = fLeft;
	}else{
		best = right;
		fBest = fRight;
	}
	
	derivative_best = -sin(best) -1;	//plug best into the derivative in place of x


	while(count < 30){
	count += 1;
	
	//determine which method to use
	if(((derivative_best * (best - left) - fBest) *
		(derivative_best * (best - right) - fBest)) > 0){

		//take a newton-ralphston step
		delta = - fBest/derivative_best;
		best += delta;
	}else{
		//take a bisection step
		delta = (right - left)/2.0;
		best = (left + right)/2.0;
	}

	if(sqrt((delta*delta)/(best*best))< tol){
		//found the root
		printf("\n the solution is...  %lf\n", best);
		break;
	}else{
		//run through loop again
		fBest = cos(best) - best;			//substitute function and best in place of x
		derivative_best = -sin(best) -1;	//substitute f' and best in place of x

		//adjust brackets
		if(fLeft*fBest < 0){
			right = best;
			fRight = fBest;
		}else{
			left = best;
			fLeft = fBest;
		}
	}

		

	}

	if(count >= 29){
		printf( "\n no convergance...., sorry");
	}

	return 0;

}