## Objective

Create a function to find a root of a given polynomial function in a given interval.

## Difficulty

## Description

Solving a polynomial is a common activity in the study of algebra and functions. Given a particular function ::f::, its solution is defined as those values in the domain such that ::f:: map each of them to ::0::.

In notational form, this means that if ::f(x) = 0::, then ::x:: is called a solution of the polynomial. Sometimes, it's also called the root of the polynomial.

For instance, given the polynomial ::f(x) = x^2 - 2x + 1::, it has only one solution which is ::x = 1::. But if given the polynomial ::f(x) = x^2 + 2x - 15::, it has two solutions, namely ::x = -5:: and ::x = 3::.

Programatically solving a given polynomial is an interesting activity. One simple and popular technique is the ** bisection method**.

It finds a solution to a polynomial in a given interval by a divide-and-conquer strategy, i.e. continuously halving the interval until the difference between the end points (of the interval) is so small that we can safely end the computation there. At that point, the mid point of the interval is the root of the polynomial.

In more detail, the bisection method works as follows:

We are given an interval ::[a, b]:: which is merely a guess for an interval where a root of the polynomial might lie. We start by determining if there is a sign change in the interval.

If there is, then based on the fact that the function is continuous, this simply means that the function cuts through the x-axis and therefore has a root.

The way this root is found is as follows:

- The midpoint ::m:: of the interval ::[a, b]:: is computed.
- From the intervals ::[a, m]:: and ::[m, b]::, which ever has a sign change, that's used as the next interval.
- Step 1 and step 2 is repeated until the absolute difference between ::a:: and ::b:: is less than a given value, usually denoted as ::\epsilon::.

Let's demonstrate the bisection method on the function ::f(x) = x^2 + 2x - 15:: and the interval ::[2, 10]::. We'll also suppose that ::\epsilon = 0.001::.

First, let's see whether there is a sign change in the interval for ::f::. Since ::f(2) = -7:: and ::f(10) = 105::, there is clearly a sign change and we can, likewise, proceed further.

Starting with the interval ::[2, 10]:::

- The midpoint ::m:: of ::2:: and ::10:: is ::6::.
- ::f(6) = 33::, likewise from the intervals ::[2, 6]:: and ::[6, 10]::, the former interval is the one where the sign change exists. Hence, we drop ::[6, 10]:: and proceed with ::[2, 6]::.

To the next iteration with the interval ::[2, 6]:::

- The midpoint ::m:: of ::2:: and ::6:: is ::4::.
- ::f(4) = 9::, likewise from the intervals ::[2, 4]:: and ::[4, 6]::, once again the former interval is the one where the sign change exists. Hence, we drop ::[4, 6]:: and proceed with ::[2, 4]::.

To the next iteration with the interval ::[2, 4]:::

- The midpoint ::m:: of ::2:: and ::4:: is ::3::.
- ::f(3) = 0::.
*Voila!*We just found a root, i.e. ::x = 3::, and hence end the iterations.

In the case above, we hit an exact root while computing the midpoint of the given interval and had to likewise end the bisection method with that solution.

Note that this doesn't happen always — sometimes, the ::x:: values converge down to such numbers that the difference between them is less than or equal to ::\epsilon::. At that point, the midpoint of these very close values is termed as the root of the given polynomial.

In this exercise, you have to create a ** bisection()** function in order to compute a root of a given polynomial function in a particular interval, if there is a root in the interval.

The polynomial function gets passed as the first argument to `bisection()`

, while the second and third arguments represent the starting and ending points of the interval, respectively.

If there isn't a guarantee that there exists a root of the polynomial in the given interval, i.e. there is no sign change, the function `bisection()`

must return `null`

.

In addition to this, you must take ::\epsilon:: as ::0.0001:: in the function.

Following is an illustration of the usage of this function:

`function f(x) { return x ** 2 + 2 * x - 15 }`

`bisection(f, 2, 10)`

`bisection(f, -6, -4)`

`bisection(f, 3, 4)`

`bisection(f, -6, 10)`

`bisection(f, 100, 1000)`

`function f(x) { return (x - 1) * (x + 1) }`

`bisection(f, 0, 10)`

`bisection(f, -10, 0)`

`bisection(f, -10, 10)`

## New file

Inside the directory you created for this course on JavaScript, create a new folder called **Exercise-10-Bisection-Method** and put the .html solution files for this exercise within it.

## Solution

First, let's decide on the naming of `bisection()`

's parameters:

- The first argument is the polynomial function whose root we ought to find. A conventional name would be
.`f`

- The second argument is the starting point of the interval. In the discussion above, we called it ::a::, and although we could name it
`a`

in`bisection()`

as well, we'll rather go with the name. That's because with`x1`

`x1`

, it'll be easier to name the corresponding y-value, i.e.`y1`

. - On the same lines, we'll call the third argument
.`x2`

This gives us the following definition:

```
function bisection(f, x1, x2) {
// Code to go here...
}
```

Now, let's begin crafting the body of `bisection()`

.

It's a good programming practice to define constants right at the start of a script/function. In our case, the value of ::\epsilon:: is to be taken as `0.0001`

, and since this is a constant, we'll define it right at the start in `bisection()`

as ** epsilon**:

```
function bisection(f, x1, x2) {
const epsilon = 0.0001;
}
```

Up next, we'll calculate the mappings of `x1`

and `x2`

(i.e. the corresponding y-values), namely ** y1** and

**, and then check whether either of them is**

`y2`

`0`

.If that is the case, it means that we're provided with a root of the polynomial function and hence should return that root, without executing any further.

This is accomplished below:

```
function bisection(f, x1, x2) {
const epsilon = 0.0001;
var y1 = f(x1);
var y2 = f(x2);
// If provided with a root, return that root.
if (y1 === 0) {
return x1;
}
if (y2 === 0) {
return x2;
}
}
```

The first step in `bisection()`

is to determine whether there is a sign change in the given interval. This requires a simple `if`

condition.

If there is no sign change, we assume the worst case that there is no root in the interval, and just return `null`

:

```
function bisection(f, x1, x2) {
const epsilon = 0.0001;
var y1 = f(x1);
var y2 = f(x2);
// If provided with a root, return that root.
if (y1 === 0) {
return x1;
}
if (y2 === 0) {
return x2;
}
// If there is no sign change in the interval [x1, x2],
// return null.
if (y1 * y2 > 0) {
return null;
}
}
```

*sure*about this, and therefore to keep from running into a meaningless iteration, we return

`null`

.If the `if`

block above gets skipped, that simply means that there is a sign change in the interval and therefore there is surely at least one root to find.

Step one is to calculate the difference in the provided `x1`

and `x2`

values. If the difference is less than or equal to `epsilon`

which is `0.0001`

, then this repetitive bisection must end.

Needless to say the idea of repetitively bisecting the given interval hints us at a loop, and specifically a `while`

loop as we don't know the number of iterations to be performed. The loop's condition is simple — if the difference between `x1`

and `x2`

is greater than `epsilon`

, we must continue with the bisection.

Thus far, we get to the following code:

```
function bisection(f, x1, x2) {
const epsilon = 0.0001;
var y1 = f(x1);
var y2 = f(x2);
// If provided with a root, return that root.
if (y1 === 0) {
return x1;
}
if (y2 === 0) {
return x2;
}
// If there is no sign change in the interval [x1, x2],
// return null.
if (y1 * y2 > 0) {
return null;
}
var xMid, yMid;
var diff = Math.abs(x1 - x2);
while (diff > epsilon) {
// Code to go here...
}
}
```

Note the use of `Math.abs()`

in computing the difference between `x1`

and `x2`

. It's necessary because we are only interested in how close are the given values together, not in the sign of the difference.

Inside the `while`

loop, we first compute the mid point of `x1`

and `x2`

, namely `xMid`

, and then compute its mapping under the provided function `f`

. We call this mapping of `xMid`

as `yMid`

.

After this, we check which interval has the sign change and then proceed with that interval for the next iteration, after recomputing the absolute difference between `x1`

and `x2`

.

Here's the code accomplishing all of this:

```
function bisection(f, x1, x2) {
const epsilon = 0.0001;
var y1 = f(x1);
var y2 = f(x2);
// If provided with a root, return that root.
if (y1 === 0) {
return x1;
}
if (y2 === 0) {
return x2;
}
// If there is no sign change in the interval [x1, x2],
// return null.
if (y1 * y2 > 0) {
return null;
}
var xMid, yMid;
var diff = Math.abs(x1 - x2);
while (diff > epsilon) {
xMid = (x1 + x2) / 2;
yMid = f(xMid);
// If the mid point is a root, return it.
if (yMid === 0) {
return xMid;
}
// Determine which of the intervals [x1, xMid] and [xMid, x2]
// has the sign change, and then continue with that interval.
if (y1 * yMid <= 0) {
x2 = xMid;
}
else {
x1 = xMid;
}
diff = Math.abs(x1 - x2);
}
// Code to go here...
}
```

In the end, we calculate the mid point of `x1`

and `x2`

again, based on their new values, and then round the result to 3 decimal places.

Here's the complete definition of `bisection()`

:

```
function bisection(f, x1, x2) {
const epsilon = 0.0001;
var y1 = f(x1);
var y2 = f(x2);
// If provided with a root, return that root.
if (y1 === 0) {
return x1;
}
if (y2 === 0) {
return x2;
}
// If there is no sign change in the interval [x1, x2],
// return null.
if (y1 * y2 > 0) {
return null;
}
var xMid, yMid;
var diff = Math.abs(x1 - x2);
while (diff > epsilon) {
xMid = (x1 + x2) / 2;
yMid = f(xMid);
// If the mid point is a root, return it.
if (yMid === 0) {
return xMid;
}
// Determine which of the intervals [x1, xMid] and [xMid, x2]
// has the sign change, and then continue with that interval.
if (y1 * yMid <= 0) {
x2 = xMid;
}
else {
x1 = xMid;
}
diff = Math.abs(x1 - x2);
}
xMid = (x1 + x2) / 2
return Number(xMid.toFixed(3));
}
```

Note the expression `Number(xMid.toFixed(3))`

. `xMid.toFixed(3)`

serves to round `xMid`

to 3 decimal places and then return the result in the form of a string. `Number()`

then converts this string into a number that can be returned by `bisection()`

.

And this completes the exercise.