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:
Code:
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):
Code:
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:
