Implementing alternative Fibonacci sequence

Question

So I'm struggling with Question 3. I think the representation of L would be a function that goes something like this:

import numpy as np
def L(a,  b):
    #L is 2x2 Matrix, that is 
    return(np.dot([[0,1],[1,1]],[a,b]))


def fibPow(n):
    if(n==1):
        return(L(0,1))
    if(n%2==0):
        return np.dot(fibPow(n/2), fibPow(n/2))
    else:
        return np.dot(L(0,1),np.dot(fibPow(n//2), fibPow(n//2)))

Given b I'm pretty sure I'm wrong. What should I be doing? Any help would be appreciated. I don't think I'm supposed to use the golden ratio property of the Fibonacci series. What should my a and b be?

EDIT: I've updated my code. For some reason it doesn't work. L will give me the right answer, but my exponentiation seems to be wrong. Can someone tell me what I'm doing wrong

The question isn't clear enough, can you attach an image of the full question? — Shay Yzhakov
– Shay Yzhakov, Commented Sep 29, 2020 at 22:56
Although in this case it's clear enough, f is nowhere defined in that image. — user202729
– user202729, Commented Sep 29, 2020 at 23:38

user58697 · Accepted Answer · 2020-09-30 16:28:18Z

1

With an edited code, you are almost there. Just don't cram everything into one function. That leads to subtle mistakes, which I think you may enjoy to find.

Now, L is not function. As I said before, it is a matrix. And the core of the problem is to compute its nth power. Consider

L = [[0,1], [1,1]]

def nth_power(matrix, n):
    if n == 1:
        return matrix
    if (n % 2) == 0:
        temp = nth_power(matrix, n/2)
        return np.dot(temp, temp)
    else:
        temp = nth_power(matrix, n // 2)
        return np.dot(matrix, np.dot(temp, temp))

def fibPow(n):
    Ln = nth_power(L, n)
    return np.dot(L, [0,1])[1]

The nth_power is almost identical to your approach, with some trivial optimization. You may optimize it further by eliminating recursion.

answered Sep 30, 2020 at 16:28

user58697

8,0481 gold badge16 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user58697 Over a year ago

@pasha Think about the dimensionality. In your implementation the base case of fibPow returns a vector (1x2). The np.dot of two such vectors returns a scalar.

user58697 · Accepted Answer · 2020-09-29 23:37:05Z

1

First thing first, there is no L(n, a, b). There is just L(a, b), a well defined linear operator which transforms a vector a, b into a vector b, a+b.

Now a huge hint: a linear operator is a matrix (in this case, 2x2, and very simple). Can you spell it out?

Now, applying this matrix n times in a row to an initial vector (in this case, 0, 1), by matrix magic is equivalent to applying nth power of L once to the initial vector. This is what Question 2 is about.

Once you determine how this matrix looks like, fibPow reduces to computing its nth power, and multiplying the result by 0, 1. To get O(log n) complexity, check out exponentiation by squaring.

edited Sep 29, 2020 at 23:37

answered Sep 29, 2020 at 23:25

user58697

8,0481 gold badge16 silver badges30 bronze badges

2 Comments

pasha Over a year ago

That matrix thing was what I missed. Thank you so much.

pasha Over a year ago

Hey I updated the question. Do you think you could tell me what I'm doing wrong

Collectives™ on Stack Overflow

Implementing alternative Fibonacci sequence

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related