Can I find the number of digits of a BigInteger in C#?

Question

I am solving this problem, in which they ask for the index of the first Fibonacci number of 1000 digits, and my first idea was something similar to:

BigInteger x = 1;
BigInteger y = 1;
BigInteger tmp = 0;

int currentIndex = 2;
while (x.NoOfDigits < 1000)
{
    tmp = x + y;
    y = x;
    x = tmp;
    currentIndex++;
}
return currentIndex;

However, as far as I can tell, there is no method for counting the number of digits of a BigInteger. Is this true? One way of circumventing it is to use the .ToString().Length method of a BigInteger, but I'm told that string processing is slow.

A BigInteger also has a .ToByteArray(), and I thought of converting a BigInteger to a byte array and checking the length of that array - but I don't think that this uniquely determines the number of digits in the BigInteger.

For what it's worth, I implemented another way of solving it, which is manually storing the Fibonacci numbers in array, and which stops as soon as the array is full, and I compared this to the .ToString-based method, which is about 2.5 times slower, but the first method takes 0.1 second, which also seems like a long time.

Edit: I've tested the two suggestions in the answers below (the one with BigInteger.Log and the one with MaxLimitMethod). I get the following run times:

• Original method: 00:00:00.0961957
• StringMethod: 00:00:00.1535350
• BigIntegerLogMethod: 00:00:00.0387479
• MaxLimitMethod: 00:00:00.0019509

Program

using System;
using System.Collections.Generic;
using System.Numerics;
using System.Diagnostics;

class Program
{
    static void Main(string[] args)
    {
        Stopwatch clock = new Stopwatch();
        clock.Start();
        int index1 = Algorithms.IndexOfNDigits(1000);
        clock.Stop();
        var elapsedTime1 = clock.Elapsed;
        Console.WriteLine(index1);
        Console.WriteLine("Original method: {0}",elapsedTime1);
        Console.ReadKey();

        clock.Reset();
        clock.Start();
        int index2 = Algorithms.StringMethod(1000);
        clock.Stop();
        var elapsedTime2 = clock.Elapsed;
        Console.WriteLine(index2);
        Console.WriteLine("StringMethod: {0}", elapsedTime2);
        Console.ReadKey();

        clock.Reset();
        clock.Start();
        int index3 = Algorithms.BigIntegerLogMethod(1000);
        clock.Stop();
        var elapsedTime3 = clock.Elapsed;
        Console.WriteLine(index3);
        Console.WriteLine("BigIntegerLogMethod: {0}", elapsedTime3);
        Console.ReadKey();

        clock.Reset();
        clock.Start();
        int index4 = Algorithms.MaxLimitMethod(1000);
        clock.Stop();
        var elapsedTime4 = clock.Elapsed;
        Console.WriteLine(index4);
        Console.WriteLine("MaxLimitMethod: {0}", elapsedTime4);
        Console.ReadKey();


    }
}

static class Algorithms
{
    //Find the index of the first Fibonacci number of n digits
    public static int IndexOfNDigits(int n)
    {
        if (n == 1) return 1;
        int[] firstNumber = new int[n];
        int[] secondNumber = new int[n];

        firstNumber[0] = 1;
        secondNumber[0] = 1;
        int currentIndex = 2;

        while (firstNumber[n-1] == 0)
        {
            int carry = 0, singleSum = 0;
            int[] tmp = new int[n]; //Placeholder for the sum
            for (int i = 0; i<n; i++)
            {
                singleSum = firstNumber[i] + secondNumber[i];
                if (singleSum >= 10) carry = 1;
                else carry = 0;

                tmp[i] += singleSum % 10;
                if (tmp[i] >= 10)
                {
                    tmp[i] = 0;
                    carry = 1;
                }
                int countCarries = 0;
                while (carry == 1)
                {
                    countCarries++;
                    if (tmp[i + countCarries] == 9)
                    {
                        tmp[i + countCarries] = 0;
                        tmp[i + countCarries + 1] += 1;
                        carry = 1;
                    }
                    else
                    {
                        tmp[i + countCarries] += 1;
                        carry = 0;
                    }
                }
            }

            for (int i = 0; i < n; i++ )
            {
                secondNumber[i] = firstNumber[i];
                firstNumber[i] = tmp[i];
            }
            currentIndex++;
        }
        return currentIndex;
    }

    public static int StringMethod(int n)
    {
        BigInteger x = 1;
        BigInteger y = 1;
        BigInteger tmp = 0;
        int currentIndex = 2;

        while (x.ToString().Length < n)
        {
            tmp = x + y;
            y = x;
            x = tmp;
            currentIndex++;
        }
        return currentIndex;
    }

    public static int BigIntegerLogMethod(int n)
    {
        BigInteger x = 1;
        BigInteger y = 1;
        BigInteger tmp = 0;
        int currentIndex = 2;

        while (Math.Floor(BigInteger.Log10(x) + 1) < n)
        {
            tmp = x + y;
            y = x;
            x = tmp;
            currentIndex++;
        }
        return currentIndex;
    }

    public static int MaxLimitMethod(int n)
    {
        BigInteger maxLimit = BigInteger.Pow(10, n - 1);
        BigInteger x = 1;
        BigInteger y = 1;
        BigInteger tmp = 0;
        int currentIndex = 2;

        while (x.CompareTo(maxLimit) < 0)
        {
            tmp = x + y;
            y = x;
            x = tmp;
            currentIndex++;
        }
        return currentIndex;
    }
}

Answer 1

Provided that x > 0

int digits = (int)Math.Floor(BigInteger.Log10(x) + 1);

will get the number of digits.

Out of curiosity, I tested the

int digits = x.ToString().Length; 

approach. For 100 000 000 iterations, it's 3 times slower than the Log10 solution.

Answer 2

Expanding on my comment--instead of testing based on number of digits, test based on exceeding a constant that has the upper limit of the problem:

public static int MaxLimitMethod(int n)
    {
        BigInteger maxLimit = BigInteger.Pow(10, n);
        BigInteger x = 1;
        BigInteger y = 1;
        BigInteger tmp = 0;
        int currentIndex = 2;

        while (x.CompareTo(maxLimit) < 0)
        {
            tmp = x + y;
            y = x;
            x = tmp;
            currentIndex++;
        }
        return currentIndex;
    }

This should result in a significant performance increase.