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?
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.
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
The Final Conclusion
Sometimes the best solution is brute force. Sometimes just good old math.