Efficient calculation of Fibonacci series

Question

I'm working on a Project Euler problem: the one about the sum of the even Fibonacci numbers.

My code:

def Fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return Fibonacci(n-1) + Fibonacci(n-2)

list1 = [x for x in range(39)]
list2 = [i for i in list1 if Fibonacci(i) % 2 == 0]

The problem's solution can be easily found by printing sum(list2). However, it is taking a lot of time to come up with the list2 I'm guessing. Is there any way to make this faster? Or is it okay even this way...

(the problem: By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.)

Solution 1

Yes. The primitive recursive solution takes a lot of time. The reason for this is that for each number calculated, it needs to calculate all the previous numbers more than once. Take a look at the following image.

It represents calculating Fibonacci(5) with your function. As you can see, it computes the value of Fibonacci(2) three times, and the value of Fibonacci(1) five times. That just gets worse and worse the higher the number you want to compute.

What makes it even worse is that with each fibonacci number you calculate in your list, you don't use the previous numbers you have knowledge of to speed up the computation – you compute each number "from scratch."

There are a few options to make this faster:

---

1. Create a list "from the bottom up"

The easiest way is to just create a list of fibonacci numbers up to the number you want. If you do that, you build "from the bottom up" or so to speak, and you can reuse previous numbers to create the next one. If you have a list of the fibonacci numbers [0, 1, 1, 2, 3], you can use the last two numbers in that list to create the next number.

This approach would look something like this:

>>> def fib_to(n):
...     fibs = [0, 1]
...     for i in range(2, n+1):
...         fibs.append(fibs[-1] + fibs[-2])
...     return fibs
...

Then you can get the first 20 fibonacci numbers by doing

>>> fib_to(20)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

Or you can get the 17th fibonacci number from a list of the first 40 by doing

>>> fib_to(40)[17]
1597

---

2. Memoization (relatively advanced technique)

Another alternative to make it faster exists, but it is a little more complicated as well. Since your problem is that you re-compute values you have already computed, you can instead choose to save the values you have already computed in a dict, and try to get them from that before you recompute them. This is called memoization. It may look something like this:

>>> def fib(n, computed = {0: 0, 1: 1}):
...     if n not in computed:
...         computed[n] = fib(n-1, computed) + fib(n-2, computed)
...     return computed[n]

This allows you to compute big fibonacci numbers in a breeze:

>>> fib(400)
176023680645013966468226945392411250770384383304492191886725992896575345044216019675

This is in fact such a common technique that Python 3 includes a decorator to do this for you. I present to you, automatic memoization!

import functools

@functools.lru_cache(None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

This does pretty much the same thing as the previous function, but with all the computed stuff handled by the lru_cache decorator.

---

3. Just count up (a naïve iterative solution)

A third method, as suggested by Mitch, is to just count up without saving the intermediary values in a list. You could imagine doing

>>> def fib(n):
...     a, b = 0, 1
...     for _ in range(n):
...         a, b = b, a+b
...     return a

---

I don't recommend these last two methods if your goal is to create a list of fibonacci numbers. fib_to(100) is going to be a lot faster than [fib(n) for n in range(101)] because with the latter, you still get the problem of computing each number in the list from scratch.

Solution 2

This is a very fast algorithm and it can find n-th Fibonacci number much faster than simple iterative approach presented in other answers, it is quite advanced though:

def fib(n):
    v1, v2, v3 = 1, 1, 0    # initialise a matrix [[1,1],[1,0]]
    for rec in bin(n)[3:]:  # perform fast exponentiation of the matrix (quickly raise it to the nth power)
        calc = v2*v2
        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
        if rec=='1':    v1, v2, v3 = v1+v2, v1, v2
    return v2

You can read some more about involved math here.

---

Solution 3

Python doesn't optimize tail recursion, thus most solutions presented here will fail with Error: maximum recursion depth exceeded in comparison if n is too big (and by big, I mean 1000).

The recursion limit can be increased, but it will make Python crash on stack overflow in the operating system.

Note the difference in performance between fib_memo / fib_local and fib_lru / fib_local_exc: LRU cache is a lot slower and didn't even complete, because it produces a runtime error already for n = ~500:

import functools
from time import clock
#import sys
#sys.setrecursionlimit()

@functools.lru_cache(None)
def fib_lru(n):
    if n < 2:
        return n
    return fib_lru(n-1) + fib_lru(n-2)

def fib_memo(n, computed = {0: 0, 1: 1}):
    if n not in computed:
        computed[n] = fib_memo(n-1, computed) + fib_memo(n-2, computed)
    return computed[n]

def fib_local(n):
    computed = {0: 0, 1: 1}
    def fib_inner(n):
        if n not in computed:
            computed[n] = fib_inner(n-1) + fib_inner(n-2)
        return computed[n]
    return fib_inner(n)

def fib_local_exc(n):
    computed = {0: 0, 1: 1}
    def fib_inner_x(n):
        try:
            computed[n]
        except KeyError:
            computed[n] = fib_inner_x(n-1) + fib_inner_x(n-2)
        return computed[n]

    return fib_inner_x(n)

def fib_iter(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

def benchmark(n, *args):
    print("-" * 80)
    for func in args:
        print(func.__name__)
        start = clock()
        try:
            ret = func(n)
            #print("Result:", ret)
        except RuntimeError as e:
            print("Error:", e)
        print("Time:", "{:.8f}".format(clock() - start))
        print()

benchmark(500, fib_iter, fib_memo, fib_local, fib_local_exc, fib_lru)

Results:

fib_iter
Time: 0.00008168

fib_memo
Time: 0.00048622

fib_local
Time: 0.00044645

fib_local_exc
Time: 0.00146036

fib_lru
Error: maximum recursion depth exceeded in comparison
Time: 0.00112552

The iterative solution is by far the fastest and does not corrupt the stack even for n=100k (0.162 seconds). It does not return the intermediate Fibonacci numbers indeed.

If you want to compute the nth even Fibonacci number, you could adapt the iterative approach like this:

def fib_even_iter(n):
    a, b = 0, 1
    c = 1
    while c < n:
        a, b = b, a + b
        if a % 2 == 0:
            c += 1
    return a

Or if you are interested in every even number on the way, use a generator:

def fib_even_gen(n):
    a, b = 0, 1
    c = 1
    yield a
    while c < n:
        a, b = b, a + b
        if a % 2 == 0:
            yield a
            c += 1
    return a

for i, f in enumerate(fib_even_gen(100), 1):
    print("{:3d}.  {:d}".format(i, f))

Result:

  1.  0
  2.  2
  3.  8
  4.  34
  5.  144
  6.  610
  7.  2584
  8.  10946
  9.  46368
 10.  196418
 11.  832040
 12.  3524578
 13.  14930352
 14.  63245986
 15.  267914296
 16.  1134903170
 17.  4807526976
 18.  20365011074
 19.  86267571272
 20.  365435296162
 21.  1548008755920
 22.  6557470319842
 23.  27777890035288
 24.  117669030460994
 25.  498454011879264
 26.  2111485077978050
 27.  8944394323791464
 28.  37889062373143906
 29.  160500643816367088
 30.  679891637638612258
 31.  2880067194370816120
 32.  12200160415121876738
 33.  51680708854858323072
 34.  218922995834555169026
 35.  927372692193078999176
 36.  3928413764606871165730
 37.  16641027750620563662096
 38.  70492524767089125814114
 39.  298611126818977066918552
 40.  1264937032042997393488322
 41.  5358359254990966640871840
 42.  22698374052006863956975682
 43.  96151855463018422468774568
 44.  407305795904080553832073954
 45.  1725375039079340637797070384
 46.  7308805952221443105020355490
 47.  30960598847965113057878492344
 48.  131151201344081895336534324866
 49.  555565404224292694404015791808
 50.  2353412818241252672952597492098
 51.  9969216677189303386214405760200
 52.  42230279526998466217810220532898
 53.  178890334785183168257455287891792
 54.  757791618667731139247631372100066
 55.  3210056809456107725247980776292056
 56.  13598018856492162040239554477268290
 57.  57602132235424755886206198685365216
 58.  244006547798191185585064349218729154
 59.  1033628323428189498226463595560281832
 60.  4378519841510949178490918731459856482
 61.  18547707689471986212190138521399707760
 62.  78569350599398894027251472817058687522
 63.  332825110087067562321196029789634457848
 64.  1409869790947669143312035591975596518914
 65.  5972304273877744135569338397692020533504
 66.  25299086886458645685589389182743678652930
 67.  107168651819712326877926895128666735145224
 68.  453973694165307953197296969697410619233826
 69.  1923063428480944139667114773918309212080528
 70.  8146227408089084511865756065370647467555938
 71.  34507973060837282187130139035400899082304280
 72.  146178119651438213260386312206974243796773058
 73.  619220451666590135228675387863297874269396512
 74.  2623059926317798754175087863660165740874359106
 75.  11111460156937785151929026842503960837766832936
 76.  47068900554068939361891195233676009091941690850
 77.  199387062373213542599493807777207997205533596336
 78.  844617150046923109759866426342507997914076076194
 79.  3577855662560905981638959513147239988861837901112
 80.  15156039800290547036315704478931467953361427680642
 81.  64202014863723094126901777428873111802307548623680
 82.  271964099255182923543922814194423915162591622175362
 83.  1152058411884454788302593034206568772452674037325128
 84.  4880197746793002076754294951020699004973287771475874
 85.  20672849399056463095319772838289364792345825123228624
 86.  87571595343018854458033386304178158174356588264390370
 87.  370959230771131880927453318055001997489772178180790104
 88.  1571408518427546378167846658524186148133445300987550786
 89.  6656593304481317393598839952151746590023553382130993248
 90.  28197781736352815952563206467131172508227658829511523778
 91.  119447720249892581203851665820676436622934188700177088360
 92.  505988662735923140767969869749836918999964413630219877218
 93.  2143402371193585144275731144820024112622791843221056597232
 94.  9079598147510263717870894449029933369491131786514446266146
 95.  38461794961234640015759308940939757590587318989278841661816
 96.  162926777992448823780908130212788963731840407743629812913410
 97.  690168906931029935139391829792095612517948949963798093315456
 98.  2923602405716568564338475449381171413803636207598822186175234
 99.  12384578529797304192493293627316781267732493780359086838016392
100.  52461916524905785334311649958648296484733611329035169538240802

Time: 0.00698620

That's the first 100 even Fibonacci numbers in ~7ms and includes the overhead of printing to terminal (easy to underestimate on Windows).

Solution 4

Based on the fact that fib(n) = fib(n-1)+fib(n-2), the straightforward solution is

def fib(n):
    if (n <=1):
        return(1)
    else:
        return(fib(n-1)+fib(n-2))

however, the problem here is that some values are calculated multiple times, and therefore it is very inefficient. The reason can be seen in this sketch:

Essentially, each recursive call to fib function has to compute all the previous fibonacci numbers for its own use. So, the most computed value will be fib(1) since it has to appear in all the leaf nodes of the tree shown by answer of @kqr. The complexity of this algorithm is the number of nodes of the tree, which is $O(2^n)$.

Now a better way is to keep track of two numbers, the current value and the previous value, so each call does not have to compute all the previous values. This is the second algorithm in the sketch, and can be implemented as follows

def fib(n):
   if (n==0):
       return(0,1)
   elif (n==1):
       return(1,1)
   else:
       a,b = fib(n-1)
       return(b,a+b)

The complexity of this algorithm is linear $O(n)$, and some examples will be

>>> fib(1)
(1, 1)
>>> fib(2)
(1, 2)
>>> fib(4)
(3, 5)
>>> fib(6)
(8, 13)

Solution 5

import time


def calculate_fibonacci_1(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return calculate_fibonacci_1(n - 1) + calculate_fibonacci_1(n - 2)


def calculate_fibonacci_2(n):
    fib = [0] * n
    fib[0] = 1
    fib[1] = 1
    for i in range(2, n):
        fib[i] = fib[i - 1] + fib[i - 2]
    return fib[n-1]


def calculate_fibonacci_3(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


def calculate_fibonacci_4(n):
    v1, v2, v3 = 1, 1, 0
    for rec in bin(n)[3:]:
        calc = v2*v2
        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
        if rec == '1':
            v1, v2, v3 = v1+v2, v1, v2
    return v2


def calculate_fibonacci_5(n):
    if n == 0:
        return (0, 1)
    else:
        a, b = calculate_fibonacci_5(n // 2)
        c = a * (b * 2 - a)
        d = a * a + b * b
        if n % 2 == 0:
            return (c, d)
        else:
            return (d, c + d)

    n = 30

    start = time.time()
    calculate_fibonacci_1(n)
    end = time.time()
    print(end - start)

    start = time.time()
    calculate_fibonacci_2(n)
    end = time.time()
    print(end - start)

    start = time.time()
    calculate_fibonacci_3(n)
    end = time.time()
    print(end - start)

    start = time.time()
    calculate_fibonacci_4(n)
    end = time.time()
    print(end - start)

    start = time.time()
    calculate_fibonacci_5(n)
    end = time.time()
    print(end - start)

for n=30:

0.264876127243
6.19888305664e-06
8.10623168945e-06
7.15255737305e-06
4.05311584473e-06

for n=300:

>10s
3.19480895996e-05
1.78813934326e-05
7.15255737305e-06
6.19888305664e-06

for n=3000:

>10s
0.000766038894653
0.000277996063232
1.78813934326e-05
1.28746032715e-05

for n=30000:

>10s
0.0550990104675
0.0153529644012
0.000290870666504
0.000216007232666

for n=300000:

>10s
3.35211610794
0.979753017426
0.012097120285
0.00845909118652

for n=3000000:

>10s
>10s
>10s
0.466345071793
0.355515003204

for n=30000000:

>100s
>100s
>100s
16.4943139553
12.6505448818

disclaimer: codes of functions no. 4 and 5 were not written by me

View more solutions

Comments

[Mitch Wheat]

which is why I suggested the poster look at the wiki page for Fibonacci numbers

[Esailija]

Recursively expressing something does not make it automatically easier to understand

[kqr]

In case you are referring to tail-call optimisation when you say "optimize right recursive code" – that's not a possible optimisation to do here, since you recurse down two branches. If it would be possible at all, you would be able to emulate it in Python using a keyword argument.

[ChrisProsser]

@Esailija I agree that it doesn't automatically make it easier to understand, but you can often express it more succinctly and in a very similar way to a the way you would see the formula shown e.g. fibonacci formula is F_n = F_{n-1} + F_{n-2} with seed values F_0 = 0, F_1 = 1. The program suggested by the OP is almost identical.

[Paulo Bu]

@kqr: I see, so this kind of optimization can't be done in functional languages?

[kqr]

Not when computing fibonacci numbers using this method, no. The computer needs to keep each frame in the stack to be able to perform the addition.

[ChrisProsser]

@MitchWheat It may be helpful if you provide link. I tried searching and found this page: stackoverflow.com/tags/fibonacci/info which doesn't seem to say anything not covered by the OP.

[Mitch Wheat]

@ChrisProsser: I'm assuming even a new user can use a search engine.

[will]

If you change the function at the end coming from mitch to a generator instead, it'll be even better, as you won't be recalculating the numbers each time. just change return to yield and move it into the for loop.

[kqr]

@will wouldn't it basically become the first function by then? (Except that you can only take a value once out of it, and you can't index it.)

[user65165]

Awesome reply! Thank you very much. I learned a lot of new stuff as well :D

[Paulo Bu]

@kqr: Thanks, I'll remove that recommendation from the answer to prevent further misleading.

[will]

@kqr yah. It would be the same, but without requiring they all be stored. If you wanted to index it, then you'd just need to do list(fib(N)). Probably at a small performance hit though. I didn't read the whole answer. I'm hungover.

[wim]

Very nice comprehensive answer. Using mutable default argument for a memo is one of my favourite python tricks. You could also mention the closed-form expression for fib numbers.

[Bonifacio2]

Could you write a small explanation on what your code is doing?

[previous_developer]

Where can I find a mathematical explanation source for first method?

[Piotr Dabkowski]

You can read about involved math here: en.wikipedia.org/wiki/Fibonacci_number#Matrix_form. My algorithm uses fast exponentiation to raise the matrix to the nth power.

[Ali Arda Orhan]

It's too cryptic to understand. I don't recommend the solution for fresh-starters.

[CodeManX]

A solution to compute the first nth even Fibonacci numbers using a generator is missing from this comprehensive answer however. You can find an implementation in my answer below. @kqr: Any idea why LRU cache decorator is a lot slower than a hand-crafted memoized solution?

[kqr]

@CoDEmanX Boring answer: The hand-crafted cache is specialised for the task and therefore performs better by being able to completely ignore a lot of edge cases. The decorator is supposed to do the right thing for any function call with any set of parameters, which eats cycles. Interesting answer: knock yourself out: fossies.org/dox/Python-3.4.3/functools_8py_source.html#l0043‌​8

[greybeard]

Answering what? Try to understand the question, check whether the answer you're tempted to give is already there - or in one of the "duplicate"s.

[Abx]

@greybeard Its just an additional info that wont harm anyone.It might not help you but it would certainly help others who seek it.

[greybeard]

+1 for introducing [generator] to this question. (You can generate the even-valued terms directly using a, b = 0, 2 and a, b = b, a + 4*b.)

[leitasat]

Is it faster than the plain closed form? en.wikipedia.org/wiki/Fibonacci_number#Computation_by_roundi‌​ng

[Hubert Kario]

@leitasat probably, but will also be incorrect for large values of n as python floats are limited precision, unlike the ints

[Alexandros Spyropoulos]

memoization would return in large sets in fib computed[n] = fib(n-1, computed) + fib(n-2, computed) [Previous line repeated 995 more times] RecursionError: maximum recursion depth exceeded

[Victor Castro]

I made a simple example using Ruby instead (n - 1).times.reduce([0, 1]) { |array| [array[1], array[0] + array[1]] }.last

[Manoel Vilela]

And unfortunatelly even using tail-call this doesn't solve, @AlexandrosSpyropoulos. Just because Guido, the creator of Python, don't like the idea of Tail Call Optimization... err. Well, +1 for the answer using the functools.lru_cache. Really great

[CodeManX]

@greybeard: Thanks, that makes quite a difference for n = 100k (12.5s vs. 0.6s with printing to console disabled).

[Him]

There is a closed-form formula for Fibonacci numbers. Why on earth would one use something else?

[greybeard]

How does this make [finding] the sum of the even-valued terms not [exceeding] four million fast?

[anthony sottile]

the question however is tagged [python]

[qwr]

This is by far the fastest method. It may be even faster to use n % 2, n //= 2 for rec instead of the string operation bin.

[greybeard]

What question does this answer?

[dan-klasson]

@greybeard "Is there any way to make this faster?"

[Prokhozhii]

getFib(10000) OverflowError: complex exponentiation

[Prokhozhii]

fib(10000) OverflowError: (34, 'Result too large')

[Prokhozhii]

You may check by yourself I guess.

[rocksNwaves]

@Scott, I'm late to the party, but I found a reason for not using the closed form as I was working on Project Euler #25: Find the index of the first fibonacci number whose length is 1000 digits. I tried the closed form first, but it causes overflow errors because it deals with floats (I think). Perhaps there is a way to cleverly type cast your calculations back to int, but this solution was so fast, why would I care?

[Him]

@rocksNwaves did you use the solution in my answer below? It should handle arbitrarily large numbers, in python at least (which allows arbitrarily large ints)

[rocksNwaves]

Hi @Scott, I ended up using this "memoization" technique. I chose it mostly because I have a hard time thinking recursively, so this was good practice for me. I see you have two answers below, did you have a preference between the two?

[Him]

@rocksNwaves, one computes the nth fibo in O(1) time. The other computes the sum of the first n fibos in O(1) time.

[sidgeon smythe]

This is not "essentially constant time"; the exponentiation (your rootipower function) does ~lg n arithmetic operations, and the output itself has ~n digits so no algorithm can be sub-linear (see the answer by yairchu here)

[egyik]

Let's clarify the intent of the sumOfEvenFibonacciNumbersUpTo function. The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8 etc. This function is meant to return (for example) 0, 0, 2, 2, 2, 2, 2, 2, 10, 10, 10 for inclusiveLimit inputs from 0 to 10 i.e. it does what it says it does. In particular it doesn't print the Fibonacci sequence like most answers do. It directly does what the OP asked for i.e. calculates the sum of the even elements of the sequence less than or equal to the limit parameter. A small amount of maths is required to prove it works.

[egyik]

I'm sad someone downvoted this answer. It is making me question my appetite for bothering to share information here.

[anantdark]

Hey, i used the automated memoization and the bottom up method. I found the bottom up method to be more fast. I used the time module to calculate the speed of both the methods.

[Piotr Dabkowski]

math.pow(x, N) is not O(1), O(log(N)) at best.

[Bastian Venthur]

Care to explain?

[Piotr Dabkowski]

The complexity is O(1) if and only if the program completes in ~the same amount of CPU cycles regardless of the input. math.pow(2, N) is not a single CPU instruction, it translates to tons of multiplications (log(N)) if fast exponentiation is used. The multiplication of integers in python is also not constant time - they can be arbitrary size (eg 1024 bit) so you need multiple CPU instructions to multiply large integers. However, in your case you use floats and these are constant 64bit so the complexity would be O(log(N)). Note the result you get from this is just a float approximation.

[greybeard]

you defined a function but it would be best to use a while loop neither rules out the other.

[greybeard]

What question does this answer? I don't see solve Project Euler Problem 2 fast.

[greybeard]

What question does this answer? I don't quite see solve Project Euler Problem 2 fast.

[greybeard]

If anyone wants to watch this working, add print(even, next, sum) to the loop.

[greybeard]

(If you explained how/why this works, someone might award a bounty.)

[greybeard]

Far as computing one Fibonacci number goes, I find the take of kqr in method 3(2015) (repeated by dan-klasson in 2018) nicer, if deplorably undocumented.

[ranjith chilupuri]

@greybeard, I meant the function defined in the question is not ideal and it would be best to use a while loop, As in the question it was a recursion.(and again recursions vs loops depends on the language) And the question also needs to make list of even valued Fibonacci number and sum it up I don't think the answer (repeated by dan-klasson in 2018) fits the situation. I am still working on writing answers and thanks for your honest opinion on that.

[Prashanth]

This seems to only be an approximate solution. For example the result of fib(1000) is wrong.

[PatrickT]

No it's not typically O(1) time, because you have gigantic powers of floats to be computed. You can see that easily if you try to calculate the Fibonacci numbers using the Binet formula, a pencil, and lots of paper!

[CogitoErgoCogitoSum]

In Python3, the discrepancy occurs at n=72 and higher. This is a good implementation as a "base case" for the conditional n<=71, and larger n can be calculated recursively. You could use this code to get larger fibonacci numbers if you use the decimal package to improve floating point precision.

[CogitoErgoCogitoSum]

My algorithm can achieve at least Fib(100 million) without error.

[greybeard]

This adds a sidestep to "halving/doubling" approaches I guess about three times as fast for computing just one smaller value and taking a bigger step.

[greybeard]

I wish you'd keep prime testing out - I suggest that you post a separate (cross-linked) self-answered question (I'm not into answer seeking a question any more than into solution in dire need of a problem).

[CogitoErgoCogitoSum]

I included the primality test because it IS a common problem, and large primes require large fibos, which this algorithm is capable of generating. It is a side note, admittedly. But what other reason would anyone have to generate fibos this large? As for the criticism that you only see syntax or other superficial changes, you clearly havent ran the code or observed performance, and you clearly dont care about my claims enough to consider them valid enough to test. You really dont think an algorithm capable of generating fib(100 million) competes in this arena?

[greybeard]

I noticed en.wikipedia digresses to primality testing on the Fibonacci number page, too.

[greybeard]

Most everything has been done before, if not yet by everyone in every language.

[CogitoErgoCogitoSum]

Right... so you dont believe innovation is a thing then, huh? Okay. I never claimed to be the originator of the algorithm. In fact I made it clear that I got it from wikipedia in my second paragraph. Did you read anything I wrote? What I do get credit for is being the first person on THIS page to contribute THIS algorithm to THIS conversation, so that other people can find it and learn from it. Do you really need a community-driven wikipedia to set a standard for you here? Any more naysaying? Why does every Q or A on SO have to be defended? youtube.com/watch?v=IbDAmvUwo5c

[greybeard]

([greybeard] doesnt believe innovation is a thing on the contrary: I believe in discovery and innovation as firmly as in apostrophes. It was a thing when Fibonacci wrote about that sequence, if it had been done hundreds of years before. What naysaying? I'm the one who up-voted - and have a look at comments I left with other contributions to this question&answers. And, of course, the posts themselves: upvote what you think useful (beyond current voting); consider down-voting what you think detrimental. (This is not conversation/thread - this is neither usenet nor a chat room)).

[greybeard]

tell me what you think. I[…]can't find a way in my limited (programming) knowledge to improve it What improvements I see waiting are in the way the solution is denoted.

[TryingHardToBecomeAGoodPrSlvr]

Also, this formula, when used in Python3, returns incorrect results past n = 71 (correct answer = 308061521170129, result from the code: 308061521170130).

[revo]

sqrt of 5 is an irrational number and calculating that has limits. Although this is O(1), it wouldn't be precise on calculating big numbers of fibo. Hence matrix exponentiation is the better alternative.

[Him]

@revo this does not actually compute sqrt(5). It's only present algebraically. At the end, all of the sqrt(5)'s cancel out or multiply into 5s which are precise.

[Him]

@revo to be clear, this solution involves no floating point arithmetic whatsoever.

[Him]

Also, the number of operations in this solution is constant, but the length of the number is linear in $n$, so once you move significantly past the size of your processor registers, there is no sub-linear algorithm.

[greybeard]

How does this find the sum of the even-valued [Fibonacci numbers not exceeding four million]?

[greybeard]

How does this find the sum of the even-valued [Fibonacci numbers not exceeding four million]?

[greybeard]

How does this find the sum of the even-valued [Fibonacci numbers not exceeding four million]?

[greybeard]

How does this find the sum of the even-valued [Fibonacci numbers not exceeding four million]?

[greybeard]

How does this find the sum of the even-valued [Fibonacci numbers not exceeding four million]?

[greybeard]

How does this find the sum of the even-valued [Fibonacci numbers not exceeding four million]?

[Bastian Venthur]

@PiotrDabkowski well, If I look a the runtimes for n = 0..1500 the timings seem pretty constant to me. All in the range of 2.5e-06 seconds. Definitely not O(log(n)). Regarding the correctness of the result, please check the Wikipedia article I've linked.

[Piotr Dabkowski]

@BastianVenthur Just run 'a = pow(2, 10000000000000)' and see for yourself :) The runtime of pow(2, N) is not independent of N, clearly.

[Piotr Dabkowski]

And btw for your "constant" result, it seems there is a large constant factor in the pow, so the O(log(n)) behavior will not be visible until N is large.

[mercury0114]

An even faster method is to identify that the n-th fibonacci number is equal to the n-th power of a golden ratio (a sum of two n-th powers to be presice), and you can perform a logarithmic algorithm to compute the n-th power.

[Skillmon]

Tiny improvement: Only calculate calc+v3*v3 in an else to rec=='1'