我需要计算
BigInteger99212344999941234567890123456789020我需要这样做对于具有
BigInteger的
184948。 我怎样才能快速且可扩展地做到这一点？
转换为字符串方法很慢：
public String getWritableNumber(BigInteger number) {
// Takes over 30 seconds for 184948 decimal digits
return "10^" + (number.toString().length() - 1);
}
这种 loop-devide-by-ten 方法甚至更慢：
public String getWritableNumber(BigInteger number) {
int digitSize = 0;
while (!number.equals(BigInteger.ZERO)) {
number = number.divide(BigInteger.TEN);
digitSize++;
}
return "10^" + (digitSize - 1);
}
有没有更快的方法？
这是基于 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");
}
这可以在不到一秒的时间内检查
BigInteger184,948这看起来正在发挥作用。我还没有运行详尽的测试，也没有运行任何时间测试，但它似乎有一个合理的运行时间。
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 秒以下。
我认为您可以使用 bitLength() 获取 log2 值，然后 将基数更改为 10。
但是，结果可能有一位数的错误，所以这只是一个近似值。
但是，如果可以接受，您始终可以在结果上加 1 并将其限制为“最多”。或者，减去 1，并得到 至少。
BigInteger转换为
BigDecimalanswer来计算位数。这似乎比使用
BigInteger.toString() 更有效，因为这将为 String private static int numberOfDigits(BigInteger value) {
return significantDigits(new BigDecimal(value));
}
private static int significantDigits(BigDecimal value) {
return value.scale() < 0
? value.precision() - value.scale()
: value.precision();
}
此方法根据给定值计算以 10 为底的对数的整数部分。但是，它没有使用循环除法，而是使用类似于平方求幂的技术。
这是一个实现前面提到的运行时的粗略实现：
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;
}
希望这会有所帮助。
显然你可以将它转换成字符串并检查长度，但这就是......我能说什么......丑陋。
如果不是
BigIntMath.floor(Math.log10(number))BigIntn1e161e16n * 16 + Math.floor(Math.log10(remainder))unsigned approx_digits_in_base(unsigned bits, unsigned base){
// approximate the number of digits for a given number of bits (suitable to malloc).
static const unsigned char logs[] = {40, 63, 80, 92, 103, 112, 120, 126, 132, 138, 143, 148, 152, 156, 160, 163, 166, 169, 172, 175, 178, 180, 183, 185, 188, 190, 192, 194, 196, 198, 200, 201, 203, 205, 206, 208, 209, 211, 212, 214, 215, 217, 218, 219, 220, 222, 223, 224, 225, 226, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238};
return 2 + !bits + bits * 40 / logs[base - 2]; // including a bit for the sign.
}