我正在解决这个问题，其中他们要求第一个1000位斐波那契数的索引，我的第一个想法类似于：
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;
但是，据我所知，没有方法可以计算 BigInteger 的位数。这是真的？规避它的一种方法是使用 BigInteger 的 .ToString().Length 方法，但我被告知字符串处理速度很慢。
BigInteger 还有一个 .ToByteArray()，我想将 BigInteger 转换为字节数组并检查该数组的长度 - 但我不认为这唯一地决定了 BigInteger 中的位数。
对于它的价值，我实现了另一种解决方法，即手动将斐波那契数存储在数组中，并且一旦数组满就停止，我将其与基于 .ToString 的方法进行了比较，该方法大约是慢了 2.5 倍，但是第一种方法需要 0.1 秒，看起来也很长。
编辑：我已经测试了下面答案中的两个建议（一个使用 BigInteger.Log，另一个使用 MaxLimitMethod）。我得到以下运行时间：
节目
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;
}
}
假设 x > 0
int digits = (int)Math.Floor(BigInteger.Log10(x) + 1);
将得到位数。
出于好奇，我测试了
int digits = x.ToString().Length;
方法。对于 100 000 000 次迭代，它比 Log10 解决方案慢 3 倍。
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;
}
这应该会带来显着的性能提升。
这是 .NET 5 上更快的方法（因为需要
GetBitLength()
）：
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;
}
对于大值，该算法最慢的部分是 BigInteger.Pow()
操作。我已经优化了Singulink.Numerics.BigIntegerExtensions
中的
CountDigits() 方法，其缓存的幂为 10，因此请检查一下您是否对最快的实现感兴趣。默认情况下，它的缓存指数高达 1023，但如果您想以内存使用换取更大值的更快性能，您可以通过调用 BigIntegerPowCache.GetCache(10, maxSize)（其中
maxSize = maxExponent + 1）来增加最大缓存指数。在 i7-3770 CPU 上，当数字计数
时，该库需要 350ms 才能获得 1000 万个
BigInteger如评论中所示，接受的答案不可靠。此方法适用于所有数字：
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;
}
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
是 ln(10) / ln(2) 的常量值，我们用它来将二进制转换为十进制。我使用谷歌的 Gemini AI 来找到这个解决方案。另外，我认为这种方法比
BigInteger.Log10(x)
解决方案更快，因为它似乎没有对 Biginteger 进行数学处理。所以如果数量很大的话，这种方式应该会更快。