14

We all know fibonacci series, when k = 2.

I.e.: 1,1,2,3,5,8,13

But this is the 2-fibonacci. Like this, I can count the third-fibonacci:

1,1,2,4,7,13,24

And the 4-fibonacci:

1,1,2,4,8,15,29

...and so goes on

What I'm asking is an algorithm to calculate an 'n' element inside a k-fibonacci series.

Like this: if I ask for fibonacci(n=5,k=4), the result should be: 8, i.e. the fifth element inside the 4-fibonacci series.

I didn't found it anywhere web. A resouce to help could be mathworld

Anyone? And if you know python, I prefer. But if not, any language or algorithm can help.

Tip I think that can help: Let's analyze the k-fibonacci series, where k will go from 1 to 5

k    fibonacci series

1    1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, ...
2    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
3    1, 1, 2, 4, 7, 13, 24, 44, 81, ...
4    1, 1, 2, 4, 8, 15, 29, 56, 108, ...
5    1, 1, 2, 4, 8, 16, 31, 61, 120, ...

Analyzing this, we can see that the array [0:k] on the k-fibonacci series is equal to the previous fibonacci series, and it goes on till the k=1

i.e. (I'll try to show, but I'm not finding the right way to say it):

k    fibonacci series

1    1, 
2    1, 1, 
3    1, 1, 2, 
4    1, 1, 2, 4, 
5    1, 1, 2, 4, 8,

Hope I've helped somehow to solve this.

[SOLUTION in python (if anyone needs)]

class Fibonacci:

    def __init__(self, k):
        self.cache = []
        self.k = k

        #Bootstrap the cache
        self.cache.append(1)
        for i in range(1,k+1):
            self.cache.append(1 << (i-1))

    def fib(self, n):
        #Extend cache until it includes value for n.
        #(If we've already computed a value for n, we won't loop at all.)
        for i in range(len(self.cache), n+1):
            self.cache.append(2 * self.cache[i-1] - self.cache[i-self.k-1])

        return self.cache[n]


#example for k = 5
if __name__ == '__main__':
    k = 5
    f = Fibonacci(k)
    for i in range(10):
        print f.fib(i),
Improve this question
4
  • @Amber, @Itay: thanks for tips. Any algorithm to solve this? I'm really lost on this problem. Commented Nov 8, 2010 at 8:51
  • @ Gabriel - Not really sure what you mean by algorithm? The computation of fibonacci numbers is not really complex... Commented Nov 8, 2010 at 8:56
  • I found some paper about it THE GENERALIZED BINET FORMULA. Posted the link in my answer. Commented Nov 8, 2010 at 8:58
  • 1
    Old question, but I believe my new answer contributes something new. Commented Jan 3, 2018 at 11:17

10 Answers 10

Reset to default
9

As with 2-fibonacci, dynamic programming is the way to go. Memoize the values of earlier ks to quickly compute the later ones, in O(n) time.

Another optimization that you can use to improve speed for large values of k is instead adding f(n-k) through f(n-1) to get f(n), instead just use (2*f(n-1)) - f(n-k-1). Since this only uses 2 lookups, 2 adds, and a multiply, it's vastly superior to k lookups and k adds when k becomes large (but it's still O(n), just a smaller constant multiplier).

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

Comments

7

Here is an iterative solution building on Ambers answer:

class Fibonacci {

    List<Integer> cache = new ArrayList<Integer>();
    final int K;

    public Fibonacci(int k) {
        this.K = k;

        // Bootstrap the cache
        cache.add(1);
        for (int i = 1; i <= k; i++)
            cache.add(1 << (i-1));
    }

    public long fib(int n) {

        // Extend cache until it includes value for n.
        // (If we've already computed a value for n, we won't loop at all.)
        for (int i = cache.size(); i <= n; i++)
            cache.add(2 * cache.get(i-1) - cache.get(i-K-1));

        // Return cached value.
        return cache.get(n);
    }
}

A test looks like this:

public class Main {
    public static void main(String[] args) {
        System.out.println("k     fibonacci series");

        for (int k = 1; k <= 5; k++) {
            System.out.print(k + "     ");

            Fibonacci f = new Fibonacci(k);
            for (int i = 0; i < 10; i++)
                System.out.print(f.fib(i) + ", ");
            System.out.println("...");

        }
    }
}

And prints

k     fibonacci series
1     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
2     1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
3     1, 1, 2, 4, 7, 13, 24, 44, 81, 149, ...
4     1, 1, 2, 4, 8, 15, 29, 56, 108, 208, ...
5     1, 1, 2, 4, 8, 16, 31, 61, 120, 236, ...
Improve this answer

3 Comments

Note that due to implementation via recursion, this may run into (ironic for the site) stack overflow errors for large values of n (or in certain languages, 'maximum recursion depth' errors).
@Amber, much nicer now. Good idea with the (2*f(n-1)) - f(n-k-1) suggestion.
@Amber, @gwylim, @MAK, @Itay: Thank you all for answers. I took the algorithm implemented in java and transformed in python. I'll edit my question to post the code, so that if anyone else needs it's right there. Thank you all, very much.
6

If you just want to solve for one value (i.e. fibonnaci(n,k)), then a more efficient way is to use a linear recurrence, which will be O(k^3 log(n)) (the k^3 factor can be improved with a better matrix multiplication algorithm).

Basically, the way this works is that you express the vector F(n), F(n-1) ... F(n-k) as matrix times the vector F(n-1), F(n-2) ... F(n-k-1). Then since matrix multiplication is associative, you can raise the matrix to a power, and multiply this by an initial vector F(k), F(k-1) ... F(0).

Exponentiation can be done in O(log(n)) using exponentiation by squaring.

For example, for the k=3 case, we will have:

[F(n+2)]   [1 1 1] [F(n+1)]
[F(n+1)] = [1 0 0] [F(n)  ]
[F(n)  ]   [0 1 0] [F(n-1)]

so to solve for F(n), you just find

[F(n+2)]   [1 1 1]^n [F(2)]
[F(n+1)] = [1 0 0]   [F(1)]
[F(n)  ]   [0 1 0]   [F(0)]
Improve this answer

Comments

3

The straightforward way is to simply add up the last k terms to get the current term every time. This gives us a O(n*k) runtime.

Another way would be to use matrix exponentiation. For k=2, you can model the situation using a matrix. From (Fn-1, Fn-2) we can derive (Fn, Fn-1) by computing (Fn-1+Fn-2,Fn-1).

Thus, multiplying the coloumn matrix 

[
Fn-1
Fn-2
]

with the square matrix

[
1 1
1 0
]

yields 

[
Fn-1 + Fn-2
Fn-1
]

thereby giving us the value of Fn.

Of course, this isn't really any better than O(n*k) yet. We would still be running a O(n) loop/recursion to get the n-th term.

Observe that (I am writing coloumn vectors horizontally for convenience now, but they are still coloumns)

[[Fn],[Fn-1]] = [[Fn-1],[Fn-2]]*[[1,1] [1,0]]
              = [[Fn-2],[Fn-3]]*[[1,1] [1,0]]*[[1,1] [1,0]]
              = [[Fn-3],[Fn-4]]*[[1,1] [1,0]]*[[1,1] [1,0]]*[[1,1] [1,0]]
              = [[Fn-3],[Fn-4]]*([[1,1] [1,0]])^3
              = [[Fn-k],[Fn-k-1]]*([[1,1] [1,0]])^k
              = [[F1],[F0]]*([[1,1] [1,0]])^n-1

Now, ([[1,1] [1,0]])^n-1 can be computed in O(log(n)) time using exponentiation by squaring. Thus, you can compute the n-th term of k-fibonacci using at most log(n) matrix multiplications. Using straightforward matrix multiplication, this gives us a complexity of O(k^3*log(n)).

Edit:

Here's some code in Python I hacked together to illustrate what I'm saying better:

from itertools import izip

def expo(matrix,power, identity):
    if power==0:
        return identity
    elif power==1:
        return matrix
    elif power&1:
        return multiply(matrix,expo(matrix,power-1,identity))
    else:
        x=expo(matrix,power>>1,identity)
        return multiply(x,x)

def multiply(A,B):
    ret=[list() for i in xrange(len(B))]
    for i,row in enumerate(B):
        for j in xrange(len(A[0])):
            coloumn=(r[j] for r in A)
            ret[i].append(vector_multiply(row,coloumn))
    return ret

def vector_multiply(X,Y):
    return sum(a*b for (a,b) in izip(X,Y))

def fibonacci(n,start=[[1],[0]], k=2):
    identity=[[1 if col==row else 0 for col in xrange(k)] for row in xrange(k)] # identity matrix
    # build the matrix for k
    matrix=[[1]*k]
    for i in xrange(1,k):
        matrix.append([0]*(i-1)+[1]+[0]*(k-i))
    return multiply(start,expo(matrix,n-1,identity))[0][0]

print fibonacci(10)
Improve this answer

2 Comments

You're matrix multiplication is the wrong way around and matrix multiplication takes atleast O(k^2.3) (this is the best known algorithm), the naive one takes O(k^3). So the complexity is higher than O(k^2*log(n))
@JPvdMerwe: Thanks. Corrected my answer.
1

For the exercise of it, I implemented this in Haskell. Here is how fib is ordinarily written as a list comprehension:

fib = 1:1:[x + y | (x,y) <- zip fib $ tail fib]

Generalizing to 'k' terms is difficult because the zip requires two arguments. There is a zip3, zip4, etc. but no general zipn. However we can do away with the technique of creating pairs, and instead generate "all tails of the sequence", and sum the first k members of those. Here is how that looks for the k=2 case:

fib2 = 1:1:[sum $ take 2 x | x <- tails fib2]

Generalizing to any k:

fibk k = fibk'
  where fibk' = take (k - 1) (repeat 0) ++ (1:[sum $ take k x | x <- tails fibk'])


> take 10 $ fibk 2
[0,1,1,2,3,5,8,13,21,34]

> take 10 $ fibk 3
[0,0,1,1,2,4,7,13,24,44]

> take 10 $ fibk 4
[0,0,0,1,1,2,4,8,15,29]
Improve this answer

Comments

1

Another log(n) solution below.
Source and explanation here.
You could cache the solutions if a lot of calls are made.

public class Main {
    /* 
     * F(2n) = F(n) * (2*F(n+1) - F(n))
     * F(2n+1) = F(n+1)^2 + F(n)^2
     * Compute up to n = 92, due to long limitation<br>
     * Use different type for larger numbers
     */
    public static long getNthFibonacci(int n) {
        long a = 0;
        long b = 1;
        for (int i = 31 - Integer.numberOfLeadingZeros(n); i >= 0; i--) {

            long d = a * ((b << 1) - a); // F(2n)
            long e = a * a + b * b; // F(2n+1)
            a = d;
            b = e;

            if (((1 << i) & n) != 0) { // advance by one
                long c = a + b;
                a = b;
                b = c;
            }
        }
        return a;
    }
}
Improve this answer

Comments

1

People have already mentioned O(logN) solutions. Not many people understand how the constants in the matrix that is exponentiated came into being. If you want a detailed analysis of how to use matrices to solve linear recurrences, have a look at Code Overflow.

Improve this answer

Comments

1

Here's an efficient, terse and exact closed form solution.

def fibk(n, k):
    A = 2**(n+k+1)
    M = A**k - A**k // (A - 1)
    return pow(A, n+k, M) % A

for k in xrange(1, 10):
    print ', '.join(str(fibk(n, k)) for n in xrange(15))

Here's the output:

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610
1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136
1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536
1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930
1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617
1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936
1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080
1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144

The method is effectively computing X^(n+k) in the polynomial ring Z[X]/(X^k-X^(k-1)-X^(k-2)-...-1) (where the result of the constant term in the final polynomial is somewhat surprisingly fibk(n, k)), but using a large enough integer A instead of X to perform the calculation in the integers.

Improve this answer

Comments

0

I guess that you need something that is better than O(nk).
For O(nk), you can just compute it naively.
In case that you have an upper bound on n <= N and k <= K, you can also build a matrix NxK once and query it anytime you need the value.

EDIT
If you want to dig further into math, you can try to read this paper on Generalized Order-k Pell Numbers.

Improve this answer

3 Comments

Note that some "naive" calculations are more naive than others. A truly naive computation of a Fibonacci number is more like O(N!) (if it uses recursive calculation without memoization).
@Amber - I meant for the less naive one :)
@Itay: Your link is dead. Here is the author's publication list. Lots of useful articles to this topic: ekilic.etu.edu.tr/Publications.htm
0

simple brute-force solution 

    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int k = scanner.nextInt();
    long formula ;
    formula = k ;


    long[] fib = new long[n+1];

    for (int i = 1; i <=n ; i++) {
        if(i<=k) fib[i]  = 1;
        else {
            fib[i] = formula;
            formula =(formula*2-fib[i-k]);
        }
    }


    for (int i = 1; i <=fib.length-1 ; i++) {
        System.out.print(fib[i]+" ");
    }
Improve this answer

2 Comments

solution in a formalism not worth mentioning. While I see (formula*2-fib[i-k]) as a valid addition to the answers existing at the time of adding this: what magic makes 1000000007 rear its ugly head?
sorry for that typo

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.