CODEWITHSUNDEEP
javaalgorithmsquare-root
poseidon_rishi
poseidon_rishi

Reputation: 81

Check a number is perfect square or not

How does the following algorithm to calculate perfect square works.I am trying to use this piece of logic to calculate square root.But i don't understand how does it calculates the square root.Is there any algorithm that does the logic written in this code?

public static boolean isPerfectSquare(BigDecimal num) {
            BigDecimal squareRoot = one;
            BigDecimal square = one;
            BigDecimal i = one;
            BigDecimal newSquareRoot;
            int comparison = -1;

            while (comparison != 0) {
                if (comparison < 0) {
                    i = i.multiply(two);
                    newSquareRoot = squareRoot.add(i).setScale(0, RoundingMode.HALF_UP);
                } else {
                    i = i.divide(two);
                    newSquareRoot = squareRoot.subtract(i).setScale(0, RoundingMode.HALF_UP);
                }

                if (newSquareRoot.compareTo(squareRoot) == 0) {
                    return false;
                }

                squareRoot = newSquareRoot;
                square = squareRoot.multiply(squareRoot);
                comparison = square.compareTo(num);
            }

            return true;
        }

Upvotes: 1

Views: 638

Answers (1)

Wes Cumberland
Wes Cumberland

Reputation: 1338

I recommend you add some System.out.println() calls to watch how it's progressing yourself.

Below is the output I received after doing the same and running it on 101. It is simply increasing its guess until it is too high, then refining its guess until it finds an exact match or determines that it can't.

Its refinement process is to step down in progressively smaller steps until it is too low. Then it jumps back up (step is doubled) and it begins stepping downwards again. If it gets to a point where its step value is less than 1 then it gives up because the parameter is not a perfect square. If, at any step, the square of the guess matches the parameter, then you've found your square root and therefore you know the parameter is a perfect square. 

   1 is lower  than 101: adding    2. New guess at square root is   3 (  9)
   9 is lower  than 101: adding    4. New guess at square root is   7 ( 49)
  49 is lower  than 101: adding    8. New guess at square root is  15 (225)
 225 is higher than 101: subbing   4. New guess at square root is  11 (121)
 121 is higher than 101: subbing   2. New guess at square root is   9 ( 81)
  81 is lower  than 101: adding    4. New guess at square root is  13 (169)
 169 is higher than 101: subbing   2. New guess at square root is  11 (121)
 121 is higher than 101: subbing   1. New guess at square root is  10 (100)
 100 is lower  than 101: adding    2. New guess at square root is  12 (144)
 144 is higher than 101: subbing   1. New guess at square root is  11 (121)
 121 is higher than 101: subbing 0.5. New guess at square root is  11 (121)
101 is not a perfect square

Upvotes: 3

Related Questions