BigInteger：计算可伸缩方法中的小数位数
我需要计算BigInteger的小数位数。 例如：
-
99返回2 -
1234返回4 -
9999返回4 -
12345678901234567890返回20
我需要为具有184948十进制数字的BigInteger执行此操作。 我怎样才能快速，可扩展？
convert-to-String方法很慢：
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); }
有没有更快的方法？
这看起来很有效。 我还没有进行详尽的测试，或者我没有运行任何时间测试，但它似乎有一个合理的运行时间。
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 (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(); } }
在我的Celeron M笔记本电脑上花了大约3秒钟，所以它应该在一些不错的套件上达到2秒。
这是基于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十进制数字，并且在一秒钟内完成更多。
我认为您可以使用bitLength（）来获取log2值，然后将基数更改为10 。
然而，结果可能是错误的一位数，所以这只是一个近似值。
但是，如果这是可以接受的，您可以始终将1添加到结果中并将其限制为最多 。 或者，减1， 至少得到。
这是另一种比Convert-to-String方法更快的方法。 不是最好的运行时间，但仍然是合理的0.65秒而不是2.46秒，使用Convert-to-String方法（180000位）。
此方法根据给定值计算基数10对数的整数部分。 但是，它不使用循环除法，而是使用类似于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; }
希望这会有所帮助。