Algorithm for k-Fibonacci
https://stackoverflow.com/questions/4122291
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
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),
Solution
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, ...
OTHER TIPS
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).
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)]
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)
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]
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;
}
}
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.
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.
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.
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]+" ");
}
