Algorithm for adding large lists of rational numbers

Handle overflows of a and b first in the two-fraction add operation. Do not form bd and then reduce it; divide by the denominator GCD first.

# all inputs already reduced; checked_ raises/reports overflow
addreduced(a, b, c, d):
    g = gcd(b, d)
    u = d / g
    v = b / g
    n = checkedadd(checkedmul(a, u), checkedmul(c, v))
    q = checkedmul(v, d)        # q == lcm(b, d), without computing b*d first
    h = gcd(abs(n), q)
    return n / h, q / h

sumrationals(xs):
    # coalesce equal denominators: a1/b + a2/b + ... = (a1+a2+...)/b
    heap = empty min-heap ordered by denominator size
    for each denominator b:
        s = checkedsumofnumeratorswiththatdenominator(b)
        push(heap, reduce(s, b))
    while heap has more than one item:
        x = pop(heap)
        y = pop(heap)
        push(heap, addreduced(x.a, x.b, y.a, y.b))
    return pop(heap)

For arbitrary input, fixed-width a and b still need overflow checks at each checked* operation. If those checks fail, use arbitrary-precision integers or change to a different exact method. Useful search terms: exact rational arithmetic, intermediate expression swell, binary splitting, rational reconstruction, Chinese Remainder Theorem.