Java BigInteger，切断了最后一位数字

Fairly easy, if the BigInteger number is 543 I want it to cut off the last digit so that it is 54.

相当容易,如果BigInteger数字是543,我希望它切断最后一位数,使其为54。

Two easy ways to do this can be :

两种简单的方法可以是:

Use strings, get substring and create new biginteger with the new value.

使用字符串,获取子字符串并使用新值创建新的biginteger。

Use BigIntegers divide method with number 10. ( 543 / 10 = 54.3 => 54 )

使用数字10的BigIntegers除法。(543/10 = 54.3 => 54)

The thing is I will be performing this a lot of times with large integers of course.

问题是我当然会用大整数执行这么多次。

My guess is that playing around with strings will be slower but then again I haven't used Bigintegers so much and have no idea how expensive the "divide" operation is.

我的猜测是,用字符串来玩会慢一些,但是我又没有那么多地使用Bigintegers,也不知道“除法”操作有多昂贵。

The speed is essential here, what is the fastest way to implement this (memory is no problem only speed) ?

速度在这里是必不可少的,实现这个的最快方法是什么(内存只是速度没问题)?

Others solutions are also welcome.

其他解决方案也欢迎。

9 个解决方案

#1

Dividing by 10 is much faster than using a substring operation. Using the following benchmark, I get about 161x times (ratio is proportional to bit count)

除以10比使用子串操作快得多。使用以下基准测试,我得到大约161倍(比率与位数成比例)

    long divTime = 0;
    long substrTime = 0;
    final int bitsCount = 1000;

    for (int i = 0; i < 1000; ++i) {
        long t1, t2;
        BigInteger random = new BigInteger(bitsCount, new Random());

        t1 = System.currentTimeMillis();
        random.divide(BigInteger.TEN);
        t2 = System.currentTimeMillis();
        divTime += (t2 - t1);

        t1 = System.currentTimeMillis();
        String str = random.toString();
        new BigInteger(str.substring(0, str.length() - 1));
        t2 = System.currentTimeMillis();
        substrTime += (t2 - t1);
    }

    System.out.println("Divide: " + divTime);
    System.out.println("Substr: " + substrTime);
    System.out.println("Ratio:  " + (substrTime / divTime));

#2

Divide by 10 is most likely going to be faster.

除以10最有可能更快。

#3

If you create a BigInteger statically that has the number 10, and then use that to divide by 10, that will be potentially the fastest way to do this. It beats creating a temporary new BigInteger every time.

如果静态地创建一个具有数字10的BigInteger,然后使用它除以10,那么这可能是最快的方法。它每次都会创建一个临时的新BigInteger。

The problem with substring is that you are essentially creating a new String every single time, and that is much slower, not to mention the slowness that is iterating through a string to get its substring.

substring的问题在于你实际上每次都在创建一个新的String,而且速度要慢得多,更不用说通过字符串迭代来获取其子字符串的缓慢。

#4

The fastest possible implementation would probably be to use a data type whose internal representation uses base 10, i.e. some sort of BCD. Then, division by 10 would simply mean dropping the last byte (or even just incrementing/decrementing an index if you implement it the right way).

最快可能的实现可能是使用其内部表示使用基数10的数据类型,即某种BCD。然后,除以10将简单地意味着删除最后一个字节(或者如果以正确的方式实现它,甚至只是递增/递减索引)。

Of course, you'd have to implement all arithmetic and other operations you need from scratch, making this a lot of work.

当然,您必须从头开始实现所需的所有算术运算和其他运算,这需要做很多工作。

#5

The fastest way is dividing the number by 10 with an efficient internal division implementation. The internals of that operation are behind the scenes but certainly non-trivial since the number is stored base-2.

最快的方法是使用有效的内部划分实现将数字除以10。该操作的内部是在幕后,但肯定是非平凡的,因为数字存储在base-2。

#6

It's probably premature to even be asking this question. Do it the obvious way (divide by ten), then benchmark it, and optimize it if you need to. Converting to a string representation and back will be much slower.

甚至提出这个问题可能为时过早。以明显的方式(除以10),然后对其进行基准测试,并在需要时进行优化。转换为字符串表示并返回将慢得多。

#7

The toString() alone is probably slower than the substring.

单独的toString()可能比子字符串慢。

#8

Various people have said that dividing by 10 will be faster than converting to a string and taking the substring. To understand why, just think about the computation involved in converting from a BigInteger to a String, and vice versa. For example:

不同的人都说过,除以10将比转换为字符串和获取子字符串更快。要理解原因,只需考虑从BigInteger转换为String所涉及的计算,反之亦然。例如:

/* simplified pseudo code for converting +ve numbers to strings */
StringBuffer sb = new StringBuffer(...);
while (number != 0) {
   digit = number % 10;
   sb.append((char)(digit + '0'));
   number = number / 10;
}
return sb.toString();

The important thing to note is that converting from a number to a string entails repeatedly dividing by 10. Indeed the number of divisions is proportional to log10(number). Going in the other direction involves log10(number) multiplications. It should be obvious that this is much more computation than a single division by 10.

需要注意的重要一点是,从数字转换为字符串需要重复除以10.实际上,除法的数量与log10(数字)成正比。进入另一个方向涉及log10(数字)乘法。显而易见的是,这比单个除以10的计算要多得多。

#9

if performance is crucial... don't use java

如果性能至关重要......不要使用java

In languages which compile to machine code (for instance c or c++) the integer divide is quicker by a huge factor. String operations use (or can use) memory allocations and are therefore slow.

在编译为机器代码的语言中(例如c或c ++),整数除法的速度要快得多。字符串操作使用(或可以使用)内存分配,因此很慢。

My bet is that in java int divisions will be quicker too. Otherwise their vm implementation is really weird.

我敢打赌,在java int中,分区也会更快。否则他们的vm实现真的很奇怪。

#1