Generalised Fibonacci

Question

How to find the nth term of the recurrence in log(n) time.

F[n]=F[n-1]+F[n-3]
F[2]=1;
F[3]=2;
F[4]=3;
F[5]=4;

I could not create the required matrix to exponentiate. Sorry if this seems somewhat off-topic.

Thanks but i found the answer. https://math.stackexchange.com/questions/891964/generalised-fibonacci/891979#891979

It looks like http://stackoverflow.com/questions/30595844/java-8-lambda-expressions-for-solving-fibonacci-non-recursive-way/30632678#30632678 — Rodolfo, Jul 02 '15 at 00:58

score 0 · Answer 1 · edited May 23 '17 at 12:25

0

The nth fibnonacci number is given by:

f(n) = Floor(phi^n / sqrt(5) + 1/2)

where

phi = (1 + sqrt(5)) / 2

Assuming that the primitive mathematical operations (+, -, * and /) are O(1) you can use this result to compute the nth Fibonacci number in O(log n) time (O(log n) because of the exponentiation in the formula).

With reference to: nth fibonacci number in sublinear time

edited May 23 '17 at 12:25

Community

1
1

answered Aug 09 '14 at 12:07

lakshmen

28,346
66
178
276

I wasn't doing for fibonacci series.. but something similar. thanks anyway. also i dont think your answer always gives accurate results for higher values of n. – user3908641 Aug 09 '14 at 12:27

Generalised Fibonacci

1 Answers1