Foobar Fuel Injection Perfection efficiency I was writing this code and was using the BigInteger class because it needs to work with numbers up to 309 digits long, however it takes too long to run with numbers that are too big.  I was hoping to find a way to make it more efficient and faster, but have tried everything in my power.  Any suggestions?

public static int answer (String n) {
    return helper(new BigInteger(n));
}
public static int helper (BigInteger n) {
    BigInteger one = new BigInteger("1");
    BigInteger two = new BigInteger("2");
    BigInteger zero = new BigInteger("0");
    if (n.compareTo(two) == -1) {
        return 0;
    }
    if (n.mod(two).equals(zero)) {
        return helper(n.divide(two)) + 1;
    }
    return Math.min(helper(n.add(one).divide(two)) + 2, helper(n.subtract(one).divide(two)) + 2);
}
I was going to make this a comment, but it's easier as an answer.

Your issue very likely stems from the large amount of division / modulo, those are very slow operations, and the larger the number the slower they are.

If we consider n % 2 == 0, we can replace that modulo entirely with n &amp; 1 == 0, because the bit-pattern of 1 is 0b00000001, which means we will only be looking at the last bit of n (which happens to be the easiest way to determine even vs. odd).

Likewise, you only ever divide by 2, which can be more easily accomplished via n &gt;&gt; 1, which will shift the entire bit-array right one position (which is equivalent to a divide-by-two), accomplished via n.shiftRight(1). Between the two of these, you'll probably find that performance is increased ten-fold. You could run both of these formulas with the value of 5, for example, to prove it to yourself.

The advantage to both of these is the heavily reduced instruction cost. If we take a look at the instruction tables provided by this handy PDF, we can get a rough-estimate of the issue by looking for certain, specific instructions. These may not be the exact instructions the JVM is executing, but they'll give us a good feel for how division vs. shifting and modulo vs. anding perform.

For a modulo, in x86, this is accomplished by using the DIV instruction and checking the remainder register, so we know that we need that instruction for both comparisons.

For anding, in x86, this is accomplished by the AND instruction, and for right-bit-shifting, in x86, this is accomplished by the SHR instruction.

The first instruction I want to lookup is DIV, since we need it for all our comparisons. I'm going to reference the 'Skylake' values (since that is my processor chipset). The table for it is laid out below:

                     µops   µops                        Reciprocal
                     fused  unfused µops                through
Instruction Operands domain domain  each port   Latency put        Comments
DIV         r64      36     36      p0 p1 p5 p6 35-88   21-83


The first thing that stands out there is that the latency is 35-88 cycles. That means the result will be valid after that cycle-count passes. That's a lot.

Let's look at AND:

AND OR XOR  r,r/i    1      1      p0156        1       0.25


Oh boy, latency of 1 already. What about SHR:

SHR SHL SAR r,i      1      1      p06          1       0.5


Same thing, so that gives us an estimate that we should be seeing ~35x improvement on execution time just from these optimizations. In reality it'll be less, a good conservative estimate is ~20x, just because of overhead and I'm not certain this is the course the JVM is taking. (It could have optimized something.) If the JVM did a good optimization, and not one for the special case of 2, then you're likely looking at 2-10x improvement, but that's still a lot of improvement.



The names answer and helper are very non-descriptive. Consider naming the methods after the algorithm or based on what they do, as they're currently non-sensical.