from math import isinf
from sys import float_info
twopow = 2.0**(float_info.max_exp-1)

def msum(iterable):
    # assumes no infinities and nans in the input
    def add_to_partials(x):
        i = 1
        for y in partials[1:]:
            if abs(x) < abs(y):
                x, y = y, x
            hi = x+y
            # if hi overflows, adjust x by +-2**max_exp, adjust
            # partials[0] accordingly, and recompute
            if isinf(hi):
                if x > 0:
                    x = x-twopow-twopow
                    partials[0] += 1.0
                else:
                    x = x+twopow+twopow
                    partials[0] -= 1.0
                hi = x+y
            x, lo = hi, y - (hi - x)
            if lo:
                partials[i] = lo
                i += 1
        partials[i:] = [x] if x else []

    partials = [0.0]
    for x in iterable:
        add_to_partials(x)

    psum = sum(partials[1:], 0.0)
    if not partials[0]:
        # usual case
        return psum
    elif partials[0] == 1.0 and psum < 0.0:
        partials[0] -= 1.0
        add_to_partials(twopow)
        add_to_partials(twopow)
        if partials[0] == 0.0:
            return sum(partials[1:], 0.0)
    elif partials[0] == -1.0 and psum > 0.0:
        partials[0] += 1.0
        add_to_partials(-twopow)
        add_to_partials(-twopow)
        if partials[0] == 0.0:
            return sum(partials[1:], 0.0)

    if partials[0] > 0:
        return float('inf')
    else:
        return float('-inf')


if __name__ == '__main__':

    test_values = [
        ([], 0.0),
        ([0.0], 0.0),
        ([1e100, 1.0, -1e100, 1e-100, 1e50, -1.0, -1e50], 1e-100),
        ([1e308, 1e308, -1e308], 1e308),
        ([-1e308, 1e308, 1e308], 1e308),
        ([1e308, -1e308, 1e308], 1e308),
        ([2.0**1023, 2.0**1023], float('inf')),
        ([2.0**1023, 2.0**1023, -1.0], float('inf')),
        ([2.0**1023, 2.0**1023, -2.0**1000], 1.7976930277114552e+308),
        ([twopow, twopow, twopow, twopow, -twopow, -twopow], float('inf')),
        ([twopow, twopow, twopow, twopow, -twopow, -twopow, -twopow], 8.9884656743115795e+307),
        ([2.0**53, -0.5, -2.0**-54], 2.0**53-1.0),
        ([2.0**1023-2.0**970, -1.0, 2.0**1023], 1.7976931348623157e+308),
        ([2.0**1023-2.0**970, 0.0, 2.0**1023], float('inf')),
        ([2.0**1023-2.0**970, 1.0, 2.0**1023], float('inf')),
    ]
    
    for i, (vals, s) in enumerate(test_values):
        m = msum(vals)
        if m != s:
            print "Test %d failed: %r vs %r expected for %r." % (i, m, s, vals)