finding number of digits in nth fibonacci number

Finding number of digits in n’th Fibonacci number



Given a number n, find number of digits in n’th Fibonacci Numbers. First few Fibinacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ….

Input : n = 6
Output : 1
6'th Fibonacci number is 8 and it has 
1 digit.

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

simple solution is to find n’th Fibonacci Number and then count number of digits in it. This solution may lead to overflow problems for large values of n. Adirect way is to count number of digits in the nth Fibonacci number using below Binet’s Formula.

fib(n) = (Φn - Ψ-n) / √5
where
Φ = (1 + √5) / 2
Ψ = (1 - √5) / 2

The above formula can be simplified, 
fib(n) = round(Φn / √ 5) 
Here round function indicates nearest integer.

Count of digits in Fib(n) = Log10Fib(n)
                          = Log10n / √ 5)
                          = n*Log10(Φ) - Log10√5
                          = n*Log10(Φ) - (Log105)/2

As mentioned in this G-Fact, this formula doesn’t seem to work and produce correct Fibonacci numbers due to limitations of floating point arithmetic. However, it looks viable to use this formula to find count of digits in n’th Fibonacci number. Below is C++ implementation of the formula.

/* C++ program to find number of digits in nth
   Fibonacci number */
#include<bits/stdc++.h>
using namespace std;

// This function returns the number of digits
// in nth Fibonacci number after ceiling it
// Formula used (n * log(phi) - (log 5) / 2)
long long numberOfDigits(long long n)
{
    if (n == 1)
        return 1;

    // using phi = 1.6180339887498948
    long double d = (n * log10(1.6180339887498948)) -
                    ((log10(5)) / 2);

    return ceil(d);
}

// Driver program to test the above function
int main()
{
    long long i;
    for (i = 1; i <= 10; i++)
    cout << "Number of Digits in F("
         << i <<") - "
         << numberOfDigits(i) << "\n";

    return 0;
}

Output:

Number of Digits in F(1) - 1
Number of Digits in F(2) - 1
Number of Digits in F(3) - 1
Number of Digits in F(4) - 1
Number of Digits in F(5) - 1
Number of Digits in F(6) - 1
Number of Digits in F(7) - 2
Number of Digits in F(8) - 2
Number of Digits in F(9) - 2
Number of Digits in F(10) - 2

References: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#section2https://en.wikipedia.org/wiki/Fibonacci_number This article is contributed by Ayush Khanduri. If you like GeeksforGeeks and would like to contribute, you can also write an article usingcontribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s