patternpythonMinor
Sum of even Fibonacci numbers
Viewed 0 times
evennumbersfibonaccisum
Problem
So, in my first attempt I created a code that generated all fibonacci numbers and appended to a list. This list I then traversed to get the even numbers and added them up. It worked, but took like 5 complete seconds to work.
Then I decided to not create a list and add the even numbers as I'm generating them. It looked like this
It still took quite a lot of time (didn't record it) compared to the people who got it done in like 100 milliseconds or something (I got this question on Project Euler).
Is there a way to make it faster?
Here's the link to the problem
https://projecteuler.net/problem=2
Then I decided to not create a list and add the even numbers as I'm generating them. It looked like this
a = 1
b = 1
c = 0
Sum = 0
while c<4000000:
c = a + b
if c%2==0:
Sum+=c
a = b
b = c
print SumIt still took quite a lot of time (didn't record it) compared to the people who got it done in like 100 milliseconds or something (I got this question on Project Euler).
Is there a way to make it faster?
Here's the link to the problem
https://projecteuler.net/problem=2
Solution
Obviously, every third Fibonacci number is even, and the rest of them are odd. Less obviously (but trivially follows from, say, Binet's formula), they satisfy another linear recurrence:
\$F_{3(n+1)} = 4 F_{3n} + F_{3(n-1)}\$
Using this fact, you may cut the execution time threefold.
\$F_{3(n+1)} = 4 F_{3n} + F_{3(n-1)}\$
Using this fact, you may cut the execution time threefold.
Context
StackExchange Code Review Q#140628, answer score: 5
Revisions (0)
No revisions yet.