# Accurate sum of a range object in O(1)

I recently created a function calculating the sum of an arbitrary range object in $O(1)$:

def sum_of_range(range_obj):
"""Calculates the sum of a range object (Python 3) in O(1).

This function always returns a python integer representing the sum
without loss of precision (as would happen if it uses intermediate
floating point values).
"""
start, stop, step = range_obj.start, range_obj.stop, range_obj.step
len_ = len(range_obj)
if step > 0:
if start >= stop:
return 0
# Find the last "really" included number. Subtract one from stop
# because the stop is not included in ranges.
upper = (stop - 1 - start) // step * step + start
else:
if stop >= start:
return 0
# In case the step is negative we need to add one to the difference
upper = (stop - start + 1) // step * step + start
sum_first_and_last = upper + start
return (sum_first_and_last * len_) // 2


I used "random" tests to verify that it works:

import random

for i in range(100000):  # make a lot of random tests
up = random.randint(-10000, 10000)
lo = random.randint(-10000, 10000)
step = random.randint(-25, 25)
if step == 0:  # steps of zero are not possible
continue
rg = range(lo, up, step)
assert sum_of_range(rg) == sum(rg)


Is there any room for improvement? Especially (but not only):

• Code performance
• Should I replace the random tests with explicit tests or can I neglect explicit tests? Or should I include both?
• Not clear why you hoisted the len_ computation. You only use it once, at the end of the routine. So no performance advantage for hoisting. In cases of early exit, actually a deficit. And distance between load into local variable and use raises clarity issues. Jan 19, 2017 at 20:10
• Now that you mention it... no idea why it's hoisted. :( Jan 19, 2017 at 20:22

Let's get a closer look at the sum you're trying to calculate:

$$start + (start+step) + (start+2 \times{}step) + \ldots + (start + (len-1)\times{} step)$$

Which can be reordered as:

$$start + \ldots + start + step + 2\times{}step + \ldots + (len-1)\times{}step$$

Which gives you a nice formula regardless of the sign of start or step or even the value of stop:

$$start \times{} len + step \times\frac{len(len-1)}{2}$$

All the complexity being hidden in the len(range_obj) call. So you can just write:

def sum_of_range(range_obj):
"""Calculates the sum of a range object (Python 3) in O(1).

This function always returns a python integer representing the sum
without loss of precision (as would happen if it uses intermediate
floating point values).
"""

length = len(range_obj)
step_counts = length * (length - 1) // 2
return range_obj.start * length + range_obj.step * step_counts

• Ah, that's really clever, it took a moment to realize that one of len and len-1 is even so their product is even as well and one can safely use floor division. Thanks. Jan 19, 2017 at 21:45
• @MSeifert Yes, thats basic sum from 0 to n: en.m.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF Jan 19, 2017 at 21:48

range_obj is not a container, and you cannot rely on len(range_obj) being $O(1)$. A simple experiment

$python -mtimeit "len(range(10))" 10000000 loops, best of 3: 0.158 usec per loop$ python -mtimeit "len(range(10000000))"
10 loops, best of 3: 188 msec per loop


shows that it is in fact linear.

The bright side is that you don't need len at all. You need a number of elements, and even though it is numerically equal to len, it can (and should) be computed as

    len_ = (obj.stop - obj.start) // obj.step

• At least on my computer it's constant, what python and python version are you using? Jan 19, 2017 at 22:45
• You're probably testing in Python 2, but either way, you can't reasonably pin the linear time on len as you're timing the creation of the range object too. Instead use the setup argument to remove this possibility, as then you can time only len. Jan 20, 2017 at 2:39
• stackoverflow.com/questions/31839032/… Jan 20, 2017 at 7:07
• To expand on my last comment, I used: python -m timeit -s "r=range(10)" "len(r)", where I changed; Python versions, the size of the range, and used xrange and range in Python 2, and found no reasonable (0.1usec) change in time. Jan 20, 2017 at 10:54