6
\$\begingroup\$

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

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 Sum

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

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! It is encouraged to put the name of the what code does into the title, not what you want. Currently it could be "Sum of even Fibonacci numbers". Additionally, it would be great if you put the problem statement into the body of the post, as well as link to it. \$\endgroup\$ – Incomputable Sep 6 '16 at 12:01
  • \$\begingroup\$ Is this your full code? It takes around 46ms on my pc to finish. \$\endgroup\$ – ChatterOne Sep 6 '16 at 12:14
  • \$\begingroup\$ Yes. That's the whole code. Also, I have a feeling the time problem is coming because of some other factor and not because the code is bad. In any case, any suggestions on improving this code is appreciated. \$\endgroup\$ – Cubestormer Iv Sep 6 '16 at 12:18
5
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

You should adhere to the recommendations of pythons official style-guide, PEP8. This means using lower_case for variable (and function) names. CamelCase is recommended for classes only.

At the same time it recommends using a leading _ if you would otherwise shadow a built-in variable. So I would use _sum or even better the more descriptive even_sum instead of Sum.

It also recommends putting spaces around operators.


You could use python's tuple assignment to shorten your code a bit:

a, b, c = b, c, a+b

Final code:

I used fn for \$f_n\$ (the current fibonacci number), fn_1 for \$f_{n-1}\$ and fn_2 for \$f_{n-2}\$.

I put the code into a function to allow reusability.

def even_fib_sum(limit=4000000):
    fn_2, fn_1, fn = 1, 1, 0
    even_sum = 0
    while fn < limit:
        fn_2, fn_1, fn = fn_1, fn, fn_1 + fn_2
        if fn%2 == 0:
            even_sum += fn
    return even_sum

print even_fib_sum()
\$\endgroup\$
1
\$\begingroup\$

The Fibonacci sequence grows fast enough that it exceeds 4 000 000 with its 34th term, as shown on the OEIS.

Given this fact, hardcoding the set of even Fibonacci numbers under 4 000 000 - or even their sum - would be far from impractical and would be an obvious solution to drastically increase execution time.

\$\endgroup\$
  • \$\begingroup\$ It's true that it would be faster, but it kinda defeats the spirit of the challenge. By the same logic, you could just do a print 4613732 and be done with it. \$\endgroup\$ – ChatterOne Sep 6 '16 at 13:30
  • \$\begingroup\$ Of course it does, and I surely don't advocate it. However, pre-computing (parts of) solutions is a great way to speed computation in a general case when the set of possible parameters is not too large (here, it's empty). So I think that not only it might explain the fastest answers referenced on ProjectEuler from people which might not have your concerns, but it's also a valid solution to generic "time-limit-exceeded" problems. \$\endgroup\$ – Aaron Sep 6 '16 at 13:36
1
\$\begingroup\$

Firstly, we can observe that the sum of Fibonacci numbers is simply offset from a Fibonacci number. I'll take the convention that \$F_0 = 0\$, \$F_1 = 1\$. Then $$\sum_{i=0}^n F_i = F_{n+2} - 1$$ Proof by induction is easy: \$\sum_{i=0}^{n+1} F_i = F_{n+1} + \sum_{i=0}^n F_i = F_{n+1} + F_{n+2} - 1 = F_{n+3}-1\$.

Secondly, we can observe that since the Fibonacci numbers go odd, odd, even, the sum of the first \$n\$ even Fibonacci numbers is the sum of the first \$2n\$ odd Fibonacci numbers, and half the sum of the first \$3n\$ Fibonacci numbers. I.e. $$\sum_{i=1}^n F_{3n} = \frac{F_{3n+2} - 1}2$$

So you can skip the sum provided that you can compute how many terms you need. And you can compute the \$n\$th Fibonacci number in \$O(\lg n)\$ operations using \$F_{m+n} = F_{m+1} F_n + F_m F_{n-1}\$.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.