### Farey/Stern-Brocot approximation to a real number

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.

 ``123456789101112131415161718192021222324252627282930313233`` `````` #include #include 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; } ``````
Last edited on
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:
 ``123456789`` ``````// 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.``````

Last edited on
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.

 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950`` `````` #include #include 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; } ``````
 ``30313233343536`` ``````// 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:
 ``1234`` `````` 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/
Last edited on
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?

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657`` `````` #include #include 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; } ``````

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.
Last edited on
If I move the brace I get an error that my variables aren't declared. How would I work around that?
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);`
Topic archived. No new replies allowed.