Avoid Needless Overflow

Question

I am stuck with a problem. I am programming a fractions calculator (for an Assignment). So far it works great, the problem is I have to handle arithmetic overflow. I did some research an understand overflow now. But, I don't know how to handle it. The overflow is caused by the simple operations between nominator and denominator.

The example we are given is that the fraction operation: 999999/1000000 * 500000/999999 should give the answer 1/2. When my program goes to multiply 999999 * 500000 there is an overflow and the end result is inaccurate (I get -2 10204169/22761874).

The main objective is to produce correct results whenever the reduced number can be correctly represented without overflow.

Any help is greatly appreciated.

I think you should - at least - tell us which language you are using. Each language has its tricks to avoid these pitfalls. Python has an even nicer trick: — jcoppens, Sep 05 '14 at 23:15
may be this [How to deal with overflow and underflow?](https://stackoverflow.com/a/33006665/2521214) will help a bit but I suspect your problem is that you are using low bit-width for sub-results ... `999999 * 500000` will not fit into 32bit int and you should use either 64 bit variables or reorder the operations so subresults will fit into your variables. If you are really using fractions (which I do not see anywhere) then you should simplify nominator and denominator when you can by dividing them both by GCD on each change... — Spektre, Jul 05 '17 at 10:49

score 0 · Answer 1 · answered Sep 05 '14 at 23:16

0

I think you should - at least - tell us which language you are using. Each language has its tricks to avoid these pitfalls. Python has an even nicer trick:

>>> from fractions import Fraction as Fraction
>>> Fraction(999999 * 500000, 1000000 * 999999)
Fraction(1, 2)

answered Sep 05 '14 at 23:16

jcoppens

5,306
6
27
47

Thanks for your answer! I'm using C++. That is a neat trick. Any way to replicate that in C++? – BugsGalore Sep 05 '14 at 23:58

score 0 · Answer 2 · answered Sep 07 '14 at 23:23

Thanks everyone for helping. I finally figured it out. I converted the fraction into a decimal by dividing the numerator by the denominator and then rounded it down using floor (); Once it was rounded down I turned it back to a fraction. Seems to work fine.

Here is the logic:

operation: 999999/1000000 * 500000/999999

Fraction was 999999/1000000
toDecimal = .999999
floor ()= 1
fraction = 1/1

Fraction was 500000/999999
toDecimal = .5000005
floor ()= .50
fraction = 1/2

operation is now 1/1 * 1/2 = 1/2 (Woohoo!)

Hope this helps someone out there with this problem.

Avoid Needless Overflow

2 Answers2