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.