//C1
//Solve a function,using Newton Methom

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

//Original Function
double func(double x)  
{
	return x*x*x+x*x-3*x-3;
}

//Differencial Function
double dfunc(double x)
{
	return 3*x*x+2*x-3;
}

//decide whether a number is approximate enough to 0
int iszero(double x)
{
	if (fabs(x)<1e-7)
	    return 1;
	else
		return 0;
}

//Newton Methom
//Troot:tolerantion of root;Tf:toleration of function
int nmf(double x,double Troot,double Tf,long N,int time)      
{
	double x1;
    if (iszero(dfunc(x))==0    && 	 N>0    )
	{
		x1=x-func(x)/dfunc(x);
		time++;
		if (fabs(x1-x)<Troot  ||   fabs(func(x1))<Tf)
		{   
			cout<<"The root is: "<<x1<<endl;              //output the root
			cout<<"The error is: "<<fabs(func(x1))<<endl; //output the error
			cout<<"iteration times"<<time;
			return 1;
		}
		else
		{
			nmf(x1,Troot,Tf,N-1,time);
		}
	}
	else
	{
	     cout<<"This methom doesnot work properly.It will return a unkonwn number"<<endl;	
	}
	return 0;
}

void main()
{
	double x=1.5,Troot=1e-7,Tf=1e-7;          //Initilaze node and tolerance
	long N=1000000;       
	clock_t start, finish;                    //Initilaze times
    start = clock();                          // Gets system time 
	nmf(x,Troot,Tf,N,0);       
	finish = clock();                         // Gets system time again 
	cout<<"The methom takes time: "<<(double)(finish - start) / CLOCKS_PER_SEC<<endl;
	cin>>x;
}

//解為x=1.73205
//僅迭代4次，精度達到了7.977e-12，程序執行時間<0.01s
//可見在知道解的大致值的情況下，Newton Methom是相當好的解法