# How can we optimizing Java BigInteger operations?

### Problem

Reduce the number to 1 in a minimal number of steps, following the rules:

• If the number is even, divide it by 2.
• Otherwise, increment or decrement it by 1.

Limit: s can be up to 309 digits long.

### Solution

public static int solution(String s) {
BigInteger n = new BigInteger(s);
BigInteger one = BigInteger.ONE;
BigInteger two = BigInteger.TWO;
BigInteger four = new BigInteger("4");
int count = 0;

while (n.compareTo(one) == 1) {
count++;

if( n.and(one).intValue() == 0 )
n = n.divide(two);
else if ( n.intValue() == 3 || n.mod(four).intValue() == 1)
n = n.subtract(one);
else
}

return count;
}


Is there a better way to do things binary-operations-wise for this problem?

At the moment the choice I am making among these functions:

• use n.byteValue() to compare with the integer,
• or use function n.equals().

What more can we improve?

Follow-up question posted here

• Limits and link to the problem please. Dec 15 '20 at 16:05
• @superbrain Thanks. I have added limit in the problem description. Dec 15 '20 at 16:12
• Why keep the source of the problem secret? Dec 15 '20 at 16:16
• My bad @superbrain lol Dec 15 '20 at 16:58
• Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see What should I do when someone answers my question? as well as what you may and may not do after receiving answers. Dec 16 '20 at 8:29

Division of the big integers is a very expensive operation. Even a division by 2 is linear in terms of its length: all bits must be shifted. The overall complexity is $$\O(n \log{n})\$$.

A natural desire is to not do arithmetics at all, but simulate it. Convert the bigint to byte array, and inspect bits, pretending that you perform arithmetics. In broad strokes, run the loop (starting with cursor = 0) until the number is exhausted:

if bit(cursor) == 0
// simulate division
increment counter
else
peek next_bit
if next_bit == 0
// simulate subtraction
increment counter by 2
else
while next_bit == 1
increment counter
peek next_bit
set bit at cursor to 1



This touches each bit just once, driving the complexity down to $$\O(n)\$$. Care must be taken to correctly terminate the loop.

• Can you explain how theirs is O(n log n)? Dec 16 '20 at 5:16
• @KellyBundy As I said, each division is $O(n)$, and there are about $O(\log{n})$ of them.
– vnp
Dec 16 '20 at 5:18
• Isn't each division O(log n)? Dec 16 '20 at 5:19
• @KellyBundy Perhaps me being sloppy. To quote myself in terms of its length : $n$ in this analysis is not the bigint value, but its length; the number of bits.
– vnp
Dec 16 '20 at 6:16
• This provides another dimension to solve the problem but looks a bit complicated, may be because I have not worked with Bits. But thank you @vnp for the perspective. Dec 16 '20 at 10:52

# Divide by 2

As implemented, the even-test and divide by two operations is very inefficient.

BigInteger provides a getLowestSetBit() function, which returns "the index of the rightmost (lowest-order) one bit"

So if n.getLowestSetBit() returns 12, you can evenly divide the value by 2 a total of twelve times, before the least significant bit is set. Instead of actually doing the division by 2 that many times, the shiftRight(int n) function should be used:

   while (n.compareTo(one) == 1) {

int zeros = n.getLowestSetBit();
if (zeros > 0) {
n = n.shiftRight(zeros);
count += zeros;
} else {
count++;
if ( n.intValue() == 3 || n.mod(four).intValue() == 1)
n = n.subtract(one);
else
}
}


# Mod-4

Using n.mod(four).intValue() == 1 to test whether the value should be incremented or decremented is also horribly inefficient. Java must actually compute the modulo-4 remainder of the entire number; expecting it to optimize n.mod(four).intValue() == 1 into the much faster n.and(three).intValue() == 1 is expecting a lot from the optimizer.

But even computing n.and(three) is too much work! We know n is larger than 1, and that bit #0 is set. If bit #1 is set, then n % 4 == 3; if bit #1 is not set, then n % 4 == 1. And BigInteger also provides the testBit(int n) function:

          if ( n.intValue() == 3 || !n.testBit(1))
n = n.subtract(one);
else
}


# Possible Bug

n.intValue() == 3

Since n can have over 300 digits, at any point in the process, the value of n can easily overflow an integer:

Consider the 33-bit value 0x100000003. The number is not 3, but the intValue() of the number is 3.

You probably want to explicitly test for value BigInteger(3). Since comparing the entire value may be slower than testing a single bit, you may want to reorder the test to check the bit first.

          if ( !n.testBit(1) || n.equals(three) )
n = n.subtract(one);
else
}

• Maybe n.bitCount() == 2 would be a fast "equals three" test? Dec 16 '20 at 19:06
• @superbrain Hardly. Counting number of bits different from the sign bit is not likely a fast operation. Besides, it is wrong: new BigInteger("5").bitCount() == 2. Dec 16 '20 at 19:48
• Oops, I meant bitLength. Dec 16 '20 at 19:52
• @superbrain It may take many cycles to calculate n.bitLength() when you have a 300-digit value. Equality comparison usually short-circuits at the first inequality, so is likely faster. I'll admit, I haven't profiled -- I'm just guessing. n.bitLength() == 2 is true for 2, 3, -3 and -4, so that test is not an obvious "equal to 3" test, despite the problem (probably) restricting the input numbers to positive values, and the previous even-odd test indicating we are on the odd path. Dec 16 '20 at 20:07
• Surely it has the bit length already stored and wouldn't go and calculate it? Dec 16 '20 at 20:08

You wrote:

    while (n.compareTo(one) == 1) {


As the documentation says:

This method is provided in preference to individual methods for each of the six boolean comparison operators (<, ==, >, >=, !=, <=). The suggested idiom for performing these comparisons is: (x.compareTo(y) <op> 0), where <op> is one of the six comparison operators.

So that would be:

    while (n.compareTo(one) > 0) {


I also find that much easier to understand. You just need to read the three parts n, one and > and mentally move the > between the operands, i.e., n > one.