Java BigInteger, cut off last digit

Question

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

Two easy ways to do this can be :

1. Use strings, get substring and create new biginteger with the new value.
2. Use BigIntegers divide method with number 10. ( 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.

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

Others solutions are also welcome.

Answer 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)

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

Answer 2

Divide by 10 is most likely going to be faster.

Answer 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.

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.

Answer 4

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.

Answer 5

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).

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

Answer 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.

Answer 7

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

Answer 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:

/* 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.

Answer 9

if performance is crucial... don't use 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.

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