 # How to find next fibonacci number if given a fibonacci number?

How to find next fibonacci number if given a fibonacci number?

for eg if n = 8

1 Like

What is the required time complexity?

O(1) Time Complexity.

What is the range of n?

Range of n ?

Btw, did you go through this? Trust me, I didn’t extract it from the deep web, just a simple Google search. 2 Likes

this is the correct way but i remember it’s not accurate for very large value of n’s
(which is why you asked for the range of n right?)

3 Likes

I think this formula is the best.
Proof is also given.

but it only works for smaller values. maximum upto 50

Who told you that. I think it will work for every value.

This is the plot of the absolute errors of the values approximated by the formula for values of X \in [1, 82]. The max value of the range is denoted by MAX in the Python 3 script. You may play with them to see how the values change.

Here's the code
from math import sqrt
from matplotlib import pyplot as plt

MAX = 82 # limit of X
num = (1 + sqrt(5)) / 2 # multiplying factor

# creating the lists
X		= [_ for _ in range(1, MAX + 1)]	# index
Fib		= [1 for _ in range(1, MAX + 1)]	# Actual values
Approx	= [1 for _ in range(1, MAX + 1)]	# Approx values
Err		= [1 for _ in range(1, MAX + 1)]	# |Real - Approx|

# fill 'em up
for _ in range(2, MAX):
Fib[_] = Fib[_ - 1] + Fib[_ - 2]
for _ in range(1, MAX):
Approx[_] = int(Fib[_ - 1] * num)
for _ in range(1, MAX):
Err[_] = abs(Fib[_] - Approx[_])

# X vs Error

# values
print("X\tError")
for _ in range(0, MAX):
print("%d\t%d" % (X[_], Err[_]))

# plot
plt.plot(X, Err, color = 'r')
plt.show() 3 Likes