c# - 获取 BigInteger 前 5 位数字的最快方法

Question

假设n是一个BigInteger，我想要它的前5位数字。我从两个方面思考:

1. 将 n 除以 10 log₁₀(n)-5 次(因此仅保留前 5 位数字)。
2. 获取 n 字符串的 Substring(0, 5)。

我不知道哪一个更快，或者是否有其他选项可能比这些更好。

在测试这些选项之前，我想听听对此的考虑(您对它们有何看法，是否有更好的东西等)。

Answer 1

如果我们想找出前5位前导数字，我们可以利用整数除法:

   123     / 1   == 123
   12345   / 1   == 12345
   1234567 / 100 == 12345

简单的方法是在 10 大于或等于 1_000_000 时将原始值除以 10 :

   1234567 => 123456 => 12345

但是，除法的成本很高，尤其是当我们有一个巨大的数字时(如果我们有一个约 1000000 位的数字，我们必须将此数字除约 1000000 次)。创建更快的解决方案 我们可以计算 source 的适当幂(幂计算很快)，然后只除一次:

  1234567 / Pow(10, Log10(1234567) - 5 + 1)

所以原始想法是

  result = source / BigInteger.Pow(10, (int)BigInteger.Log10(source) - 4);

这里有两个困难:

1. 负数(至少在计算对数时应该取 source 的绝对值)
2. 巨大 4 的舍入错误(如果我们进行舍入并且只有 Log10 数字会怎样？)

为了解决这两个问题，我自己将 Log10(2) * Log2(source) 计算为 5 :

  value.GetBitLength() * 0.30102999566398

这保证了我至少有至少个 6 数字，但在出现舍入错误的情况下可能是 0.30102999566398 < Log10(2) (注意 ojit_code )。

将所有内容组合在一起:

private static int FirstDigits(BigInteger value) {
  if (value.IsZero)
    return 0; 

  int digits = 5;

  int result = (int)(value / 
    BigInteger.Pow(10, (int)(value.GetBitLength() * 0.30102999566398 - digits + 1)));

  while (result >= 1_000_000 || result <= -1_000_000)
    result /= 10;  

  return result;   
}