Compute the Nth Fibonacci Numbers using Iterative and Math Algorithms

The Fibonacci sequence goes like this: 1, 1, 2, 3, 5, 8, 13, 21, 34, ... The next number can be found by adding up the two numbers before it, and the first two numbers are always 1. Write a function that takes an integer n and returns the nth Fibonacci number in the sequence.

Note: n will be less than or equal to 30.

Example 1
Input
n = 1
Output
1
Explanation
This is the base case and the first fibonacci number is defined as 1.

Example 2
Input
n = 6
Output
8
Explanation
Since 8 is the 6th fibonacci number: 1, 1, 2, 3, 5, 8.

Example 3
Input
n = 7
Output
13
Explanation
Since 13 is the seventh number: 1, 1, 2, 3, 5, 8, 13

Iterative Algorithm to Compute the Nth Fibonacci Number

Iteratively, we can compute the next item in the Fibonacci sequences.

int solve(int n) {
    int a = 1, b = 1;
    if (n <= 2) return 1;
    for (int i = 1; i < n; ++ i) {
        int c = a + b;
        a = b;
        b = c;
    }
    return a;
}

The complexity is O(N) as we are iterating N times to find the Nth Fibonacci number. The space complexity is O(1) constant.

Using Binet's Formula to Compute the Nth Fibonacci Number

According to Binet's Formula, we can compute the Nth Fibonacci Number by the followign equation:

[math] \frac{(1+\sqrt(5))^n - (1-\sqrt(5))^n}{2^n\sqrt(5)} [/math]

Thus, the following C++ computes the Nth Fibonacci Number using this equation which runs O(1) time and O(1) space (assuming the equation computation is O(1) constant))

int solve(int n) {
   return (pow(1 + sqrt(5), n) - pow(1 - sqrt(5), n)) / (pow(2, n) * sqrt(5));
}

--EOF (The Ultimate Computing & Technology Blog) --

Reposted to Algorithm Blockchain and Cloud

Follow me for topics of Algorithms, Blockchain and Cloud.
I am @justyy - a Steem Witness
https://steemyy.com

My contributions

• Steem Blockchain Tools
• Computing & Technology
• Download Youtube Video
• Find Cheap & Bargin VPS: VPS Database
• Online Software and Tools

Support me

If you like my work, please:

• Buy Me a Coffee, Thanks!
• Become my Sponsor, Thanks!
• Voting for me:
  https://steemit.com/~witnesses type in justyy and click VOTE
  
  Alternatively, you could proxy to me if you are too lazy to vote! and you can also vote me at the tool I made: https://steemyy.com/witness-voting/?witness=justyy