1
\$\begingroup\$

This is the follow up question of 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

The solution I have come up with is below:

import java.math.BigInteger;

public class Solution {

    public static int solution(String s) {
        BigInteger n = new BigInteger(s);

        if ( isPrimitive(n) ) {
            return longOps(0, n.longValue());
        }

        return bigIntOps(n);
    }

    public static int bigIntOps(BigInteger n) {
        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).byteValue() == 0 ){
                n = n.shiftRight(1);

                if ( isPrimitive(n) )
                    return longOps(count, n.longValue());

            } else if ( n.byteValue() == 3 || n.mod(four).byteValue() == 1)
                n = n.subtract(one);
            else
                n = n.add(one);
        }

        return count;
    }

    public static int longOps(int count, long n) {

        while (n > 1) {
            count++;

            // If number is divisible by 2
            if ( (n & 1) == 0 ) {

                // Check if the number is power of two
                if ((n&(n-1)) == 0)
                    return (int)Math.ceil(Math.log(n)/Math.log(2)) + count - 1;
                else
                    n = n >> 1;// Binary Division

            } else if ( n == 3 || n%4 == 1 )
                n--;
            else
                n++;
        }

        return count;
    }

    public static boolean isPrimitive(BigInteger n) {
        return n.compareTo(new BigInteger(String.valueOf(Long.MAX_VALUE))) < 0;
    }

}

Just some note from the source I collect:

"From the research, BigInteger operations are memory intensive and hence slow. Hence, the processing was divided into BigInteger processing and long processing.

A check was made at first to see if the number is long, and the processing was divided based on the number. Check was also made in the BigInteger processing to check if the remainder was a long, and if true, further processing was done for long processing.

I found a sweet math solution to find the 2 power of number: Math.ceil(Math.log(x)/Math.log(2))

This solution provided a single statement to find the number of steps.

Unfortunately BigInteger does not provide Math.log() functionality so this could not be implemented which could have been a great solution."

\$\endgroup\$
4
\$\begingroup\$

Log2(n)

Math.ceil(Math.log(x)/Math.log(2)) is not the fastest way of determining \$\lceil\log_2{n}\rceil\$, of an integer n. That requires converting the integer to a double, calculating the transcendental function, dividing by a constant, and then converting back to an integer, while rounding up.

Much faster is to count the number of bits in the value. \$\lceil\log_2{255}\rceil\$ is 8, and \$255 = 11111111_2\$ which has 8 bits. Exact powers of two are represented by a 1 followed by \$\log_2\$ zeros; we can fix this with a tiny amount of preprocessing: subtracting 1.

Java doesn't directly provide the number of bits in an int, but it does give us Integer.numberOfLeadingZeros(), which will we can use to get the answer:

int ceil_log_2(int n) {
    if (n < 1)
        return Integer.MIN_VALUE;
    return 32 - Integer.numberOfLeadingZeros(n - 1);
}

Java's BigInteger does give us the BigInteger.bitLength() which does directly give the number of bits required to represent the number, so will give us the answer more directly:

int ceil_log_2(BigInteger n) {
    if (n.compareTo(BigInteger.ONE) < 0)
        return Integer.MIN_VALUE;
    return n.subtract(BigInteger.ONE).bitLength();
}

bigIntOps

Even/Odd

In bigIntOps(), you are now dividing by 2 using a shiftRight(1) operation. Good; that faster than actual division.

But you are testing if the value is even by and'ing the BigInteger value with BigInteger.ONE, which likely allocates a new BigInteger value, which after being used must be garbage collected. Then, you discard all of the upper bits of the value keeping only the lower 8 with .byteValue(), and finally test if that is zero.

You could simply discard the upper bits, then and with 1, and test:

if (n.byteValue() & 1 == 0)

Now no additional BigInteger temporary object is being created, which is a win. But that is still doing unnecessary work. Java directly provides a way of testing individual bits of a BigInteger, with .testBit():

if (n.testBit(0) == false)

Looping

While the result is even, you are dividing by 2. You are doing this by shifting by 1 bit, which is faster than division, but still creates a new BigInteger object each step.

You notice this with your power-of-two test in longOps, and handle a power-of-two final value in one operation, instead of doing it in multiple steps.

Why not do that in bigIntOps as well?

BigInteger.getLowestSetBit() will tell you the number of trailing zero bits in the number, which is the number of times it can be divided evenly by 2. And this works not only for exact power-of-twos

int zeros = n.getLowestSetBit();
n = n.shiftRight(zeros)
count += zeros;

Note that this works for integers as well:

int zeros = Integer.numberOfTrailingZeros(n);
n >>= zeros;
count += zeros;

So instead of doing a bunch of divisions one at a time, you can do them in bulk. And not just for power of twos.

With the value \$3*2^{1024}\$, you'd do 1024 divisions by 2 in one step, leaving 3, which you'd then subtract 1, and then divide by 2, for 1026 steps, done in 3 calculations.

mod-4

Like the n.and(one) early, n.mod(four).byteValue() == 1 takes a possibly 1000-bit number, and does expensive modulo-4 division, and creates a new BigInteger value to store the result in, which must be allocated, and then garbage collected later. You then discard all of the upper bits, and compare the result with 1.

Again, since your doing modulo-4 math, you can do modulo-256 math first, without changing the result. n.byteValue() % 4 == 1. This means no temporary BigInteger object needs to be created.

But because you know that n is odd (or you would be doing division-by-2), the results must be 1 or 3. This means you are effectively just testing whether or not bit 1 is set. n.testBit(1) == false. Which is a lot clearer and more direct:

isPrimitive

Every time, isPrimitive is called, this statement is executed:

    return n.compareTo(new BigInteger(String.valueOf(Long.MAX_VALUE))) < 0;

You are converting Long.MAX_VALUE to a string, and then converting that back to binary form in BigInteger.

EVERY TIME!

If ever there was time to declare a constant, that was it, so it was done once, and not every call.

It could also be made more efficient by getting rid of the string intermediate step, and simple use BigInteger.valueOf(Long.MAX_VALUE).


Improved Code

import java.math.BigInteger;

public class Solution {

    private final static BigInteger MAX_LONG = BigInteger.valueOf(Long.MAX_VALUE);

    public static int solution(String s) {
        BigInteger n = new BigInteger(s);
        int count = 0;

        while (n.compareTo(MAX_LONG) > 0) {
            int zeros = n.getLowestSetBit();

            if (zeros > 0) {          // Even!
                n = n.shiftRight(zeros);
                count += zeros;
            } else {                  // Odd
                if (n.testBit(1))        // At least 2 least significant one bits
                    n = n.add(BigInteger.ONE);
                else                     // Only 1 least significant one bit
                    n = n.subtract(BigInteger.ONE);
                count++;
            }
        }

        // Value now fits with a primitive long
        long lv = n.longValue();

        while (lv > 3) {
            int zeros = Long.numberOfTrailingZeros(lv);
            if (zeros > 0) {          // Even!
                lv >>= zeros;
                count += zeros;
            } else {                  // Odd
                if (lv % 4 == 1)        // Only 1 least significant one bit
                    lv--;              
                else
                    lv++;               // At least 2 least significant one bits
                count++;
            }
        }

        if (lv == 3)
            count += 2;
        if (lv == 2)
            count += 1;

        return count;
    }
}

Notice:

  • The BigInteger loop condition loops while the value is greater than Long.MAX_VALUE, instead of while greater than 1. This naturally breaks out of the loop when the value is small enough. No need for a separate test.
  • The n.byteValue() == 3 special case is not even present in BigInteger case, since it does not change the number of steps, and adding the test will slow execution down.
  • The lv == 3 special case can been removed from the primitive loop as well, by only looping while lv > 3!

Improved Algorithm

Consider:

11111000000111111100000000111111100000000111011100000111100000111     +1
11111000000111111100000000111111100000000111011100000111100001000     / 2^3
11111000000111111100000000111111100000000111011100000111100001        -1
11111000000111111100000000111111100000000111011100000111100000        / 2^5
111110000001111111000000001111111000000001110111000001111             +1
111110000001111111000000001111111000000001110111000010000             / 2^4
11111000000111111100000000111111100000000111011100001                 -1
11111000000111111100000000111111100000000111011100000                 / 2^5
111110000001111111000000001111111000000001110111                      +1
111110000001111111000000001111111000000001111000                      / 2^3
111110000001111111000000001111111000000001111                         +1
111110000001111111000000001111111000000010000                         / 2^4
11111000000111111100000000111111100000001                             -1
11111000000111111100000000111111100000000                             / 2^8
111110000001111111000000001111111                                     +1
111110000001111111000000010000000                                     / 2^7
11111000000111111100000001                                            -1
11111000000111111100000000                                            / 2^8
111110000001111111                                                    +1
111110000010000000                                                    / 2^7
11111000001                                                           -1
11111000000                                                           / 2^6
11111                                                                 +1
100000                                                                / 2^5

How many bits were there originally? How many divide by 2's?

How many groups of 1 bits were there? How many extra operations did a single 1 bit require? How many operations did a group of more than a single 1 bit require?

Can you just count groups of 1's, single 1's, and total number of bits? Are there any special cases you need to consider, like ending with 3, or a single 0 bit?

\$\endgroup\$
3
  • \$\begingroup\$ That is a perfect example of how code review should be done! Hats off Sir. I just read your feedback and ran the code against the test codes but unfortunately it fails for BigInteger. Could you please verify by yourself as well? :) The recommendations are really great so I am making adjustments based on them and will get back to you soon. Thank you so much. I just enjoyed the experience. \$\endgroup\$ Dec 20 '20 at 6:29
  • 1
    \$\begingroup\$ Hats off? No! This is the Winter Bash! We’re supposed to be putting hats on. Re: BigIntegers not working, looks like I forgot n = at the start of the n.shiftRight(zeros) line. Performed the shift, but didn’t store the result. Sigh. \$\endgroup\$
    – AJNeufeld
    Dec 20 '20 at 6:48
  • \$\begingroup\$ LOL.. Thank you @AJNeufeld! Solution works. You definitely pointed out what I was looking for. I hope you have a great time ahead. Take care. \$\endgroup\$ Dec 20 '20 at 6:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.