16

我需要计算 a 的小数位数BigInteger。例如：

  • 99返回2
  • 1234返回4
  • 9999返回4
  • 12345678901234567890返回20

我需要对带有十进制数字等的 aBigInteger184948执行此操作。我怎样才能快速且可扩展地做到这一点？

转换为字符串的方法很慢：

public String getWritableNumber(BigInteger number) {
   // Takes over 30 seconds for 184948 decimal digits
   return "10^" + (number.toString().length() - 1);
}

这种循环除以十的方法甚至更慢：

public String getWritableNumber(BigInteger number) {
    int digitSize = 0;
    while (!number.equals(BigInteger.ZERO)) {
        number = number.divide(BigInteger.TEN);
        digitSize++;
    }
    return "10^" + (digitSize - 1);
}

有没有更快的方法？

4

5 回答 5

14

这是一种基于Dariusz 回答的快速方法：

public static int getDigitCount(BigInteger number) {
  double factor = Math.log(2) / Math.log(10);
  int digitCount = (int) (factor * number.bitLength() + 1);
  if (BigInteger.TEN.pow(digitCount - 1).compareTo(number) > 0) {
    return digitCount - 1;
  }
  return digitCount;
}

以下代码测试数字 1、9、10、99、100、999、1000 等一直到万位数：

public static void test() {
  for (int i = 0; i < 10000; i++) {
    BigInteger n = BigInteger.TEN.pow(i);
    if (getDigitCount(n.subtract(BigInteger.ONE)) != i || getDigitCount(n) != i + 1) {
      System.out.println("Failure: " + i);
    }
  }
  System.out.println("Done");
}

这可以在一秒钟内检查十进制数字和更多BigInteger。184,948

于 2014-05-21T02:36:54.920 回答
10

这看起来像是在工作。我还没有运行详尽的测试，也没有运行任何时间测试，但它似乎有一个合理的运行时间。

public class Test {
  /**
   * Optimised for huge numbers.
   *
   * http://en.wikipedia.org/wiki/Logarithm#Change_of_base
   *
   * States that log[b](x) = log[k](x)/log[k](b)
   *
   * We can get log[2](x) as the bitCount of the number so what we need is
   * essentially bitCount/log[2](10). Sadly that will lead to inaccuracies so
   * here I will attempt an iterative process that should achieve accuracy.
   *
   * log[2](10) = 3.32192809488736234787 so if I divide by 10^(bitCount/4) we
   * should not go too far. In fact repeating that process while adding (bitCount/4)
   * to the running count of the digits will end up with an accurate figure
   * given some twiddling at the end.
   * 
   * So here's the scheme:
   * 
   * While there are more than 4 bits in the number
   *   Divide by 10^(bits/4)
   *   Increase digit count by (bits/4)
   * 
   * Fiddle around to accommodate the remaining digit - if there is one.
   * 
   * Essentially - each time around the loop we remove a number of decimal 
   * digits (by dividing by 10^n) keeping a count of how many we've removed.
   * 
   * The number of digits we remove is estimated from the number of bits in the 
   * number (i.e. log[2](x) / 4). The perfect figure for the reduction would be
   * log[2](x) / 3.3219... so dividing by 4 is a good under-estimate. We 
   * don't go too far but it does mean we have to repeat it just a few times.
   */
  private int log10(BigInteger huge) {
    int digits = 0;
    int bits = huge.bitLength();
    // Serious reductions.
    while (bits > 4) {
      // 4 > log[2](10) so we should not reduce it too far.
      int reduce = bits / 4;
      // Divide by 10^reduce
      huge = huge.divide(BigInteger.TEN.pow(reduce));
      // Removed that many decimal digits.
      digits += reduce;
      // Recalculate bitLength
      bits = huge.bitLength();
    }
    // Now 4 bits or less - add 1 if necessary.
    if ( huge.intValue() > 9 ) {
      digits += 1;
    }
    return digits;
  }

  // Random tests.
  Random rnd = new Random();
  // Limit the bit length.
  int maxBits = BigInteger.TEN.pow(200000).bitLength();

  public void test() {
    // 100 tests.
    for (int i = 1; i <= 100; i++) {
      BigInteger huge = new BigInteger((int)(Math.random() * maxBits), rnd);
      // Note start time.
      long start = System.currentTimeMillis();
      // Do my method.
      int myLength = log10(huge);
      // Record my result.
      System.out.println("Digits: " + myLength+ " Took: " + (System.currentTimeMillis() - start));
      // Check the result.
      int trueLength = huge.toString().length() - 1;
      if (trueLength != myLength) {
        System.out.println("WRONG!! " + (myLength - trueLength));
      }
    }
  }

  public static void main(String args[]) {
    new Test().test();
  }

}

在我的 Celeron M 笔记本电脑上花了大约 3 秒，所以它应该在一些不错的套件上达到 2 秒以下。

于 2013-09-17T21:40:56.930 回答
9

我认为您可以使用bitLength()获取 log2 值，然后将基数更改为 10。

然而，结果可能有一个数字的错误，所以这只是一个近似值。

但是，如果这是可以接受的，您始终可以在结果中添加 1 并将其限制为最多. 或者，减 1，至少得到.

于 2013-09-16T12:50:33.813 回答
1

这是另一种比 Convert-to-String 方法更快的方法。不是最好的运行时间，但仍然是合理的 0.65 秒，而使用 Convert-to-String 方法（180000 位）为 2.46 秒。

此方法根据给定值计算以 10 为底的对数的整数部分。但是，它不是使用循环除法，而是使用类似于平方求幂的技术。

这是实现前面提到的运行时的粗略实现：

public static BigInteger log(BigInteger base,BigInteger num)
{
    /* The technique tries to get the products among the squares of base
     * close to the actual value as much as possible without exceeding it.
     * */
    BigInteger resultSet = BigInteger.ZERO;
    BigInteger actMult = BigInteger.ONE;
    BigInteger lastMult = BigInteger.ONE;
    BigInteger actor = base;
    BigInteger incrementor = BigInteger.ONE;
    while(actMult.multiply(base).compareTo(num)<1)
    {
        int count = 0;
        while(actMult.multiply(actor).compareTo(num)<1)
        {
            lastMult = actor; //Keep the old squares
            actor = actor.multiply(actor); //Square the base repeatedly until the value exceeds 
            if(count>0) incrementor = incrementor.multiply(BigInteger.valueOf(2));
            //Update the current exponent of the base
            count++;
        }
        if(count == 0) break;

        /* If there is no way to multiply the "actMult"
         * with squares of the base (including the base itself)
         * without keeping it below the actual value, 
         * it is the end of the computation 
         */
        actMult = actMult.multiply(lastMult);
        resultSet = resultSet.add(incrementor);
        /* Update the product and the exponent
         * */
        actor = base;
        incrementor = BigInteger.ONE;
        //Reset the values for another iteration
    }
    return resultSet;
}
public static int digits(BigInteger num)
{
    if(num.equals(BigInteger.ZERO)) return 1;
    if(num.compareTo(BigInteger.ZERO)<0) num = num.multiply(BigInteger.valueOf(-1));
    return log(BigInteger.valueOf(10),num).intValue()+1;
}

希望这会有所帮助。

于 2014-12-27T07:28:06.947 回答
1

您可以先将 a 转换BigInteger为 a BigDecimal，然后使用此答案计算位数。这似乎比使用更有效，BigInteger.toString()因为它会为String表示分配内存。

    private static int numberOfDigits(BigInteger value) {
        return significantDigits(new BigDecimal(value));
    }

    private static int significantDigits(BigDecimal value) {
        return value.scale() < 0
               ? value.precision() - value.scale()
               : value.precision();
    }
于 2020-07-16T08:40:48.443 回答