Finding square roots using long division method

Question

So this is for a class assignment. I can't seem to grasp the complexity of the long division. Quite frankly, I'm not even sure how to begin to solve the algorithm to make it do what I need.

For this second part, we must take in the number the user inputs and find the square root to the specific number of decimal places the user also inputs. The algorithm I need to replicate to find the square root can be found here.

The following is what I have so far (clearly not much progress was made thus far):

import java.util.*;
import java.math.*;
import TerminalIO.*;

public class squareRootProgram{

    public static float squareRootDiv(String number, int decimals){

        String[] test = new String[2];
        float answer = 0;
        String groups = "";

        test = number.split("\\.");
        test = number.split("\\.");
        System.out.println(test[0]);
        System.out.println(test[1]);

        for(int i = 0; groups != test[i].toString(); i++){
            test[i].length();
        }
        return answer;
    }

public static void main(String[]args){

    KeyboardReader reader = new KeyboardReader();
    String response = " ";
    String initNumber = " ";
    float number = 0;
    int decimals = 0;

    System.out.println("Welcome to the square root program.");
    do{
        addLine();
        System.out.print("Please enter the number of which you want to find the square root:  ");
        initNumber = reader.readLine();
        number = Float.valueOf(initNumber);
        System.out.println(number);
        System.out.print("Please enter the number of decimal places in which you want your answer:  ");
        decimals = reader.readInt();

        System.out.println("The answer provided by division algorithm is " + squareRootDiv(initNumber,decimals));

        addLine();
        System.out.print("Would you like to try another number?: ");
        response = reader.readLine();
    }while(response.compareTo("no")!=0);

}
}

An example of the required output for this is:

Welcome to the square root program.

Please enter the number of which you want to find the square root: 3.14159
Please enter the number of decimal places in which you want your answer: 3

The answer provided by division algorithm is 1.772

Would you like to try another number?: no

Thank you for using my program.

Obviously this needs to work for any number input and any amount of decimal places the user would like to have the square root returned to.

So if anyone can help me by either explaining to me how to do the long division in Java, or leaving code for it with or without comments, it would be greatly appreciated!

Answer 1

I have created a working version of your program. The instructions you provided give us a bunch of steps that I used in my code.

As the procedure indicates, we first locate the integer part and try to find the "closest" square. In the given example, the "closest" square to 40 is 36. Let's go through this in steps.

public static double squareRootDiv (String number, int decimals) {
     if (decimals <= 0) return -1; //Sanity check
     int iPart = Integer.parseInt(number.split("\\.")[0]);

That code will give us just the integer part so that we can locate the closest square, which we do by running a loop (you could improve with a binary search) like so:

int closestSquare = 0;
for (closestSquare = 0; closestSquare <= iPart; closestSquare++) {
     if (closestSquare * closestSquare > iPart) {
          closestSquare -= 1;
          break;
     }
}

What this does is check every single number up to the integer part we found. The first number that is GREATER than the integer part indicates that we have overstepped. We step backwards once and that is the closest square. Make sure you make a variable that remembers where the decimal place should go:

int decimalIx = ans.length();

Step 2: Find the decimals.

The procedure asks us to keep track of what numbers we have found so far, as well as the remainder of the closest square subtracted from the integer part. In the case of finding 40, the remainder is 40 - 36 = 4. Our current answer so far is 6.

The procedure asks that we double the current answer and multiply it by 10, effectively multiplying the current answer by 20. If we do that, we get 120. Let's call that A for simplicity's sake. Then, we must find a digit to add to A such that (A + digit) * digit < remainder * 100. In concrete terms, we have to find some digit 1 through 9 such that (120 + (some digit)) * some digit < 4*100.

We can use the decimals parameter to bound our loop, like so:

for (int i = 0; i < decimals; i++) {
     remainder *= 100;
     int base = Integer.parseInt(ans) * 20;
     //Now check digits
     for (int j = 9; j >= 0; j--) {
          int trial = (base + j) * j; //Use the digit
          if (trial < remainder) {
               //We have found the first digit that is less than the remainder!
               remainder -= trial;
               ans += j;
               break;
          }
     }
}

Now all that remains is to send back the answer:

return Double.parseDouble(ans.substring(0, decimalIx) + "." + ans.substring(decimalIx));

Here is the full code.

public static double squareRootDiv(String number, int decimals){
        if (decimals <= 0) return -1;

        String ans = "";

        int iPart = Integer.parseInt(number.split("\\.")[0]);

        int first = getNext(iPart);
        int remainder = iPart - first*first;
        ans += first;
        int decimalIx = ans.length();
        int numDecimalsNeeded = decimals - ans.length();

        for (int i = 0; i <= numDecimalsNeeded; i++) {

            remainder *= 100;
            int base = Integer.parseInt(ans) * 20;

            for (int j = 9; j >= 0; j--) {

                int trial = (base + j) * j;

                if (trial < remainder) {
                    remainder -= trial;
                    ans += j;
                    break;
                }
            }
        }



        return Double.parseDouble(ans.substring(0, decimalIx) + "." + ans.substring(decimalIx));
    }

    public static int getNext (int iPart) {
        for (int i = 0; i <= iPart; i++) {
            if (i*i > iPart) {
                return i - 1;
            }
        }
        return -1;
    }