Print a particular nth Fibonacci number in C++ up to range 10^18

In this tutorial, we are going to learn how to print a particular Fibonacci number up to range 10^18 in C++. We are going to use a hash map for this particular problem. As we know we cannot use an array for storing so many values so using the hash map is a proper choice for this particular type of problem.

Consider fib(n) to be the (n+1) th Fibonacci number. We will have two cases when n is even and another one when n is odd. Consider a variable k which is equal to n/2.

For the first case when n is even we will use this relation :

• fib(n) = fib(k)*fib(k) + fib(k-1)*fib(k-1)

For the second case when n is odd we will use this relation :

• fib(n) = fib(k)*fib(k+1) + fib(k-1)*fib(k)

Lets try to implement our above idea to get the solution of this problem.

Program to print a particular Fibonacci number in C++

Cpp source code:

// Program to print a particular Fibonacci number
#include<bits/stdc++.h>
using namespace std;

// Declaring hashmap
map<long long int ,long long int>F;
int fib(long long int n)
{
  if(F.count(n)) // Checking if we have already calcuted that Fibonacci number
  {
    return F[n];
  }
  long long int k=n/2;
  if(n%2==0)
  {
    return F[n]=(fib(k)*fib(k)+fib(k-1)*fib(k-1))%1000000007;
  }
  else
  {
    return F[n]=(fib(k)*fib(k+1)+fib(k-1)*fib(k))%1000000007;
  }
}
// Driver Code
int main()
{
  long long int n;
  cout<<"Enter the ith number: ";
  cin>>n;
  
  F[0]=F[1]=1;
  cout<<"\nThe "<<n <<  " th Fibonacci number is "<<fib(n-1)<<"\n";
  
  return 0;
}

Input/Output:

Enter the ith number: 10000

The 10000 th Fibonacci number is 910095538

• Time Complexity of this code is O( log n * log log n ).

You may also learn,

check if a given matrix is sparse or not in C++

Solution of Tower Of Hanoi Problem in C++

Do not forget to comment if you find anything wrong in the post or you want to share some information regarding the same.