-
Notifications
You must be signed in to change notification settings - Fork 0
/
continuedFraction.cpp
68 lines (56 loc) · 1.56 KB
/
continuedFraction.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/*
* continuedFraction.cpp
*
* Created on: Oct 14, 2018
* Author: fanchen
*/
#include "continuedFraction.h"
ContinuedFraction::ContinuedFraction(int num){ // constructor
a0 = static_cast<int>(sqrt(num));
if (a0 * a0 != num){
n = num;
getPeriod(); // initialize vector period.
}
else
std::cerr << "Error! The given integer must NOT be a perfect square!" << std::endl;
};
void ContinuedFraction::getPeriod(){
int a, b, c; // each level is represented as a + (sqrt(n) - b) / c
std::map<std::pair<int, int>, bool> coeffMap; // if want to use unordered_map, must provide hash method for pair
b = a0;
c = 1;
while(true){
auto it = coeffMap.find(std::make_pair(b, c));
if (it != coeffMap.end()) // full period found
break;
else{
coeffMap[std::make_pair(b, c)] = true; // current b, c recorded
// calculate new coefficient
c = (n - b * b) / c;
a = static_cast<int>((sqrt(n) + b) / c);
b = a * c - b;
period.push_back(a); // store each a
}
}
}
mpq_class ContinuedFraction::getConvergent(int R) const{
int pLen = period.size();
mpq_class res;
if (R == 1)
return mpq_class(a0, 1);
res = 1 / mpq_class(period[(R - 2) % pLen], 1); // last element of the period
for (int i = R - 3; i >= 0; i--){ // add the rest of element, from R - 2 to 0.
res = 1 / (period[i % pLen] + res);
}
res += mpq_class(a0, 1); // add the first one
return res;
}
int ContinuedFraction::getPeriodAt(int pos) const{
return period[pos];
}
int ContinuedFraction::getPeriodLen() const{
return period.size();
}
int ContinuedFraction::geta0() const{
return a0;
}