C Language Bisection Method Algorithm;Midpoint

[min01]

Hi Everybody! I need help, I can't run the program. Also I need the iteration to run at maximum of 20 only and it has to be in C language, what should I change and am I doing this right?

DIRECTIONS ARE:
Algorithm:
1. Given a polynomial equation f(x), set 2 initial x values Xlower and Xupper.
2. Find the midpoint of the x values using: xr =xupper+xlower/2

3. Substitute the value of xr to f(x). If |f(x)| ≤ 0.001, you may stop the computation – this will
serve as your stopping criteria. If not, do the following:
a. If f(xlower) ∗ f(xr) < 0, then xupper = xr and xlower remains the same.
b. If f(xlower) ∗ f(xr) > 0, then xlower = xr and xupper remains the same.
c. If f(xlower) ∗ f(xr) = 0, then xr is the solution.

Implement the algorithm until the stopping criterion is satisfied or the number of iterations
reach 20. If either happens, display the current value of xr and the current value of f(xr). If the
maximum iteration is reached, display “MAXIMUM ITERATIONS REACHED”

THANK YOU FOR YOUR HELP!!

#include<conio.h>
#include<stdio.h>
#include<math.h>

void main()
{
 float Xl,Xr,Xu,f(xl),f(xr),f(xu);
 int i=1;

 printf("Bisect the interval and locate the midpoint, Xr= (Xl+Xu)/2\n");
 printf("Solve for f(Xl),f(Xu) and f(Xr)\n");
 a:printf("Xu: ");
 scanf("%f",&f(xu));
 printf("f(xr): ");
 scanf("%f",&f(xr));
 f(xl)=f(xu);
 f(xu)=f(xr);
 if((f(xl)*f(xu))>0)

 else
 {
     printf("\t\tXl\tXr\tXu\tf(xl)\tf(xr)\tf(xu)\n");

   b: Xl=(Xu+f(xr))/2;
  Xr=f(Xl);
  printf("\nItteration: %d\t%.4f\t%.4f\t%.4f\t%.4f\t%.4f\t%.4f",i,Xl,Xr,Xu,f(xl),f(xr),f(xu);
 }
 if((f(xl)*Xr)<0)
 {
  f(xr)=Xl;
  f(xu)=Xr;
 }
 else
 {
  Xu=Xl;
  f(xl)=Xr;
 }
 if(fabs((f(xr)-Xu)/f(xr))<=e)

 else
 {       i++;
  goto b;
 }
 c:
{
    printf("MAXIMUM ITERATIONS REACHED");
}
getch();
}

[TheIdeasMan]

...am I doing this right?

Not at all. It's an unholy mess.

[min01]

Not at all. It's an unholy mess.

Oh sorry I'm just a beginner

[seeplus]

f(x) is a polynomial equation in x. For the purpose of a C program to evaluate this, you need to know what is this equation.

You can't just transfer the mathematical equation notation directly into C. Eg you try to define as float a variable f(xl). This isn't what you think it is and what you do.

For a starter you need something like:

float f(float x)
{
    // Here is where the function is actually specified and evaluated
    // If say f(x) is mathematically 4x^2 + 3x + 2 then

    return 4 * x * x + 3 * x + 2;    // Note in c that ^ is NOT power
}

Then you can call the function f with required values. eg

float f1 = f(3.5);    // Evaluates f for the value 3.5 

etc etc etc

If you don't want to specify the function itself within the program (which means a re-compile for every different function), then having the user specify the function becomes very complicated very quickly - even if the user just specifies the power co-efficients etc. I'd advise getting the program to work properly first with a specified f function - and then extend to allow the user to input info about the required function etc.

[jonnin]

equation parsers are a large project to do yourself.
a very, very simple way to deal with this is an array.
double x[10];
...
let x[0] be x^0 (again, ^ isnt power in c++, but is easy to type here)
let x[1] be x^1
let x[2] be x^2
and so on.
9 is the highest power here (because [10]), and no negative or decimal powers. anything to 0 is 1, so that is the constant term, if you missed it.

extending this simple idea, you can make a struct of (power, coefficient) and set up letting the user populate that with an interface, then you can allow negative or decimal powers. Add all the terms, and if they were really subtracted use negative on the coefficient.

beyond these basic ideas for very basic polynomials and inputting them, it gets complicated in a hurry. But that is enough to do the problem, I think.

one last cheesy way to do the polynomial is to have the user provide the f(x) function separately and you recompile for each problem. Then it can be anything, really, so long as you agree upon the parameters to the function.

[TheIdeasMan]

Oh sorry I'm just a beginner

Well, you need to start again.

Perhaps you could fix line 5:

int main(void)

@jonnin

Not sure why you mention equation parsers if the OP is struggling with the absolute basics - just saying, politely :+)

[nuderobmonkey]

You could dividing the whole task into several small steps. And, voila, writing the code will be nearly a waltz :)

#include "f.h"  // You need to implement your polynomial function!

#include <math.h>
#include <stdio.h>
#include <stdbool.h>


#define MAX_ITERATIONS 20

double x_lower = 0;
double x_upper = 0;

double x_r = 0;

bool stop_flag = false;  // flags if a solution was found

void get_input( void );       // for step 1
void calc_midpoint( void );   // for step 2
void substitute( void );      // for step 3


void get_input( void )
{
    printf( "Set two initial x values x_lower and x_upper:\n" );

    printf( "x_lower: ");
    scanf( "%lf", &x_lower );

    printf( "x_upper: ");
    scanf( "%lf", &x_upper );
}

void calc_midpoint( void )
{
    x_r = (x_upper + x_lower) / 2;
}

void substitute( void )
{
    x_r = f(x_r);

    if(  (x_r >= 0  && x_r <= 0.001)  || ( -x_r >= 0 && -x_r <= 0.001) ) // mocking the abs()
    {
        stop_flag = true;
        return;
    }

    double x_fac = f(x_lower) * f(x_r);

    if( x_fac < 0 )  x_upper = x_r;       // a.
    else if( x_fac > 0 )  x_lower = x_r;  // b.
    else  stop_flag = true;               // c.
}

int main( void )
{
    get_input();   // reads the input

    // repeat for i iterations:
    for( int i = 0; i < MAX_ITERATIONS; ++i )
    {
        calc_midpoint();
        substitute();

        if( stop_flag == true )  // If a solution was found
            break;
    }

    if( stop_flag == true )  printf( "xr = %lf, f(xr) = %lf\n", x_r, f(x_r) );
    else  printf( "MAXIMUM_ITERATIONS REACHED\n" );

    return 0;
}

[min01]

You could dividing the whole task into several small steps. And, voila, writing the code will be nearly a waltz :)

Oh thank you so much now it's more clearer to me but unfortunately I can't run it and also I forgot I need to print out a table for every iteration.
-Iteration number
-Xlower
-Xupper
-Xr
-f(xlower)
-f(Xr)
-f(Xupper)

sorry for the inconvenience

[lastchance]

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
using namespace std;


//======================================================================


double f( const vector<double> &c, double x )       // evaluates polynomial c0 + c1.x + c2.x^2+ ... + cN.x^N
{
   double result = 0;
   for ( int i = c.size() - 1; i >= 0; i-- ) result = c[i] + x * result;
   return result;
}


//======================================================================


int main()
{
   const int MAXITER = 40;       // greater than your teacher wants
   const double EPS = 1.0e-20;   // smaller than your teacher wants

   int N;
   cout << "Input degree of polynomial (N): ";
   cin >> N;

   vector<double> c( N + 1 );
   cout << "Input coefficients c0 c1 ... c" << N << ": ";
   for ( int i = 0; i <= N; i++ ) cin >> c[i];

   double xlow, xhigh, xr, flow = 1, fhigh = 1, fr;
   while( flow * fhigh > 0 )
   {
      cout << "Input xlow, xhigh: ";   cin >> xlow >> xhigh;
      flow = f( c, xlow );
      fhigh = f( c, xhigh );
   }

   int i = 0;
   for ( string s : { "i", "xlow", "xhigh", "xr", "flow", "fhigh", "fr" } ) cout << setw( 14 ) << s;
   cout << '\n';
   while ( ++i <= MAXITER )
   {
      xr = 0.5 * ( xlow + xhigh );
      fr = f( c, xr );

      cout << setw( 14 ) << i;
      for ( double d : { xlow, xhigh, xr, flow, fhigh, fr } ) cout << setw( 14 ) << d;
      cout << '\n';

      if ( abs( fr ) < EPS ) break;
      if ( flow * fr < 0 )
      {
         xhigh = xr;
         fhigh = fr;
      }
      else
      {
         xlow = xr;
         flow = fr;
      }
   }

   if ( i > MAXITER )  cout << "Not converged in maximum iterations";
   else                cout << "Solution is " << xr << '\n';
}

Input degree of polynomial (N): 3
Input coefficients c0 c1 ... c3: -1 3 -3 1
Input xlow, xhigh: -10 10
             i          xlow         xhigh            xr          flow         fhigh            fr
             1           -10            10             0         -1331           729            -1
             2             0            10             5            -1           729            64
             3             0             5           2.5            -1            64         3.375
             4             0           2.5          1.25            -1         3.375      0.015625
             5             0          1.25         0.625            -1      0.015625    -0.0527344
             6         0.625          1.25        0.9375    -0.0527344      0.015625  -0.000244141
             7        0.9375          1.25       1.09375  -0.000244141      0.015625   0.000823975
             8        0.9375       1.09375       1.01562  -0.000244141   0.000823975    3.8147e-06
             9        0.9375       1.01562      0.976562  -0.000244141    3.8147e-06  -1.28746e-05
            10      0.976562       1.01562      0.996094  -1.28746e-05    3.8147e-06  -5.96046e-08
            11      0.996094       1.01562       1.00586  -5.96046e-08    3.8147e-06   2.01166e-07
            12      0.996094       1.00586       1.00098  -5.96046e-08   2.01166e-07   9.31323e-10
            13      0.996094       1.00098      0.998535  -5.96046e-08   9.31323e-10  -3.14321e-09
            14      0.998535       1.00098      0.999756  -3.14321e-09   9.31323e-10  -1.45519e-11
            15      0.999756       1.00098       1.00037  -1.45519e-11   9.31323e-10   4.91127e-11
            16      0.999756       1.00037       1.00006  -1.45519e-11   4.91127e-11   2.27374e-13
            17      0.999756       1.00006      0.999908  -1.45519e-11   2.27374e-13  -7.67386e-13
            18      0.999908       1.00006      0.999985  -7.67386e-13   2.27374e-13  -3.55271e-15
            19      0.999985       1.00006       1.00002  -3.55271e-15   2.27374e-13   1.19904e-14
            20      0.999985       1.00002             1  -3.55271e-15   1.19904e-14             0
Solution is 1

[min01]

.

[TheIdeasMan]

sorry for the inconvenience

As long as there is no effort on your part. You are starting to look like a traffic generator. aka trolling to waste people's time.

[min01]

.

[dhayden]

Chill dude I am trying to make my own code

Please understand that a lot of people come here hoping that we'll do their homework for them. The best way to show that you aren't one of those people is to post the code that you've written so far.

Can you post the full assignment? It might give some details on how the polynomial is supposed to be entered. There might also be other little requirements that you haven't mentioned. You'd be surprised how easy it is to miss something.

[min01]

Please understand that a lot of people come here hoping that we'll do their homework for them. The best way to show that you aren't one of those people is to post the code that you've written so far.

Thank you for your response, I actually have 3 projects and I haven't edit this one yet I'm still working on the Hangman game. By the way this is the full instructions

https://drive.google.com/folderview?id=191Nw7V6i1trIenFda8lJMtXaVOfb9tLL

[min01]

UP

[TheIdeasMan]

https://www.chegg.com/homework-help/questions-and-answers/4g-ol-3g-11-38-255-kb-s-58-c-projectspdf-project-1-bisection-method-bisection-method-techn-q80148682

Well you have been given 2 strong helpful responses, and your replies are "Sorry I can't run it", no more effort on your part.

And you think you deserve more help? -> Troll.

[min01]

Well you have been given 2 strong helpful responses, and your replies are "Sorry I can't run it", no more effort on your part.

You have no idea what I've been through. Yes someone responded but the other one is a different language so I can't use it, the other one doesn't run too and I tried changing it but still won't work for me. I am lacking of sleep because of this. Stop saying I'm a troll. Also that link you sent, I can't see it because chegg isn't free. Unlucky right? Have a nice day buddy and thank you. I'll find out soon.

[dhayden]

Min01, post your code when you have some.

[min01]

Why is <math.h> and <conio.h> doesn't run in mine? I can't see the output

#include<stdio.h>

#include<conio.h>

#include<Math.h>

/*

This structure is used to store a polynomial term. An array of such terms represents a

polynomial.

The "coeff" element stores the coefficient of a term in the polynomial,while

the "exp" element stores the exponent.

*/

struct poly

{

float coeff;

int exp;

};

void main()

{

struct poly a[50];

int array[MAXSIZE];

int i, num, power;

float x;

int lower, upper;

printf("Select maximum exponent degree(1-4): \n");

scanf("%d", &num);

if(num > 4)

break;

printf("You selected ", num);

/* Read the coefficients into an array */

for (i = 0; i <= num; i++)

{

printf("Coefficient for x^",i,":");

scanf("%d", &array[i]);

}

power = num;

printf("Given polynomial is: \n");

for (i = 0; i <= num; i++)

{

if (power < 0)

{

break;

}

/* printing proper polynomial function */

printf("Your polynomial is f(x) =");

if (array[i] > 0)

printf(" + ");

else if (array[i] < 0)

printf(" - ");

else

printf(" ");

printf("%dx^%d ", abs(array[i]), power--);

}

printf("Enter lower x:");

scanf("%d",&lower);

printf("\nEnter upper x:");

scanf("%d", &upper);

f0 = f(lower);

f1 = f(upper);

/* Checking whether given guesses brackets the root or not. */

if( f0 * f1 > 0.0)

{

printf("Incorrect Initial Guesses.\n");

goto up;

}

/* Implementing Bisection Method */

printf("\nStep\t\tx0\t\tx1\t\tx2\t\tf(x2)\n");

do

{

x2 = (x0 + x1)/2;

f2 = f(x2);

printf("%d\t\t%f\t%f\t%f\t%f\n",step, x0, x1, x2, f2);

if( f0 * f2 < 0)

{

x1 = x2;

f1 = f2;

}

else

{

x0 = x2;

f0 = f2;

}

step = step + 1;

}while(fabs(f2)>e);

printf("\nRoot is: %f", x2);

getch();

}

}

[dhayden]

It looks like this is C code, not C++.

The math file is math.h, not Math.h (lower case 'm').

Regarding conio.h, See http://www.cplusplus.com/forum/beginner/1988/ for how to prevent the console from closing down.

You're trying to do too much at once. Here is a version with conio.h commented out and math.h spelled right. I ifdef-ed out everything after the code that prints the polynomial. Get this code working first. Then move the #if 0 directive down to a good stopping point to debug the next section of code.

#include<stdio.h>
// #include<conio.h>
#include<math.h>

/*
This structure is used to store a polynomial term. An array of such
terms represents a polynomial.  The "coeff" element stores the
coefficient of a term in the polynomial,while the "exp" element stores
the exponent.
*/
struct poly
{
    float coeff;
    int exp;
};

void
main()
{
    struct poly a[50];
    int array[MAXSIZE];
    int i, num, power;
    float x;
    int lower, upper;
    printf("Select maximum exponent degree(1-4): \n");
    scanf("%d", &num);
    if (num > 4)
	break;
    printf("You selected ", num);
/* Read the coefficients into an array */
    for (i = 0; i <= num; i++)
    {
	printf("Coefficient for x^", i, ":");
	scanf("%d", &array[i]);
    }
    power = num;
    printf("Given polynomial is: \n");
    for (i = 0; i <= num; i++)
    {
	if (power < 0)
	{
	    break;
	}
/* printing proper polynomial function */
	printf("Your polynomial is f(x) =");
	if (array[i] > 0)
	    printf(" + ");
	else if (array[i] < 0)
	    printf(" - ");
	else
	    printf(" ");
	printf("%dx^%d ", abs(array[i]), power--);
    }
#if 0
    printf("Enter lower x:");
    scanf("%d", &lower);
    printf("\nEnter upper x:");
    scanf("%d", &upper);
    f0 = f(lower);
    f1 = f(upper);
/* Checking whether given guesses brackets the root or not. */
    if (f0 * f1 > 0.0)
    {
	printf("Incorrect Initial Guesses.\n");
	goto up;
    }
/* Implementing Bisection Method */
    printf("\nStep\t\tx0\t\tx1\t\tx2\t\tf(x2)\n");
    do
    {
	x2 = (x0 + x1) / 2;
	f2 = f(x2);
	printf("%d\t\t%f\t%f\t%f\t%f\n", step, x0, x1, x2, f2);
	if (f0 * f2 < 0)
	{
	    x1 = x2;
	    f1 = f2;
	}
	else
	{
	    x0 = x2;
	    f0 = f2;
	}
	step = step + 1;
    } while (fabs(f2) > e);
    printf("\nRoot is: %f", x2);
    getch();
#endif
}