Competitve-Programming/convertToRational.cpp at master · NILESH8757/Competitve-Programming · GitHub

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
//Author: Nightshade
//https://stackoverflow.com/questions/95727/how-to-convert-floats-to-human-readable-fractions
#include<bits/stdc++.h>
using namespace std;

#define mod  1000000007
#define gcd  __gcd
typedef  long long  ll;
const long maxd=1e9+6; //maximum denominator
ll p,q;
void help(double x)   //taken from stackoverflow(visit link above)
{
    ll am[2][2],it;
    double  stx;
    stx=x;
    am[0][0]=am[1][1]=1;
    am[0][1]=am[1][0]=0;
    while(am[1][0]*(it=(ll)x)+am[1][1]<=maxd)
    {
        ll t;
        t=am[0][0]*it+am[0][1];
        am[0][1]=am[0][0];
        am[0][0]=t;
        t=am[1][0]*it+am[1][1];
        am[1][1]=am[1][0];
        am[1][0]=t;
        if(x==(double)it)
          break;
        x=1/(x-(double)it);
        if(x>(double)0x7FFFFFFF)
          break;
    }
    p=am[0][0];
    q=am[1][0];
}
int main()
{
   double x;
   cin>>x;
   help(x);
   cout<<p<<"/"<<q<<endl;

 return 0;
}