Farey/Stern-Brocot approximation to a real number

[Larson730]

I have to create a program that approximates a real number using two endpoints (-0,1) and (1,0). I have to compute the mediant and decide whether x is smaller or larger than it, and move x accordingly. I have to keep doing this in a loop until the mediant is within 10^-6 of x. I have a basic algorithm down but I'm stuck on where to start. Any help is appreciated.

 #include <iostream>
#include <cstdlib>

using namespace std;

const double TOL = 1E-5;

int main(int argc,char *argv[])  {
  int 
    lowN=0, lowD=1,
    highN=1, highD=0;

  double x;

  // get x from argv[1]

  // do

    // find mediant


    // figure our which side of mediant x is on

    // adjust low or high endpoint

  // while distance from x to mediant is > TOL


  // output mediant AS A FRACTION


  return 0;
} 

[Chervil]

Well I'd prefer to use a struct or class to hold the two parts (numerator and denominator) of the fraction. Things might become a bit confusing with individual variables.

But that aside, you just need to put together each step of your algorithm.
example:

// find mediant
    int mN = lowN + highN;
    int mD = lowD + highD;

// figure our which side of mediant x is on
    double mediant = double(mN) / double(mD);
    if (mediant < X)
    {
        etc.

[Larson730]

Thank you that helped a lot, but I am still a little confused.
This is what I have going so far, I know there are plenty of errors.

#include <iostream>
#include <cstdlib>

using namespace std;

const double TOL = 1E-5;

int main(int argc,char *argv[])  {
  int 
    lowN=0, lowD=1,
    highN=1, highD=0;

  double x;
  double mediant;

  // get x from argv[1]

  do {

    // find mediant

  int mN = lowN + highN;
  int mD = lowD + highD; 

    // figure our which side of mediant x is on

  double mediant = double(mN) / double(mD);

    // adjust low or high endpoint

  if(mediant < x)  {
    mediant = mD;}
  else  {
    mediant = mN;
  }

  // while distance from x to mediant is > TOL

  while(mediant - x > TOL)  {

  // output mediant AS A FRACTION

    cout << mediant << endl;
  }
}

  return 0;
} 

[Chervil]

// adjust low or high endpoint

  if(mediant < x)  {
    mediant = mD;}
  else  {
    mediant = mN;
  }

Here, the low or high endpoint which needs to be adjusted is the values stored in lowN, lowD or highN, highD.

Also, you have a do-while loop which doesn't look right.
it starts with do on line 19 and ends with the closing brace at line 46.
But the condition seems to be missing.
it should be something like:

    do 
    {
        // body of loop here 
    } while (condition);

I think you should not output the result until after the end of that loop. Though of course during testing it can be useful to put additional cout statements in order to help understand what is going on.

One more comment, about this condition: (mediant - x > TOL)
Be careful, as the value of mediant may be either larger or smaller than x, thus the difference between the two may be either positive or negative. You may want to use the fabs() function to get the absolute value (with no sign).
( fabs(mediant - x) > TOL)

http://www.cplusplus.com/reference/cmath/fabs/

[Larson730]

So i've made some adjustments and believe i'm almost there. I still think I'm not doing the while loop correctly because I'm getting an error when compiling.

on line 54: expected 'while' before numeric constant
expected '(' before numeric constant
expected ')' before ';' token


Here's what I have so far any tips?

#include <iostream>
#include <cstdlib>

using namespace std;

const double TOL = 1E-5;

int main(int argc,char *argv[])  {
  int 
    lowN=0, lowD=1,
    highN=1, highD=0;

  double x;
  double mediant;

  // get x from argv[1]

  x = atof(argv[1]);

  do {

    // find mediant

  int mN = lowN + highN;
  int mD = lowD + highD; 

    // figure our which side of mediant x is on

  double mediant = double(mN) / double(mD);

    // adjust low or high endpoint

  if(mediant < x)  {
    mN = lowN;
    mD = lowD;  }
  else  {
    mN = highN;
    mD = highD;
  }


  // while distance from x to mediant is > TOL

  
  while(x - mN > TOL * mD);


  // output mediant AS A FRACTION

    cout << mN << "/" << mD << endl;
  
}

  return 0;
}

[Chervil]

Well,at line 53, you have the closing brace of the do- loop which started at line 21.

And then somewhere in the middle, floating around on its own is the while part, on line 46.

So you need to move either the brace, or the while, so that they are next to one another, as I showed previously.

[Larson730]

If I move the brace I get an error that my variables aren't declared. How would I work around that?

[Chervil]

Well, a variable declared inside braces { ) cannot be accessed from outside that scope. The answer is to declare all the variables before the start of the loop. I notice that mediant is declared twice, at lines 15 and 30. It should be declared just once, at line 15. And the variables int mN, mD; need to be declared somewhere around that point too.

I notice a couple of logic errors. After comparing x with the mediant at line 34, the current values of either the low or high endpoint needs to be replaced with the current mN, mD values. At the moment, the code leaves the endpoints unchanged, so the program will never terminate. The idea is that the endpoints are gradually moved closer together so that the required result is enclosed between them.

Also, I don't understand the intention behind the condition here: while(x - mN > TOL * mD);. I may be wrong, but I would have expected something more like this: while ( fabs(x - mediant) > TOL);