BigInteger：スケーラブルメソッドの小数点以下の桁数をカウントする

Question

小数点以下の桁数はBigIntegerです。たとえば、次のように

• 99戻り、私は184948ドとBigIntegerこのを行う必要があり2
• 1234戻り4
• 9999戻り4
• 123456789戻り20

桁数字など。 これを迅速かつスケーラブルにするにはどうすればよいですか？

変換ツー文字列アプローチは遅いです：

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

このループdevide・バイ・10アプローチはさらに遅いです：

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

も速くあります方法？

Answer 1

これは動作しているようです。私は徹底的なテストをまだ実行していませんが、いつでもテストを実行していますが、それは合理的な実行時間を持つようです。

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秒以下になるはずです。

Answer 2

私はbitLength()を使用してlog2の値を取得し、次にchange the base to 10と考えることができます。

ただし、結果は1桁で間違っている可能性があります。これは単なる近似値です。

ただし、それでも問題が解決しない場合は、結果に1を加えて、最大ではとなるようにバインドします。または、1を引いて、を少なくともにします。

Answer 3

ここDariusz's answerに基づく高速な方法です：

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万桁までずっと数字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"); 
} 

これはBigInteger184,948と小数点以下の桁数を確認することができ、第二の下でも、より。

Answer 4

これは、Convert-to-Stringメソッドよりも高速に行う別の方法です。最高の実行時間ではありませんが、Convert-to-String方式（180000桁）で2.46秒であったのに対して、0.65秒ではまだ合理的です。

このメソッドは、指定された値から10進数の対数の整数部分を計算します。しかし、loop-divideを使用する代わりに、SquaringによるExponentiationに似たテクニックを使用します。ここで

は、前述のランタイムを実現し、粗実装です：

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

は、この意志がお役に立てば幸いです。