BigInteger: conta il numero di cifre decimali in un metodo scalabile

Question

Ho bisogno di contare il numero di cifre decimali di un BigInteger. Ad esempio:

• 99 rendimenti 2
• 1234 rendimenti 4
• 9999 rendimenti 4
• 123456789 rendimenti 20

ho bisogno di fare questo per un BigInteger con 184948 de cifre cifre e altro. Come posso fare questo veloce e scalabile?

Il convert-to-String approccio è lento: ci

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

Sono uno più veloce:

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

Questo loop-devide-by-ten approccio è ancora più lento metodi?

Answer 1

Sembra che funzioni. Non ho ancora eseguito test esaustivi, n'o ho eseguito test in qualsiasi momento, ma sembra avere un tempo di esecuzione ragionevole.

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

} 

sono voluti circa 3 secondi sul mio portatile Celeron M e quindi dovrebbe colpire sub 2 secondi su alcuni kit di decente.

Answer 2

Penso che sia possibile utilizzare bitLength() per ottenere un valore log2, quindi change the base to 10.

Il risultato potrebbe essere errato, tuttavia, di una cifra, quindi questa è solo un'approssimazione.

Tuttavia, se ciò è accettabile, è sempre possibile aggiungere 1 al risultato e vincolarlo al numero al massimo. . In alternativa, sottrarre 1 e ottenere almeno.

Answer 3

Ecco un metodo veloce basata su 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; 
} 

Il codice seguente prova i numeri 1, 9, 10, 99, 100, 999, 1000, ecc fino a diecimila cifre:

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

Questo può controllare un BigInteger con 184,948 cifre decimali e più in ben meno di un secondo.

Answer 4

Questo è un altro modo per eseguire più rapidamente il metodo Converti in stringa. Non il miglior tempo di esecuzione, ma comunque ragionevole 0,65 secondi contro 2,46 secondi con il metodo Converti in stringa (a 180000 cifre).

Questo metodo calcola la parte intera del logaritmo in base 10 dal valore specificato. Tuttavia, invece di usare loop-divide, usa una tecnica simile a Esponentiation di Squaring.

Ecco un'implementazione greggio che raggiunge il runtime accennato in precedenza:

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

auguriamo che questo aiuta.