使用长除法求平方根

Question

所以这是 class 作业。我似乎无法理解长除法的复杂性。坦率地说，我什至不确定如何开始解决算法以使其执行我需要的操作。

对于第二部分，我们必须接受用户输入的数字，并对用户输入的具体小数位数求平方根。我需要复制求平方根的算法可以找到 here.

以下是我目前的情况（显然到目前为止没有取得太大进展）：

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);

}
}

此所需输出的示例是：

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.

显然，这需要对任何数字输入和用户希望平方根返回的任何小数位数有效。

因此，如果有人可以帮助我向我解释如何在 Java 中进行长除法，或者留下带有或不带注释的代码，将不胜感激！

Answer 1

我已经为您的程序创建了一个工作版本。您提供的说明为我们提供了我在代码中使用的一系列步骤。

如程序所示，我们首先找到整数部分并尝试找到 "closest" 方块。在给定的示例中，"closest" 与 40 的平方是 36。让我们分步进行。

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

该代码将只给我们整数部分，以便我们可以找到最近的正方形，我们通过运行一个循环（您可以通过二分搜索来改进）来完成，如下所示：

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

它的作用是检查每个数字，直到我们找到的整数部分。第一个大于整数部分的数字表示我们已经越界了。我们向后退一步，那是最近的广场。确保你创建了一个变量来记住小数点的位置：

int decimalIx = ans.length();

第 2 步：求小数。

该过程要求我们跟踪到目前为止找到的数字，以及从整数部分中减去的最近平方的余数。在找到 40 的情况下，余数是 40 - 36 = 4。我们目前的答案是 6。

该过程要求我们将当前答案加倍并乘以 10，实际上是将当前答案乘以 20。如果我们这样做，我们将得到 120。为简单起见，我们称其为 A。然后，我们必须找到一个数字添加到 A 中，使得 (A + digit) * digit < remainder * 100。具体来说，我们必须找到从 1 到 9 的某个数字，使得 (120 + (some digit)) * some数字 < 4*100。

我们可以使用 decimals 参数来限制我们的循环，像这样：

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;
          }
     }
}

现在剩下的就是发回答案：

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

这是完整的代码。

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;
    }

使用长除法求平方根

Finding square roots using long division method

java

algorithm

square-root