/********************************************************************
* Program 1.1:	Incremental Search Method for the roots of f(x)=0.	*
*				Coded by Dilip Datta								*
*																	*
*********************************************************************/

# include "acm.h"

int main()
{
	int i;
	float dx, eps;

	void insearch(float dx, float eps);

	printf("\nProblem ID in function.c                                : ");
	scanf("%d", &problem_id);
	printf("\nLower and upper limits of root-searching                : ");	/* Step-1 */
	scanf("%f %f", &xl, &xu);
	printf("\nA small positive number as converging factor            : ");
	scanf("%f", &eps);

	printf("\n\n");
	printf("Results from Incremental-Search Method for roots of f(x) = 0\n");
	printf("------------------------------------------------------------\n");
	printf("Problem ID                   : %d\n", problem_id);
	printf("Limits of search             : (%f, %f)\n", xl, xu);
	printf("Converging factor            : %f\n", eps);

	dx = (xu-xl)/10;

	insearch(dx, eps);

	if(rcnt > 0)
	{
		if(rcnt == 1) 	printf("\nRequired real root           :");
		else       		printf("\nReal roots (total=%d)         :", rcnt);

		for(i = 1; i <= rcnt-1; i++)  printf(" %f,", rx[i]);
		printf(" %f\n", rx[rcnt]);
	}
	else	printf("\nThere is no real root in the given limit\n");

	if(icnt > 0)
	{
		printf("\nPoints of infinity (total=%d) :", icnt);

		for(i = 1; i <= icnt-1; i++)  printf(" %f,", ix[i]);
		printf(" %f\n", ix[icnt]);
	}

	printf("\nNo. of function evaluations  : %d\n\n", nfun);

	return(0);
}
/********************************************************************/

void insearch(float dxi, float eps)
/* Sub-routine for Incremental-Search Method for roots of f(x)=0 */
{
	float x1, x2, dx, f1, f2, df1, df2;
	float x2o, f2o, df2o;

	void rtfunct(float x);

	dx = dxi;																/* Step-2 */
	x1 = xl;

	rtfunct(x1);
    recover_rtfunct(&f1, &df1);

	for(; ;)																/* Step-3 */
	{
		iroot(&x1, &x2, &f1, &f2, &df1, &df2, dx, eps);						/* Step-4 */

		if(end == TRUE) return;												/* Step-5 */

		if(f1*f2 < 0 || df1*df2 < 0)										/* Step-6 */
		{
			x2o = x2;		/* Original values of x2, f2 & df2 */			/* Step-7 */
			f2o = f2;
			df2o = df2;
			fvalue = FALSE; /* Function values at x1 to be copied from at x2 */

			do																/* Step-8 */
			{
				if(f2 == 0)													/* Step-9 */
				{ 
					dx = dxi;
					troot(x2, dx, eps, x2o, f2o, df2o, &x1, &f1, &df1);
				}
				else
				{
					if(fabs(f2) > 1/eps)									/* Step-10 */
					{
						dx = dxi;
						root = FALSE;

						troot(x2, dx, eps, x2o, f2o, df2o, &x1, &f1, &df1);
					}
					else
					{
						if(f1*f2 < 0)										/* Step-11 */
						{
							if(dx <= eps)									/* Step-12 */
							{
								dx = dxi;
								troot(x2, dx, eps, x2o, f2o, df2o, &x1, &f1, &df1);
							}
							else											/* Step-13 */
							{
								dx /= 10;
								x2 = x1+dx;

								rtfunct(x2);
								recover_rtfunct(&f2, &df2);
							}
						}
						else
						{
							if(df1*df2<0)									/* Step-14 */
							{
								if(dx<=eps)									/* Step-15 */
								{
									if(fabs(f2)<=eps)						/* Step-16 */
									{
										dx = dxi;
										troot(x2, dx, eps, x2o, f2o, df2o, &x1, &f1, &df1);
									}
									else									/* Step-17 */
									{
										dx = dxi;
										x1 = x2o;
										f1 = f2o;
										df1 = df2o;
									}
								}
								else										/* Step-18 */
								{
									dx /= 10;
									x2 = x1+dx;

									rtfunct(x2);
									recover_rtfunct(&f2, &df2);
								}
							}
							else											/* Step-19 */
							{
								x1 = x2;
								f1 = f2;
								df1 = df2;
								x2 = x1+dx;

								rtfunct(x2);
								recover_rtfunct(&f2, &df2);
							}
						}
					}
				}

				if(end == TRUE) return;										/* Step-20 */
			}while(dx!=dxi);												/* Step-21 */
		}
		else																/* Step-22 */
		{
			x1 = x2;
			f1 = f2;
			df1 = df2;
		}
	}																		/* Step-23 */

	return;
}
/********************************************************************/