CODEWITHSUNDEEP
c#arraysbiginteger
HowDoICSharply
HowDoICSharply

Reputation: 557

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

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:

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;
    }
}

Upvotes: 9

Views: 3272

Answers (4)

mizi
mizi

Reputation: 46

BigInteger bigInteger = BigInteger.Parse("12345678901234567890");

long bitLength = bigInteger.GetBitLength();//represents the length in binary
long decimalDigitCount = (long)Math.Ceiling(bitLength / 3.3219280948873623478703194294893);
Console.WriteLine("bigInteger is " + decimalDigitCount + "digits");

3.3219280948873623478703194294893 is a constant value of ln(10) / ln(2) and we use it for converting binary to decimal.

I used google's gemini AI for finding this solution. Also I think this way is faster than BigInteger.Log10(x) solution because it doesn't seem to do a math process on Biginteger. So if the number is very big, this way should be faster.

Upvotes: 1

Mike Marynowski
Mike Marynowski

Reputation: 3439

UPDATE:

This is an even quicker method on .NET 5 (since GetBitLength() is required):

private static readonly double exponentConvert = Math.Log10(2);
private static readonly BigInteger _ten = 10;

public static int CountDigits(BigInteger value)
{
    if (value.IsZero)
        return 1;

    value = BigInteger.Abs(value);

    if (value.IsOne)
        return 1;

    long numBits = value.GetBitLength();

    int base10Digits = (int)(numBits * exponentConvert).Dump();
    var reference = BigInteger.Pow(_ten, base10Digits);

    if (value >= reference)
        base10Digits++;

    return base10Digits;
}

The slowest part of this algorithm for large values is the BigInteger.Pow() operation. I have optimized the CountDigits() method in Singulink.Numerics.BigIntegerExtensions with a cache that holds powers of 10, so check that out if you are interested in the fastest possible implementation. It caches powers up to exponents of 1023 by default but if you want to trade memory usage for faster performance on even larger values you can increase the max cached exponent by calling BigIntegerPowCache.GetCache(10, maxSize) where maxSize = maxExponent + 1.

On an i7-3770 CPU, this library takes 350ms to get the digit count for 10 million BigInteger values (single-threaded) when the digit count <= the max cached exponent.

ORIGINAL ANSWER:

The accepted answer is unreliable, as indicated in the comments. This method works for all numbers:

private static int CountDigits(BigInteger value)
{    
    if (value.IsZero)
        return 1;
        
    value = BigInteger.Abs(value);
    
    if (value.IsOne)
        return 1;
    
    int exp = (int)Math.Ceiling(BigInteger.Log10(value));
    var test = BigInteger.Pow(10, exp);
    
    return value >= test ? exp + 1 : exp;
}

Upvotes: 3

Russ
Russ

Reputation: 4173

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.

Upvotes: 7

PHeiberg
PHeiberg

Reputation: 29831

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.

Upvotes: 9

Related Questions