[C++] 유리수 클래스(class Fraction) 구현

프로그래밍을 할 때 실수를 쓸 일이 있으면 대부분 double을 사용하지만 PS계에서는 스페셜 저지가 붙어 있지 않은 한 이런 행위는 죄악에 가깝다. 대표적인 예시가 바로 4225번. square-root를 다루는 주제에 스페셜 저지도 안 붙어 있어서, 입력값이 10000 이하임에도 불구하고 int128을 써야 하는 괴상한 문제다. 어쨌든 높은 정밀도를 위해서는, long double에 안주하지 말고 더 정확한 값을 얻을 수 있는 방법이 무엇일지를 생각해 놓아야 한다. 오차는 계산할 때마다 계속해서 불어나는 성질이 있다. 2.5를 반올림해서 3으로 표현한다면, 2.5 * 2.5는 실제로는 6.25지만 데이터 상으로는 3 * 3 해서 9가 되는 것이다. double을 쓰면 어쩔 수 없이 오차가 있을 수밖에 없다. 0.1이 2진법으로 무한소수라서 어떤 컴퓨터에서는 0.1 + 0.2 == 0.3 같은 식이 false가 된다는 사실은 잘 알려져 있을 것이다.

using namespace std;
using int64 = long long;
using int128 = __int128;

class Fraction {
    int128 q, p;
public:
    Fraction(int128 _q, int128 _p) : q(_q), p(_p) {
        if (p < 0) {
            q *= -1; p *= -1;
        }
        abbre();
    }
    Fraction(int64 n) : q(n), p(1) {}
    
private:
    Fraction& abbre() {
        if (q == 0) {
            return *this;
        }
        int128 tp = gcd(p, q);
        p /= tp; q /= tp;
        
        return *this;
    }
    
    static int128 gcd(int128 a, int128 b) {
        if (a < 0) {a *= -1;}
        if (b < 0) {b *= -1;}
        
        if (a > b) {
            return gcd_sub(a, b);
        } else {
            return gcd_sub(b, a);
        }
    }
    
    static int128 gcd_sub(int128 a, int128 b) {
        if (a % b == 0) {
            return b;
        } return gcd_sub(b, a % b);
    }
    
public:
    Fraction operator+(const Fraction &r) const {
        return Fraction(q * r.p + p * r.q, p * r.p);
    }
    Fraction operator*(const Fraction &r) const {
        return Fraction(q * r.q, p * r.p);
    }
    Fraction operator/(const Fraction &r) const {
        return Fraction(q * r.p, p * r.q);
    }
    Fraction operator/(long long n) const {
        return Fraction(q, p * n);
    }
    
public:
    Fraction non_int_part() const {
        return Fraction(q % p, p);
    }
    
    bool operator<(const Fraction& r) const {
        return q * r.p < p * r.q;
    }
    bool operator==(const Fraction& r) const {
        return q * r.p == p * r.q;
    }
};