This program was working fine yesterday, and then all of a sudden today it isn't working and I haven't changed anything?! It complies OK, but for for easy functions that I enter and know the roots of, it says there is no root.

Can anyone please explain what is going on?

``````#include <iostream>
#include <cmath>

using namespace std;

void bisection(double a, double b, double epsilon, int max, double A, double B, double C);
double f(double, double, double, double);

int main()
{
int max = 0; // maximum number of iterations
double a = 0.0; // left endpoint of original interval
double b = 0.0; // right endpoint of the original interval
double epsilon = 0.0; // convergence criterion
double A = 0.0; // A coefficient of inputed quadratic equation
double B = 0.0; // B coefficient of inputed quadratic equation
double C = 0.0; // C coefficient of inputed quadratic equation

cout << "Enter coefficents of a quadratic equation\n"
<< "in the following order: Ax^2 + Bx + C = 0" << endl;
cout << "\nEnter A: ";
cin >> A;
cout << "Enter B: ";
cin >> B;
cout << "Enter C: ";
cin >> C;
cout << "\nEnter the left endpoint of the original search interval (a): ";
cin >> a;
cout << "Enter the right endpoint of the original search interval (b): ";
cin >> b;
cout << "Enter the convergence criteria: ";
cin >> epsilon;
cout << "Enter the maximum number of iterations allowed: ";
cin >> max;

bisection(a, b, epsilon, max, A, B, C);

return 0;
}// end of main

void bisection(double a, double b, double epsilon, int max, double A, double B, double C)
{
int i = 0; // current iteration loop variable
double x1 = 0.0; // left endpoint of current interval
double x2 = 0.0; // right endpoint of current interval
double xmid = 0.0; // computed midpoint of current interval
double f1 = 0.0; // function evaluated at left endpoint of current interval
double f2 = 0.0; // function evaluated at right endpoint of current interval
double fmid = 0.0;; // function evaluated at computed midpoint of current interval
double width = 0.0; // width of original interval (b - a)
double curwidth = 0.0; // width of current interval (xmid - x1)
x1 = a;
xmid = b;
f1 = f(x1, A, B, C);
fmid = f(xmid, A, B, C);
width = (b - a);
// verify there is a root in the interval
if (f1 * fmid > 0.0)
{
cout << "\nNo root in the original interval exists" << endl;
}
else
{
for (i = 1; i <= max; i++)
{
x2 = (x1 + xmid) / 2.0;
cout << "The next midpoint, approximation is " << x2 << endl;
f2 = f(x2, A, B, C);

if (f1 * f2 <= 0.0) // root is in left half interval
{
curwidth = (x2 - x1) / 2.0;
fmid = f2;
xmid = x2;
}
else // root is in right half interval
{
curwidth = (xmid - x2) / 2.0;
f1 = f2;
x1 = x2;
}
if (curwidth < epsilon)
{
cout << "\nA root at x = " << x2 << " was found "
<< "in " << i << " iterations" << endl;
cout << "The value of the function is " << f2 << endl;
return;
}
}
}
cout << "***** BISECTION METHOD *****"
<< "\nAfter " << max << " iterations, no root was found "
<< "within the convergence criterion\n"
<< "The search for a root has failed due to excessive iterations\n"
<< "after the maximum number of " << max << " iterations" << endl;
return;
}// end of bisection

double f(double x, double A, double B, double C) // function to evaluate f(x)
{
return A * pow(x, 2) + B * x + C;
}// end of f``````

## All 5 Replies

Hopefully you found it in your code, but the midpoint on an interval from a to b is (a+b)/2 not b. And the opposite signs should be at the ends of the interval, so line 61 should be `if(f1 * f2 > 0.0)` since the sign criteria is showing that from one end of the interval to the other the function passes through zero.

It's hard to track your code because it has no formatting, and no conventional naming scheme is used. Here's an example:

``````int main
{
double end_point[2]  = {0.0},
epsilon       = 0.0,

cout << "Text\nText\n"; cin >> co_of_quad[0];
cout << "Something"; cin >> co_of_quad[1];
...``````

A style more like that would make it dramatically easier for anyone to diagnose this code.

Thank you very much for the replies, I am new to C++ but I have tried to take on board what you have said improved my code. I have also changed it so that it can evaluate it for any polynomial.

Jonsca - I am calculating the midpoint how you are saying however this happens a few lines later.

The previous code was actually working, however I was entering the number of possible iterations as 1 million and it wouldn't work like that for some reason.

So now everything is working fine, testing for x^2 - 9, over the interval (0,5) gives me a root of 3, however for the very end bit where it says "the value of the function is..." it seems to be giving out garbage for f2 instead of the zero I'm after, however I'm not sure why this is? If anyone can spot the reason for this I would be very grateful.

``````#include <iostream>
#include <vector>

using namespace std;

//Declare functions
void bisection(vector<double> A, double a, double b, double epsilon, double p, int max, int degree);
double f(vector<double>, double, double, int);

//---------------------------------------------------------------------------------------

int main()
{
vector<double> A;                  // vector of coefficients a^degree...a^0
int degree;                        // highest degree
double p;                          // p(x)
double x;                          // value which p is evaluated at
int max = 0;                       // maximum number of iterations
double left_endpoint = 0.0;        // left endpoint of original interval
double right_endpoint = 0.0;       // right endpoint of the original interval
double epsilon = 0.000001;         // convergence criterion

bisection(A, left_endpoint, right_endpoint, epsilon, p, max, degree);

return 0;
}

//---------------------------------------------------------------------------------------

void bisection(vector<double> A, double left_endpoint, double right_endpoint, double epsilon, double p, int max, int degree)
{

cout << "For polynomial p(x) = a0 + a1x + a2x^2 + ... + anx^n" << endl;
cout << "Enter the polynomial degree, n" << endl;
cout << "Example:  2 for a quadratic, 3 for a cubic..." << endl;
cout << "Degree: ";
cin >> degree;

A.resize (degree + 1);

for (int i = degree; i >= 0; i--)
{
cout << "Enter coefficient a" << i << ": ";
cin >> A[i];
}

cout << "\nEnter the left endpoint of the original search interval (a): ";
cin >> left_endpoint;
cout << "Enter the right endpoint of the original search interval (b): ";
cin >> right_endpoint;
cout << "Enter the maximum number of iterations allowed: ";
cin >> max;

double x1 = 0.0; // left endpoint of current interval
double x2 = 0.0; // right endpoint of current interval
double xmid = 0.0; // computed midpoint of current interval
double f1 = 0.0; // function evaluated at left endpoint of current interval
double f2 = 0.0; // function evaluated at right endpoint of current interval
double fmid = 0.0;; // function evaluated at computed midpoint of current interval
double width = 0.0; // width of original interval (b - a)
double curwidth = 0.0; // width of current interval (xmid - x1)

x1 = left_endpoint;

f1 = f(A, x1, p, degree);

xmid = right_endpoint;

fmid = f(A, xmid, p, degree);

width = (right_endpoint - left_endpoint);

// verify there is a root in the interval
if (f1 * fmid > 0.0)
{
cout << "\nNo root in the original interval exists" << endl;
}
else
{
for (int i = 1; i <= max; i++)
{
x2 = (x1 + xmid) / 2.0;
cout << "The next midpoint, approximation is " << x2 << endl;
f2 = f(A, x2, p, degree);
if (f1 * f2 <= 0.0) // root is in left half interval
{
curwidth = (x2 - x1) / 2.0;
fmid = f2;
xmid = x2;
}
else // root is in right half interval
{
curwidth = (xmid - x2) / 2.0;
f1 = f2;
x1 = x2;
}
if (curwidth < epsilon)
{
cout << "\nA root at x = " << x2 << " was found "
<< "in " << i << " iterations" << endl;
cout << "The value of the function at the root is " << f2 << endl;
return;
}
}
}

cout << "***** BISECTION METHOD *****"
<< "\nAfter " << max << " iterations, no root was found "
<< "within the convergence criterion\n"
<< "The search for a root has failed due to excessive iterations\n"
<< "after the maximum number of " << max << " iterations" << endl;

return;
}// end of bisection

//---------------------------------------------------------------------------------------

double f(vector<double> A, double x, double p, int degree)// function to evaluate p(x)
{
p = A[degree];
for (int i = (degree - 1); i >= 0; i--)
{
p = p*x;
p = p+A[i];
}

return p;
}// end of f

//---------------------------------------------------------------------------------------``````

That's not garbage, that's floating point for ya. Change line 84 (just for illustrative purposes) to `cout << "The next midpoint, approximation is " <<fixed<<setprecision(7)<< x2 << endl;` and include <iomanip>. Your answers had some roundoff when they were displayed and that roundoff is on the order of 10^-6 hence your "garbage."

btw, I understand your response from before, but until I used it my way I was getting that nothing had roots!

Thank you so much jonsca, you are brilliant :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.