DEV Community

Muhammed H. Alkan
Muhammed H. Alkan

Posted on • Updated on

An alternate way to calculate Fibonacci series

(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)