what is the method that takes the shortest computational time to find the nth term of a fibonacci series?

Answer 1

Binet's formula is correct but inconvenient, and z_o_r_r_o is simply wrong.

It is fastest to calculate in pairs, instead of singly.

not only is (F16, F17) is easily obtained from (F15, F16) by the definition of Fibonacci numbers

but, brilliantly,

(F15, F16) is easily obtained from (F7, F8)

because for example F16 = F8 * (F8 + 2 * F7) = 21 * (21 + 26) = 987, and F15 = F8 * F8 + F7 * F7 = 21^2 + 13^2 = 610.

So whatever number you want, by progressively halving the index when it is even or subtracting 1 when it is odd, you can get down to an easily looked-up Fibonacci number in LOGARITHMIC time.

Answer 2

I am not sure if there is a closed form for the nth term of the fibonacci series. If there is, you can calculate the nth term in constant time.

Otherwise the the time is of order n because you have to calculate the n-1 fibonacci numbers before it.

For example, if I want to calculate the nth fibonacci number,

I have the first 2 are 1 and 1

The algorithm would go something like this:

f(1) = f(2) = 1
i = 3
Do while i < n
....f(i) = f(i-1) + f(i-2)
....i = i + 1
Loop

This is an order n algorithm and is most efficient, assuming there is no closed form for the nth term of the fibonacci sequence.

Answer 3

Use Binet's formula and fast exponentiation.