Performance Improvement For Using BigInteger While Calculating Square Root

Question

I am trying to calculate the square root of all the integers below 100 with A precision of up to 10000 digits. I already tried it using Newton's method with Big Decimal, where it eats a lot of time.

So now am using Jarvis method for finding the square root using BigInteger.(I think this method involves less number of calculations and gets rid of the maintenance of decimal digits). Even then my code takes a lot of time.The following piece of code depicts the calculations.

public class SquareRootHackerRankJarvis {
static BigInteger limit;
static BigInteger a;
static BigInteger b;

private static BigInteger squareroot(int n, int digits, BigInteger ten,
        BigInteger hundred, BigInteger five) {
    limit = ten.pow(digits + 1);
    a = BigInteger.valueOf(n * 5);
    b = BigInteger.valueOf(5);

    while (b.compareTo(limit) == -1) {
        if (a.compareTo(b) != -1) {
            a = a.subtract(b);
            b = b.add(ten);
        } else {
            a = a.multiply(hundred);
            b = (b.divide(ten)).multiply(hundred).add(five);
        }
    }

    return b.divide(hundred);
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    int P = scanner.nextInt();
    int sum = 0;
    int p = 1;
    BigInteger ten = BigInteger.valueOf(10);
    BigInteger hundred = BigInteger.valueOf(100);
    BigInteger five = BigInteger.valueOf(5);
    for (int i = 1; i <= N; i++) {
        if (p * p == i) {
            p++;
            continue;
        }
        BigInteger x = squareroot(i, P, ten, hundred, five);

        char[] digits = x.toString().toCharArray();

        for (int j = 0; j <= P - 1; j++) {
            sum += Character.getNumericValue(digits[j]);
        }
    }
    System.out.println(sum);
    scanner.close();
}}

Can anyone provided or suggestions about the proper usage of BigInteger for optimum performance?

Comments on improvement of the above algorithm are also welcomed.

Answer 1

BigInteger ten = BigInteger.valueOf(10);
BigInteger hundred = BigInteger.valueOf(100);
BigInteger five = BigInteger.valueOf(5);

Should be moved outside of the function squareroot so they are not created and initialized every time function is called. Make sure they are still accessible in this function.

BigInteger num;
BigInteger limit;
BigInteger a;
BigInteger b;

Should be created outside of the function and should be only initialized on every fucntion call.

Also following line

b = (b.divide(ten)).multiply(hundred).add(five);

can be optimized to

b = b.multiply(ten).add(five);

Answer 2

One observation beyond fast computation of numerous digits of roots of non-squares is that there are just 25 non-compound numbers from 2 to 100.

Next, in addition to introducing constants like Maciej suggested, reduce the "introduction of 0 before the trailing 5" to two operations:

static final BigInteger
    ten        = BigInteger.TEN,
    oneHundred = BigInteger.valueOf(100),
    five       = BigInteger.valueOf(  5),
    fourtyFive = BigInteger.valueOf( 45);

/** Computes <code>digits</code> decimal digits of <code>n</code>
 * <em>ignoring</em> (decimal) scaling. */
private static BigInteger sqrtDigitsJarvis(int n, int digits) {
    BigInteger
        limit = ten.pow(digits + 1),     // might be an instance data member
        a = BigInteger.valueOf(n*5L),    // la*100), 
        b = five; // BigInteger.valueOf(ib*10 - 45);
// flawed for limit < sqrt(5n)
    while (b.compareTo(limit) < 0) {
        if (0 <= a.compareTo(b)) { // each branch can be parallelised
            a = a.subtract(b);
            b = b.add(ten);
        } else {
            a = a.multiply(oneHundred);
            b = b.multiply(ten).subtract(fourtyFive);
        }
    }
    return b.divide(oneHundred);
}