HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Accurate sum of a range object in O(1)

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
rangeobjectaccuratesum

Problem

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
        # instead of subtracting one.
        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 readability



  • Code performance



  • Should I replace the random tests with explicit tests or can I neglect explicit tests? Or should I include both?

Solution

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

Code Snippets

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

Context

StackExchange Code Review Q#153068, answer score: 7

Revisions (0)

No revisions yet.