 # Finding number of digits in n’th term of Fibonacci Series

Hi community

This post going to explains about how to find no of digits in nth Fibonacci. Most of you must be familiar with Fibonacci numbers.
Check this Wikipedia article if not.

Given a no N , we have to find the no of digits in nth Fibonacci.

``````Input : n = 12
Output : 3
12'th Fibonacci number is 144 and it has
3 digits
``````

Approach 1-

calculate the the nth term of Fibonacci series.

``````//Fibonacci Series using Recursion
#include <iostream>
using namespace std;
int fib(int n)
{
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}
int main ()
{
int n = 12,s,count=0;
s=fib(n);
while(s!=0)
{
s /= 10;             // n = n/10
++count;
}
printf("Number of digits: %d",count);
return 0;
}
``````

Approach 2-

Though the first approach works , we have a more efficient direct way to do this using Binet’s Formula.

``````                   No of digits in f(N)  =Log10Fib(n)

= Log10(Φn / √ 5)

= n*Log10(Φ) - Log10√5

= n*Log10(Φ) - (Log105)/2
``````

Implememntation in c++

``````#include<bits/stdc++.h>
using namespace std;

int main()

{
long long int i,n;
scanf("%lli",n);
// Formula used (n * log(phi) - (log 5) / 2)
i=ceil((n * log10(1.6180339887498948)) -
((log10(5)) / 2));
printf("Number of Digits : %d",i);

return 0;
}
``````

Happy Coding …

Edit- Though Binet’s Formula is an approximate formula for calculating nth term , its is viable to use it to calculate no of digits in nth term.

1 Like

Isn’t this an approximation? Aren’t you neglecting the negative part of the formula? Please comment on its accuracy, like range of n for which it works.

Yes the formula is an approximation to calculate the nth term of Fibonacci series due to limitations of floating point arithmetic, however it should work fine for positive integers also standard convention is we take 1st and 2nd term as 0 and 1 so negative no willn’t be there.
So it looks viable to use this formula to find count of digits in n’th Fibonacci number.

I was asking if the term ((1-sqrt(5))/2)^n would cause any effect on this but resources online indicate that its quite a reasonable apporximation for larger n. So this should work for larger n. For small we can easily brute force.

Agreed. Here am not using that formula to calculate nth term but just using a
corollary of the Binet’s Formula to find the no of digits in nth term. And as per wikipedia this would do reasonably well and reduce time taken.