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

Question

假设 n 是一个 BigInteger，我想要它的前 5 位数字。我有两种想法：

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

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

在我测试这些选项之前，我想听听关于它的考虑（您如何看待它们，是否有更好的东西，等等）。

Answer 1

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

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

天真的方法是将原始值除以 10 而它大于或等于 1_000_000:

   1234567 => 123456 => 12345

然而，除法是昂贵的，尤其是当我们有一个巨大的数字时（如果我们有一个约 1000000 位的数字，我们必须将这个数字除以约 1000000 次）。创建更快的解决方案我们可以计算 10 的适当幂（幂计算很快）然后只除一次：

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

所以原始想法是

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

这里有两个难点：

负数（我们至少在计算对数时应该取source的绝对值）
巨大 source 的舍入误差（如果我们四舍五入并且只有 4 数字怎么办？）

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

  value.GetBitLength() * 0.30102999566398

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

将所有组合在一起：

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

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

Fastest way to get the first 5 digits of a BigInteger

c#

algorithm

optimization

biginteger