# The Power of Math

Published at: 2016-10-13
Categories:
Tags:

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 `a^n + b^n`. 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 just good old math.

Similar Posts:
The comments are disabled. If you want to write something to me, you can use e.g. Twitter.