DEV Community

loading...

An alternate way to calculate Fibonacci series

lyfolos profile image Muhammed H. Alkan Updated on ・2 min read
(The alternate way is at the end!)

Fibonacci series is a collection of numbers which two numbers that precede it.

Which will produce a series like this:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377

Calculating it

There are two popular ways to do this

  • Using the normal method (1 + 1 = 2, 1 + 2 = 3, 3 + 2 = 5, ...)
  • Using the recursive method (Fn = F(n - 1) + F(n - 2) where F1 and F2 is equal to 1)

Implementations in Python will be something like this (Finding first 100 Fibonacci numbers)

  • Normal method
a, b = 0, 1
for _ in range(100)
  print(a, end=' ')
  a, b = b, a + b

#=> 0 1 1 2 3 5 8 13...
  • Recursive method
def fib(n):
  if n < 3:
    return 1
  return fib(n - 1) + fib(n - 2)

for n in range(100):
  print(fib(n), end = ' ')

#=> 0 1 1 2 3 5 8 13...
(Not recommended to do it in Python due Tail Call Optimization)

So until now, I haven't seen any other ways. Why not find another way?

There is an interesting fact in Fibonacci numbers. What is the fact?

-> Dividing F(n + 1) with Fn (F(n + 1) / Fn) will approximate the golden ratio! (1.61803399...)

Let us test it!

1, 1, 2, 3, 5, 8, 13, 21, 34...

1 / 1 = 1  
2 / 1 = 2  
3 / 2 = 1.5  
8 / 5 = 1.6  
13 / 8 = 1.62  
21 / 13 = 1.615  
34 / 21 = 1.619  
...  

And so on! While numbers getting numbers bigger, the ratio will be more similar to the golden ratio. Then, what we can do with it?

If F(n + 1) / Fn ≈ φ, Fn * φ will be (approximately) equal to F(n + 1) which founds the next fibonacci number!

So, let's implement it in Python!

fib = 1
for _ in range(100):
  print(fib, end=' ')
  fib = round(fib * 1.618)

#=> 1, 1, 2, 3, 5, 8, 13, 21, 34...`

So I multiplied fib with 1.618 which is approximate golden ratio. As I said it will be found next fibonacci number approximately. Then I rounded it because I want an integer, not a decimal. If we need to visualize it:

fib = 1  
fib = round(fib * 1.61) -> fib = round(1.61) -> fib = 2      
fib = round(fib * 1.61) -> fib = round(3.22) -> fib = 3      
fib = round(fib * 1.61) -> fib = round(4.83) -> fib = 5      
fib = round(fib * 1.61) -> fib = round(8.05) -> fib = 8      
...  

And so on! It's an interesting method (found by me :p), but it can be wrong for really big numbers. For big numbers, you will need a better approximation of the golden ratio to use it. Because the decimal numbers multiplying with big numbers will create bigger numbers. For example:

1.2345 * 10 = 12.345  
1.2345 * 100 = 123.45  
1.2345 * 1000 = 1234.5  
1.2345 * 10000 = 12345  
1.2345 * 100000 = 123450  

So basically I don't recommend this method for big numbers.

Thanks for reading this post!

Discussion (0)

pic
Editor guide