C++: Construct from Rational Number

Bjarne-stroustrup
 

To understand this task in context please see Continued fraction arithmetic

The purpose of this task is to write a function r2cf(int N1,int N2), or r2cf(Fraction N), which will output a continued fraction assuming:

N1 is the numerator
N2 is the denominator

The function should output its results one digit at a time each time it is called, in a manner sometimes described as lazy evaluation.

To achieve this it must determine: the integer part; and remainder part, of N1 divided by N2. It then sets N1 to N2 and N2 to the determined remainder part. It then outputs the determined integer part. It does this until abs(N2) is zero.

Demonstrate the function by outputing the continued fraction for:

1/2
3
23/8
13/11
22/7
-151/77

\sqrt 2 should approach [1; 2, 2, 2, 2, \ldots] try ever closer rational approximations until boredom gets the better of you:

14142,10000
141421,100000
1414214,1000000
14142136,10000000

Try :

31,10
314,100
3142,1000
31428,10000
314285,100000
3142857,1000000
31428571,10000000
314285714,100000000

Observe how this rational number behaves differently to \sqrt 2 and convince yourself that, in the same way as 3.7 may be represented as 3.70 when an extra decimal place is required, [3;7] may be represented as [3;7,\infty] when an extra term is required.

#include <iostream>
/* Interface for all Continued Fractions
Nigel Galloway, February 9th., 2013.
*/
class ContinuedFraction {
public:
	virtual const int nextTerm(){};
	virtual const bool moreTerms(){};
};
/* Create a continued fraction from a rational number
Nigel Galloway, February 9th., 2013.
*/
class r2cf : public ContinuedFraction {
private: int n1, n2;
public:
	r2cf(const int numerator, const int denominator): n1(numerator), n2(denominator){}
	const int nextTerm() {
		const int thisTerm = n1/n2;
		const int t2 = n2; n2 = n1 - thisTerm * n2; n1 = t2;
		return thisTerm;
	}
	const bool moreTerms() {return fabs(n2) > 0;}
};
/* Generate a continued fraction for sqrt of 2
Nigel Galloway, February 9th., 2013.
*/
class SQRT2 : public ContinuedFraction {
private: bool first=true;
public:
	const int nextTerm() {if (first) {first = false; return 1;} else return 2;}
	const bool moreTerms() {return true;}
};

Testing

int main() {
	for(r2cf n(1,2); n.moreTerms(); std::cout << n.nextTerm() << " ");
	std::cout << std::endl;
	for(r2cf n(3,1); n.moreTerms(); std::cout << n.nextTerm() << " ");
	std::cout << std::endl;
	for(r2cf n(23,8); n.moreTerms(); std::cout << n.nextTerm() << " ");
	std::cout << std::endl;
	for(r2cf n(13,11); n.moreTerms(); std::cout << n.nextTerm() << " ");
	std::cout << std::endl;
	for(r2cf n(22,7); n.moreTerms(); std::cout << n.nextTerm() << " ");
	std::cout << std::endl;
	for(r2cf cf(-151,77); cf.moreTerms(); std::cout << cf.nextTerm() << " ");
	std::cout << std::endl;
	return 0;
}
Output:
0 2
3
2 1 7
1 5 2
3 7
-1 -1 -24 -1 -2

\sqrt 2

int main() {
	int i = 0;
	for(SQRT2 n; i++ < 20; std::cout << n.nextTerm() << " ");
	std::cout << std::endl;
	for(r2cf n(14142,10000); n.moreTerms(); std::cout << n.nextTerm() << " ");
	std::cout << std::endl;
	for(r2cf n(14142136,10000000); n.moreTerms(); std::cout << n.nextTerm() << " ");
	std::cout << std::endl;
	return 0;
}
Output:
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
1 2 2 2 2 2 1 1 29
1 2 2 2 2 2 2 2 2 2 6 1 2 4 1 1 2

SOURCE

Content is available under GNU Free Documentation License 1.2.