fibonacci_fast.cpp File Reference

Faster computation of Fibonacci series. More...

#include <cinttypes>
#include <cstdio>
#include <iostream>

Include dependency graph for fibonacci_fast.cpp:

Go to the source code of this file.

Macros
#define	MAX   93

Functions
uint64_t	fib (uint64_t n)
int	main ()

Detailed Description

Faster computation of Fibonacci series.

An efficient way to calculate nth fibonacci number faster and simpler than \(O(n\log n)\) method of matrix exponentiation This works by using both recursion and dynamic programming. as 93rd fibonacci exceeds 19 digits, which cannot be stored in a single long long variable, we can only use it till 92nd fibonacci we can use it for 10000th fibonacci etc, if we implement bigintegers. This algorithm works with the fact that nth fibonacci can easily found if we have already found n/2th or (n+1)/2th fibonacci It is a property of fibonacci similar to matrix exponentiation.

Author

Krishna Vedala

See also

fibonacci_large.cpp, fibonacci.cpp, string_fibonacci.cpp

Definition in file fibonacci_fast.cpp.

Macro Definition Documentation

MAX

#define MAX   93

maximum number that can be computed - The result after 93 cannot be stored in a uint64_t data type.

Definition at line 27 of file fibonacci_fast.cpp.

Function Documentation

fib()

uint64_t fib

(

uint64_t

n

)

Algorithm

Definition at line 30 of file fibonacci_fast.cpp.

                         {
    static uint64_t f1 = 1,
                    f2 = 1;  // using static keyword will retain the values of
                             // f1 and f2 for the next function call.
 
    if (n <= 2)
        return f2;
    if (n >= 93) {
        std::cerr
            << "Cannot compute for n>93 due to limit of 64-bit integers\n";
        return 0;
    }
 
    uint64_t temp = f2;  // we do not need temp to be static
    f2 += f1;
    f1 = temp;
 
    return f2;
}

main()

int main

(

void

)

Main function

Definition at line 51 of file fibonacci_fast.cpp.

           {
    // Main Function
    for (uint64_t i = 1; i < 93; i++) {
        std::cout << i << " th fibonacci number is " << fib(i) << std::endl;
    }
    return 0;
}