Outputting Zeroes Problem

[gregfifth]

Working on a problem and I am somewhat lost about the mechanics of what needs to be done. I've fleshed it out the best I can but I can tell from my output it's completely off. Instructions are akin to:

given function f(x) = x^3 - 6x^2 - 7x
Write a program that outputs any zero of f(x) (i.e., the value of x for which f(x)=0). Zero is between xleft and xright. Randomly set up values of xleft and xright.
Divide integers xleft and xright in half, compute value of function f(xmid). if positive, xright=xmid.
Halfing of the interval should be done for as long as the value of f(xmid) < AbsoluteCC ie-g.


1.Generate randomly xright
2. Generate randomly xleft so it’s different. Figure out condition.
3. If (xleft > xright), swap.
4. Obtain xmid
5.if f(xmid) has same sign as f(xright) then xright = xmid etc.
Same with xleft
6. Half intervals and calculate xmid as long as |f(x_mid)| < 0

and the code I have so far is:

#include <iomanip>
#include <iostream>
#include <cmath>
using namespace std;
unsigned int seed;

double f (double x);
double random (unsigned int& seed);

double x, x_left, x_right, x_mid;
int main()
{
    x_right = rand()*random(seed);
    x_left = random(seed);
    if (x_left >x_right)
    {
        x_left = x_left + x_right;
        x_right = x_left - x_right;
        x_left = x_left - x_right;
    }
    x_mid = x_left + x_right / 2;
    if (f(x_mid) > 0)
        x_right = x_mid;
    else
        x_left = x_mid;
    
    cout << "The zeroes are: ";
    cout << endl;
    do
    {
        x_left = x_left/2;
        x_right = x_right/2;
        cout << f(x_mid);
        cout << endl;
    } while (f(x_mid) < 0);
    
    return 0;
}

double f (double x)
{
    return pow(x,3) - 6 * pow(x,2) - 7*x;
}

double random (unsigned int& seed)
{
    const int MODULUS = 15749;
    const int MULTIPLIER = 69069;
    const int INCREMENT = 1;
    seed = ((MULTIPLIER * seed) + INCREMENT)%MODULUS;
    return double(seed)/double(MODULUS);
}

I'm aware this post is sort of a mess so I really appreciate all help.

[Thomas1965]

You are stuck in an endless loop since you dont modify x_mid.

 do
    {
        x_left = x_left/2;
        x_right = x_right/2;
        cout << f(x_mid);
        cout << endl;
    } while (f(x_mid) < 0);

Divide integers xleft and xright in half, compute value of function f(xmid). if positive, xright=xmid.

Why don't you use integers as instructed?

[keskiverto]

First, know your function. It crosses the x-axis three times. Easy to test:

#include <iomanip>
#include <iostream>
#include <cmath>

double f (double x);

int main()
{
  for ( int x = -20; x < 21; ++x ) {
    std::cout << std::setw(3) << x << std::setw(5) << f(x) << '\n';
  }
  return 0;
}

double f (double x)
{
  return pow(x,3) - 6 * pow(x,2) - 7*x;
}

I would select x_right form a "sane range" and then select y_left from range [bottom,x_right).
That way y_left is automatically smaller than x_right.

Divide integers xleft and xright in half, compute value of function f(xmid).

Bad wording. Set the xmid to be the average of x_left and x_right.

Halfing of the interval should be done for as long as the value of f(xmid) < AbsoluteCC

Bad wording. You want the f(xmid) to get close to 0.0.

|f(x_mid)| < 0

Closer, but an absolute value is never less than 0.

The |f(x_mid)| is positive. When it is less than some small "epsilon", it is "close enough to 0.0".
while ( ! (abs( f(xmid) ) < epsilon) )

[gregfifth]

I did set xmid to be the average of x_left and x_right on line 21. Or am I supposed to put that in the? The absolute value help was useful, thanks.
Here's my int main after trying to follow along:

int main()
{
    x_right = rand()%30;
    for (int i = 0; i < x_right; ++i)
        x_left = random(seed);
    
    if (x_left > x_right)
    {
        x_left = x_left + x_right;
        x_right = x_left - x_right;
        x_left = x_left - x_right;
    }
    
    if (f(x_mid) > 0)
        x_right = x_mid;
    else
        x_left = x_mid;
    
    cout << "The zeroes are: ";
    cout << endl;
    do
    {
        x_left = x_left/2;
        x_right = x_right/2;
        x_mid = x_left + x_right / 2;
        cout << abs(f(x_mid));
        cout << endl;
    } while (abs(f(x_mid)) < 0.5);
    
    
    return 0;
}

but still getting a nonsense output

[keskiverto]

This program uses same search algorithm, although it seeks randomly selected 'answer' rather than x, where f(x)==0.

#include <random>
#include <chrono>
#include <iostream>

void print( int a, int b ) {
  std::cout << '[' << a << ", " << b << "]\n";
}

int main()
{
  unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
  std::default_random_engine generator(seed);
  std::uniform_int_distribution<int> upperlimit(0, 30);
  int x_right = upperlimit(generator);
  std::uniform_int_distribution<int> lowerlimit(-30, x_right - 1);
  int x_left = lowerlimit(generator);
  print( x_left, x_right ); // original range

  std::uniform_int_distribution<int> range(x_left, x_right);
  const int answer = range(generator);
  std::cout << "Seeking " << answer << '\n';

  int x_mid = (x_left+x_right) / 2;
  while ( x_mid != answer ) {
    if ( x_mid < answer ) {
      x_left = x_mid;  // narrow range from left
    }
    else {
      x_right = x_mid; // narrow range from right
    }
    print( x_left, x_right ); // new range
    x_mid = (x_left+x_right) / 2;
  }
  std::cout << "Found " << x_mid << '\n';
  return 0;
}

[gregfifth]

Is the function included in that code? that looks way above what (basic) concepts I'm trying to work though I really do appreciate the effort. At this point I'm just trying to tweak the int main that I have now so that it follows those 6 points well enough

[keskiverto]

No, there is no function there, just as I wrote. You are probably confused by the C++11 random number generation part, which is rather verbose.

No matter how you generate random numbers, you can always affect the range that they are in. They don't have to be in [0.0..1.0) or [0..N).
See http://www.cplusplus.com/reference/cstdlib/rand/

Compare this (pseudo) to your main():

int main()
{
  double x_right = // random int number in some range
  double x_left = // random int number in range that is up to x_right-1

  double x_mid = (x_left+x_right) / 2; // first guess
  double y = f( x_mid );
  while ( /* y is not close enough to 0 */ ) {
    if ( 0.0 < y ) {
      x_left = x_mid;  // narrow range from left
    }
    else {
      x_right = x_mid; // narrow range from right
    }
    x_mid = (x_left+x_right) / 2; // next guess
    y = f( x_mid );
  }
  std::cout << "f(x) is 0, when x=" << x_mid << '\n';
  return 0;
}