Java BigInteger：以可扩展的方法计算小数位数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18828377/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
BigInteger: count the number of decimal digits in a scalable method
提问by Geoffrey De Smet
I need the count the number of decimal digits of a BigInteger. For example:
我需要计算 a 的十进制位数BigInteger。例如：
99returns21234returns49999returns412345678901234567890returns20
99回报21234回报49999回报412345678901234567890回报20
I need to do this for a BigIntegerwith 184948decimal digits and more. How can I do this fast and scalable?
我需要为BigInteger带有184948十进制数字和更多的数字执行此操作。我怎样才能做到这一点快速且可扩展？
The convert-to-Stringapproach is slow:
在转换到字符串的方法是缓慢的：
public String getWritableNumber(BigInteger number) {
// Takes over 30 seconds for 184948 decimal digits
return "10^" + (number.toString().length() - 1);
}
This loop-devide-by-tenapproach 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 any faster methods?
有没有更快的方法？
采纳答案by OldCurmudgeon
This looks like it is working. I haven't run exhaustive tests yet, n'or have I run any time tests but it seems to have a reasonable run 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'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();
}
}
Took about 3 seconds on my Celeron M laptop so it should hit sub 2 seconds on some decent kit.
在我的 Celeron M 笔记本电脑上花了大约 3 秒，所以它应该在一些不错的套件上达到 2 秒以下。
回答by Dariusz
I think that you could use bitLength()to get a log2 value, then change the base to 10.
我认为您可以使用bitLength()来获取 log2 值，然后将基数更改为 10。
The result may be wrong, however, by one digit, so this is just an approximation.
然而，结果可能有一个数字错误，所以这只是一个近似值。
However, if that's acceptable, you could always add 1 to the result and bound it to be at most. Or, subtract 1, and get at least.
但是，如果这是可以接受的，您始终可以将 1 添加到结果并将其绑定到最多。或者，减去 1，得到至少。
回答by dln385
Here's a fast method based on Dariusz's answer:
这是基于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;
}
The following code tests the numbers 1, 9, 10, 99, 100, 999, 1000, etc. all the way to ten-thousand digits:
下面的代码测试数字 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");
}
This can check a BigIntegerwith 184,948decimal digits and more in well under a second.
这可以检查BigInteger与184,948小数位数多在阱中的第二下。
回答by Truthseeker Rangwan
This is an another way to do it faster than Convert-to-String method. Not the best run time, but still reasonable 0.65 seconds versus 2.46 seconds with Convert-to-String method (at 180000 digits).
这是另一种比 Convert-to-String 方法更快的方法。不是最好的运行时间，但仍然是合理的 0.65 秒与使用 Convert-to-String 方法的 2.46 秒（180000 位）。
This method computes the integer part of the base-10 logarithm from the given value. However, instead of using loop-divide, it uses a technique similar to Exponentiation by Squaring.
此方法根据给定值计算以 10 为底的对数的整数部分。但是，它没有使用循环除法，而是使用类似于乘方取幂的技术。
Here is a crude implementation that achieves the runtime mentioned earlier:
这是一个实现前面提到的运行时的粗略实现：
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 will helps.
希望这会有所帮助。
