The Power of Math

In a couple of previous posts I was considering which is better in Python: map or list comprehension. The final idea was that none of them is as fast as a C++ program, even using exactly the same algorithm.

What about changing an algorithm a little bit?

The Idea

I was thinking about speeding up the Python code. Then I thought about the simple equation for calculating nth Fibonacci number. It is very simple, the algorithm complexity is not that bad, it is something like an + bn. This is much faster for bigger n then the recursive/iterative version.

If I was going to sum all the numbers from 1 to n, then I wouldn’t write this:

def sum_numbers(n):
    return sum([x for x in range(1, n+1)])

I’d rather use the quite simple equation for summing it:

sum(n) = (1 + n) * n / 2

Then the program looks like:

def sum_numbers(n):
    return (1 + n) * n / 2

The time difference is huge: n=10*1000*1000: first program: 5s, second program: 15ms. So that’s just 333 times faster.

The Solution

So what about the equation for calculating the sum of all squares of even numbers from 1 to 1,000,000?. It is very simple:

sum(n) = (4n³ + 6n² + 2n)/3

So let’s implement it and check the time:

def sum_numbers(n):
    return (4 * n**3 + 6 * n**2 + 2*n) / 3   

This runs in 10ms. Much better compared to the previous solution, which took 70s.

The Final Conclusion

Sometimes the best solution is brute force. Sometimes it’s just the good old math.