Continued Fractions of Sqrt's Implementation (Example & Source)

[AceInfinity]

I was writing an implementation in C++, and came up with (by the output of my continued fraction list function), a cheap (dirty?, and not to mention slow) way to calculate the fraction approximations of sqrt(2) lol.

*Note: Here I didn't even use the output of my continued fraction list function, because the list for sqrt(2) is very simple and unique. With a whole part of 1, the rest is just repetitions of 2 lol.

The code which generated the output in the image above:

int solve()
{
	Fraction f(1,2);
	int limit = 20, i = 2;
	do
	{
		std::cout << i << " > " << f + Fraction(1) << std::endl;
		f = Fraction(2) + f; Fraction::Reciprocal(f);
	} while (++i <= limit);
	return 0;
}

Where Fraction is a struct I created myself, to manage numerator and a denominator, and also simplify the fraction automatically. I just overloaded a few operators, but other than that, it's a very simple type.

Here is my continued fraction list method to calculate the cf list for the sqrt(n) (along with the other misc functions):

bool isSquareNum(int n)
{
	int product;
	for (int i = 1; (product = i * i) <= n; i++)
	{
		if (product == n) return true;
	} return false;
}

void contFracOfSqrt(int n, std::vector<int>& v)
{
	if (isSquareNum(n)) v.push_back((int) sqrt(n));
	else
	{
		int f1_num = 0, f1_den = 1, f3_den;
		do {
			int nextn = (int) ((floor(sqrt(n)) + f1_num) / f1_den);
			v.push_back(nextn);
			int f2_num = f1_den;
			int f2_den = f1_num - f1_den * nextn;
			f3_den = (n - f2_den * f2_den) / f2_num;
			int f3_num = -f2_den;
			f1_num = f3_num;
			f1_den = f3_den;
		} while (f3_den != 1);
		v.push_back((v[0] * 2));
	}
}

This is a sqrt implementation. Page of reference: Continued Fractions - An introduction

I use the reciprocal of a fraction in the form 1/(n/m) for instance to avoid having to actually divide say a fraction of 1/1 and n/m to make the calculation easier. Because it is known that 1/(n/m) is the same as m/n.

:cheers: