BigInteger: counts the number of decimal digits in a scalable method

Question

I need to count the number of decimal digits of BigInteger . For example:

• 99 returns 2
• 1234 returns 4
• 9999 returns 4
• 12345678901234567890 returns 20

I need to do this for BigInteger with 184948 decimal digits and more. How can I do this fast and scalable?

The convert-to-String method is slow:

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

This ten-by-ten approach is even slower:

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

Are there faster methods?

Answer 1

It looks like it works. I haven't run exhaustive tests yet, or I'm running time tests, but it seems to have a reasonable lead time.

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

Took about 3 seconds on my Celeron M laptop, so it should take 2 seconds on some decent kit.

Answer 2

Here's a quick method based on the Dariusz 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; } 

The following code checks the numbers 1, 9, 10, 99, 100, 999, 1000, etc. up to ten thousand digits:

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

This can check BigInteger with 184,948 decimal digits and more for a second.

Answer 3

I think you can use bitLength () to get the log2 value, then change the base to 10 .

The result may be erroneous, however, with one digit, so this is just an approximation.

However, if this is acceptable, you can always add 1 to the result and tie it to the best. Or, subtract 1 and get at least.

Answer 4

This is another way to do this faster than the Convert-to-String method. Not the best running time, but still a reasonable 0.65 seconds versus 2.46 seconds using the Convert-to-String method (for 180,000 digits).

This method calculates the integer part of the base-10 logarithm from the given value. However, instead of using a division cycle, he uses a technique similar to squaring.

The following is a rough implementation that allows you to execute the above working environment:

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

Hope this helps.