Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
Faster computation of Fibonacci series. More...
#include <cinttypes>
#include <cstdio>
#include <iostream>
Macros | |
#define | MAX 93 |
Functions | |
uint64_t | fib (uint64_t n) |
int | main () |
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.
#define MAX 93 |
maximum number that can be computed - The result after 93 cannot be stored in a uint64_t
data type.
uint64_t fib | ( | uint64_t | n | ) |
Algorithm
int main | ( | void | ) |
Main function