“Tabulation method to find the first bracket of a function”
Abstract—This paper discusses finding out the first bracket between which the root of a given function f(x) would be found by using the natural tabulation method. The time complexity and scalability of the algorithm are analyzed. The results indicate that the algorithm is scalable and efficient.
I. Introduction
Finding out the bracket between which the root of a given function f(x) would be found by using several methods they are natural tabulation method, some iterative methods are Newton Raphson method, Regula falsi (false position) method, bisection method, secant method, Muller’s method. This work discusses finding the first bracket between which the root of a given function found by the natural tabulation method. What is natural tabulation is explained as follows for the given function
Example., f(x)=x2-12.
Here we need to find the first bracket between which the root of function f(x) should lies. So the method it’s self tells us to tabulate each value of x for which the value of function f(x) changes. In this method, we are initializing the x top, x bottom, and x delta (for increment, next step x delta will be 0.1,0.01...) values. The tabulation is as shown in below table1.
x_top=?, x_bottom=0, x_delta=1
x
|
0
|
1
|
2
|
3
|
4
|
f(x)
|
-12
|
-11
|
-08
|
-03
|
04
|
Table 1: natural tabulation method.
Now mark x_top=3, x_bottom=4, x_delta=0.1
x
|
3.0
|
3.1
|
3.2
|
3.3
|
3.4
|
3.5
|
f(x)
|
-3.0
|
-2.39
|
-1.76
|
-1.11
|
-0.43
|
0.25
|
Table 2: second iteration natural tabulation method.
When the sign of the function f(x) changes from negative to positive or vice-versa at this moment we mark the value which changing from negative to positive value as the first bracket. Then the third iteration of tabulation begins by updating the values of x top=4, x bottom=3.4, x delta=0.01. The second iteration is shown in below table 3.
x
|
3.4
|
3.41
|
3.42
|
3.43
|
3.44
|
3.45
|
f(x)
|
Table 3: third iteration of the natural tabulation method.
When the sign of the function f(x) changes from negative to positive or vice-versa at this moment we mark the value which changing from negative to positive value as the second bracket. Then the fourth iteration of tabulation begins by updating the values of x top, x bottom, x delta till we get an appropriate root. When the value of f(x) remains the same for next or constant for the next values of x, then we mark that value as the root of the function f(x). For the above-taken function f(x)=x2-12 the root found to be 3.46. The main advantage of this method is, it is easy to compute and calculate but the disadvantage is it’ll take more iterations to find the exact root.
II. Algorithm development
The natural tabulation method initially, accepts two stack data structures to hold the data values of table x and f(x) it is shown in below table 4.
Stack s[n]
top
|
.
|
.
|
.
|
xn
|
top
|
.
|
.
|
.
|
f(xn)
|
stack a[n]
Table 4: stack for x and function f(x).
Then accept a polynomial equation of degree n, then accept x_top, x_bottom, x_delta values. Compute the value of function f(x) then push each value of x and f(x) to the corresponding stack x and stack f(x). Then display the stack's content by calling display function. When v observe the change in sign of function f(x) delete that value from the stack by calling pop function or directly display the previous value from the stack f(x). Then carry out the next iterations until we get a constant value for function f(x) then display the x value from the top of the stack x that’s the root of a given function f(x).
To find the first bracket, two iterations are enough to find the exact root then continue with the next iterations as explained above.
Algorithm first_bracket_tabulation_ method
Input top, float s[9999],a[9999], xbottom, xtop, xdelta, x, fx, c;
Output first bracket;
Function to push
function push1(float *x)
{
if(top==stack_size-1)
{
print"stack overflow"
return ;
}
Topßtop+1;
s[top]ß*x;
}
function push2(float *fx)
{
if(top==stack_size-1)
{
print"stack overflow\n"
return;
}
Topßtop+1;
a[top]ß*fx;
}
Function to display stack x elements
function display1()
{
input i;
output s[]
if(top==-1)
{
print"stack x is empty";
return 0;
}
print"contents of the stack x";
for i=0 to i<=top
{
Print s[i];
ißi++;
}
}
Function to display stack f(x) elements
function display2()
{
Input i;
Output a[]
if(top==-1)
{
print"stack f(x) is empty";
return 0;
}
print"contents of the stack f(x)";
for i=0 to i<=top
{
Print a[i];
ißi++;
}
}
function root(float *x)
{
float bracket_found;
if(top==-1)
return 0;
bracket_foundßs[top];
return bracket_found;
}
function pop1()
{
float item_deletedx;
if(top==-1)
return 0;
item_deletedxßs[top--];
return item_deletedx;
}
int pop2()
{
float item_deletedfx;
if(top==-1)return 0;
item_deletedfxßa[top--];
return item_deletedfx;
}
function main()
{
Input choice, topß-1;
for(;;)
{
print"\n\nfinding the first bracket between which root of f(x) by tabulation method\n\n";
print"1:enter x_top and x_bottom and x_delta value\n2:push 3:display 4:root? 5:pop 6:exit\n";
print"enter the choice\t";
accept chßchoice
switch(choice)
{
case 1:
print "decide the values of x_top,x_bottom,x_delta";
accept
x_topßxtop, x_bottomßxbottom,x_deltßxdelta;
print "x_topßxtop,
x_bottomßxbottom, x_deltaßxdelta;
break;
case 2:
print"enter the value for x constant C";
accept x,c;
print"xßval, cßval";
fxß((pow(x,2))+(c));
print"fxßval”;
function push1(&x);
function push2(&fx);
break;
case 3:function display1();function display2();
break;
case 4: function root(&x);
break;
case 5: function pop1();function pop2();
break;
default:exit(0);
}
}
}
III. Algorithm and analysis of the algorithm
main
Frequency Best worst
Input choice, topß-1;
function main()
{
for(;;)--------------------------n------------1---------n
{
accept chßchoice-----------n------------1---------n
switch(choice)
{
case 1:
accept
x_topßxtop, -----------
x_bottomßxbottom,-----3n---------3--------3n
x_deltßxdelta;----------
break;
case 2:
accept x,c;
fxß((pow(x,2))+(c));--------n---------1---------n
fnction push1(&x);-----------n---------1---------n
fumction push2(&fx);--------n---------1---------n
break;
case 3:
function display1();----------n---------1-----------n
function display2();----------n---------1-----------n
break;
case 4:
function root(&x); ----------n---------1-----------n
break;
case 5:
function pop1();----------n---------1-----------n
function pop2();----------n---------1-----------n
break;
default:exit(0); -------------1---------1-----------1
}
}
}
Function to push
function push1(float *x)
{
if(top==stack_size-1) ;-------------------n--------1---------n
{
print"stack overflow"
return ;
}
Topßtop+1;-------------------n--------1---------n
s[top]ß*x; ;-------------------n--------1---------n
}
function push2(float *fx)
{
if(top==stack_size-1) ;-------------------n--------1---------n
{
print"stack overflow\n"
return;
}
Topßtop+1; ;-------------------n--------1---------n
a[top]ß*fx; ;-------------------n--------1---------n
}
Function to display stack x elements
function display1()
{
input i;
output s[]
if(top==-1) ;-------------------n--------1---------n
{
print"stack x is empty";
return 0;
}
print"contents of the stack x";
for i=0 to i<=top;-------------------n--------1---------n
{
Print s[i];
ißi++;;-------------------2--------1---------n
}
}
Function to display stack f(x) elements
function display2()
{
Input i;
Output a[]
if(top==-1) ;-------------------n--------1---------n
{
print"stack f(x) is empty";
return 0;
}
print"contents of the stack f(x)";
for i=0 to i<=top
{
Print a[i];
ißi++;;----------------2--------1---------n
}
}
function root(float *x)
{
float bracket_found;
if(top==-1) ;-------------------n--------1---------n
return 0;
bracket_foundßs[top];------1--------1---------n
return bracket_found;
}
function pop1()
{
float item_deletedx;
if(top==-1) ;-------------------n--------1---------n
return 0;
item_deletedxßs[top--];----3--------1---------n
return item_deletedx;
}
int pop2()
{
float item_deletedfx;
if(top==-1)return 0; --------------n--------1---------n
item_deletedfxßa[top--];--];----3--------1---------n
return item_deletedfx;
}
IV. Experimentation and profiling
A priori Analysis:
A Priori Analysis is analyzing the algorithm and calculating the computation time for the algorithm is termed as A Priori Analysis. After having made an analytical review of the algorithm, the calculated time complexity for it is of the O(n2).
Computing the time complexity:
Tbest α 0
Ω (0).
A Posteriori Analysis:
A Posteriori Analysis is Analysis is done after the execution of the algorithm in the Computer. This Analysis is also called as Profiling.
Tworst α 2*1+1*1+3*n+2(n)+3(n)-2(n)-2(n)+...
Tworst α ∞
Tworst α ∞
O(∞).
Below figure 5 shows the time complexity graph for finding out the first bracket between which the root of a given function f(x) would be found by using the natural tabulation method.
Figure 5 computing the time complexity for the tabulation method.
V. Summary / conclusion
The time complexity for finding the first bracket of a given function tΩ α 0 and tO α ∞. In the worst-case, the time complexity of the algorithm tends to infinity because computational or execution steps tend to infinity.
References
[1] R. Hammons, Jr., P. V. Kumar, A. R. Calderbank, N. J. A. Sloane, and P.Sol´e, The Z4-linearity of Kerdock, Preparata, Goethals, and related codes.
[2] P. Delsarte, An algebraic approach to coding theory, Philips Research reports Supplements 10 (1973).
[3] Computer Algorithms by Horowitz E., Sahni S., Rajasekaran S., Galgotia Publications, 2001.
[4] R.G. Dromey, How to solve by computer, Prentice Hall of India, New Delhi, 2004.
[5] Some Characterizations of numerical methods, Issue 1767. Author: Robert A. Melter Publisher: University of Maryland, 1987.
