Fraction class for finding square root 2 convegerence

Question

I made a class that can add, multiply and divide fractions which is presented below

class fraction
{
    unsigned long long num, denom;

public:
    fraction(int n, int d): num{n}, denom{d} {};
    fraction& operator+=(fraction frac);
    fraction& operator*=(fraction frac);
    fraction& operator/=(fraction frac);
    friend ostream& operator<<(ostream& os, const fraction& frac);
};

fraction& fraction::operator+=(fraction frac) 
{
    unsigned long long least_mult = lcm(denom, frac.denom); // Least-Common Multiple
    num *= least_mult/denom;
    num += frac.num*least_mult/frac.denom,
    denom = least_mult;
    return *this;
}

fraction& fraction::operator*=(fraction frac)
{
    num *= frac.num;
    denom *= frac.denom;
    return *this;
}

fraction& fraction::operator/=(fraction frac)
{
    num *= frac.denom;
    denom *= frac.num;
    return *this;
}

ostream& operator<<(ostream& os, const fraction& frac)
{
    os << frac.num << '/' << frac.denom;
    return os;
}

fraction operator+(fraction a, fraction b) {return a+=b;}
fraction operator*(fraction a, fraction b) {return a*=b;}
fraction operator/(fraction a, fraction b) {return a/=b;

}

When I try to compute square root two convergence using sqrt_two = 1 + 1/(1+sqrt_two) recursive relation when I get up to 4478554083/3166815962, the next value is 8399386631/7645270045 which is totally off as it is about 1.098, and therefore all the subsequent values are wrong too.

int main() 
{
    fraction one(1, 1), sqrt_two(3,2);

    for(int i = 1; i < 50; ++i)
    {
        sqrt_two = one + one/(one+sqrt_two);
        cout << sqrt_two << endl;
    }

    return 0;
}

I have tried 1+1/(1+8399386631/7645270045)) manually on a calculator and the result is still a square root convergent.

score 1 · Accepted Answer · edited May 23 '17 at 12:22

1

Looking at your code, there are lines that are susceptible to overflow. Perhaps one has happened in this case. For example,

num += frac.num*least_mult/frac.denom,

(which looks like it contains a typo, incidentally).

So, I'd suggest you see how to check for overflow, and then somehow incorporate it into your class. I'm not sure what you should do in such a case, though.

edited May 23 '17 at 12:22

Community

1
1

answered May 31 '15 at 19:09

Ami Tavory

74,578
11
141
185

score 1 · Answer 2 · answered May 31 '15 at 19:12

To compute the step that gives bad results you multiply two numbers of about 32 bits. The result exceeds the long long size (64 bit if unsigned) and you end up having wrong result because of overflow. A calculator (using more bits or silently converting to floating point) overcomes this problem.

Fraction class for finding square root 2 convegerence

2 Answers2