Suppose one wishes to implement a rational-number type. We can see examples of this in NumericAnnex, SwiftRational, NumberKit, and presumably more projects that I did not find in a brief search.

Suppose further that the `Rational`

type uses `Int`

to store its `numerator`

and `denominator`

, which are kept relatively prime with positive denominator, and that we have a `gcd`

function for `Int`

(eg. the one from Numerics).

As part of the implementation, one must write an addition operator. That is, given rational numbers `u = a/b`

and `v = c/d`

, we need to compute `u + v = (a*d + b*c) / (b*d)`

. And if the new numerator and denominator share any common factors, they must be canceled out.

The question is, how can we compute the result without spurious overflow? In other words, if the resulting numerator and denominator can both be represented as `Int`

, how do we compute them without trapping?

Of course we can factor out `g = gcd(b, d)`

, and instead calculate (`a*(d/g) + (b/g)*c) / (b*(d/g))`

. This greatly improves the situation, but spurious overflow may still occur.

To illustrate the problem, imagine for the moment that we used `Int8`

instead of `Int`

, so the maximum representable value is 127. Now suppose we have the fractions: `u = 16/35`

and `v = 39/85`

.

The sum `u + v = 109/119`

is indeed representable with `Int8`

numerator and denominator. But consider how to compute it:

```
a = 16, b = 35
c = 39, d = 85
g = gcd(35, 85) = 5
b/g = 35/5 = 7
d/g = 85/5 = 17
a*(d/g) = 16*17 = 272
(b/g)*c = 7*39 = 273
a*(d/g) + (b/g)*c = 272 + 273 = 545
b*(d/g) = 35*17 = 595
```

Thus we have a numerator of 545 and a denominator of 595. And only now, at the very end, does it become apparent that they share a common factor of 5, so the result reduces to `(545/5) / (595/5) = 109/119`

.

But several of the intermediate steps have overflowed. Namely, 272, 273, 545, and 595 are all greater than 127. Indeed, they are even greater than 255, so working with magnitudes as `UInt8`

would not eliminate the difficulty.

We can compute the intermediate products and sums using a combination of `multipliedFullWidth`

and `addingReportingOverflow`

, which yields a pair `(Int8, UInt8)`

for both numerator and denominator (rather, `(Int, UInt)`

in a real implementation).

We could implement a `gcd`

function on these pairs, then call `dividingFullWidth`

to cancel the gcd out of the resulting numerator and denominator. This would work, though Iâ€™m not sure the best strategy for writing that `gcd`

function.

(We might also have to preemptively check the size of the pair before dividing, because the documentation for `dividingFullWidth`

merely says it â€śmayâ€ť trap if the result overflows, but does not guarantee it.)

Is this the correct approach, or is there a better way?