fbpx

C++: Continued Fraction

Bjarne-stroustrup
 

A number may be represented as a continued fraction (see Mathworld for more information) as follows:

a_0 + \cfrac{b_1}{a_1 + \cfrac{b_2}{a_2 + \cfrac{b_3}{a_3 + \ddots}}}

The task is to write a program which generates such a number and prints a real representation of it. The code should be tested by calculating and printing the square root of 2, Napier’s Constant, and Pi, using the following coefficients:

For the square root of 2, use a0 = 1 then aN = 2. bN is always 1.

\sqrt{2} = 1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \ddots}}}

For Napier’s Constant, use a0 = 2, then aN = N. b1 = 1 then bN = N − 1.

e = 2 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{2}{3 + \cfrac{3}{4 + \ddots}}}}

For Pi, use a0 = 3 then aN = 6. bN = (2N − 1)2.

\pi = 3 + \cfrac{1}{6 + \cfrac{9}{6 + \cfrac{25}{6 + \ddots}}}

#include <iomanip>
#include <iostream>
#include <tuple>

typedef std::tuple<double,double> coeff_t; // coefficients type
typedef coeff_t (*func_t)(int); // callback function type

double calc(func_t func, int n)
{
	double a, b, temp = 0;
	for (; n > 0; --n) {
		std::tie(a, b) = func(n);
		temp = b / (a + temp);
	}
	std::tie(a, b) = func(0);
	return a + temp;
}

coeff_t sqrt2(int n)
{
	return coeff_t(n > 0 ? 2 : 1, 1);
}

coeff_t napier(int n)
{
	return coeff_t(n > 0 ? n : 2, n > 1 ? n - 1 : 1);
}

coeff_t pi(int n)
{
	return coeff_t(n > 0 ? 6 : 3, (2 * n - 1) * (2 * n - 1));
}

int main()
{
	std::streamsize old_prec = std::cout.precision(15); // set output digits
	std::cout 
	<< calc(sqrt2, 20) << '\n'
	<< calc(napier, 15) << '\n'
	<< calc(pi, 10000) << '\n'
	<< std::setprecision(old_prec); // reset precision
}
Output:
1.41421356237309
2.71828182845905
3.14159265358954

SOURCE

Content is available under GNU Free Documentation License 1.2.