# 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. Commented Dec 15, 2020 at 16:05
• @superbrain Thanks. I have added limit in the problem description. Commented Dec 15, 2020 at 16:12
• Why keep the source of the problem secret? Commented Dec 15, 2020 at 16:16
• My bad @superbrain lol Commented Dec 15, 2020 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. Commented Dec 16, 2020 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)? Commented Dec 16, 2020 at 5:16
• @KellyBundy As I said, each division is $O(n)$, and there are about $O(\log{n})$ of them.
– vnp
Commented Dec 16, 2020 at 5:18
• Isn't each division O(log n)? Commented Dec 16, 2020 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
Commented Dec 16, 2020 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. Commented Dec 16, 2020 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? Commented Dec 16, 2020 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. Commented Dec 16, 2020 at 19:48
• Oops, I meant bitLength. Commented Dec 16, 2020 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. Commented Dec 16, 2020 at 20:07
• Surely it has the bit length already stored and wouldn't go and calculate it? Commented Dec 16, 2020 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.