Square root of X

subject

Enter a value greater than or equal to 2 The integer of x, Calculate and print x What is the square root of ？ Don't use  Math.sqrt(x)( The result retains only integers )

The exact results are obtained by replacing the square root function with other mathematical functions , Take the integer part as the answer ;

Approximate results are obtained by mathematical methods , Directly as the answer .

Method 1 ： Violence solution

package main;

import java.util.Scanner;

public class Text {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(" Please enter a value greater than 2 The integer of ");
        int x= sc.nextInt();
        int ans=1;
        while (true){
            if(ans*ans<=x&&(ans+1)*(ans+1)>x)
                break;
            ans++;
        }
        System.out.println(ans);
    }
}

advantage ： Easy to understand

shortcoming ： If the number entered is large , The efficiency of this method is very low .

Method 2 ： Two points search

When x≥2 when , Its integer square root must be less than x/2 And greater than 0, namely 0<a<x/2. because a It must be an integer , This problem can be translated into finding a specific value in an ordered set of integers , So you can use binary search .

The lower bound of binary search is 0, The upper bound can be roughly set to x. In each step of binary search , We just need to compare the intermediate elements mid The sum of the squares of x The size of the relationship , The range of the upper and lower bounds is adjusted by comparing the results .

package main;

import java.util.Scanner;

public class Text {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(" Please enter a value greater than 2 The integer of ");
        int x= sc.nextInt();
        int ans=-1;
        int r=x;// Upper boundary 
        int  l=0;// Lower boundary 
        while (l <= r) {// The lower boundary is larger than the upper boundary to exit the cycle 
            int mid = l + (r - l) / 2;// In the middle 
            if ((long) mid * mid <= x) {// Judge the square sum of the intermediate value x The relationship between 
                ans = mid;
                l = mid + 1;// Change lower boundary 
            } else {
                r = mid - 1;// Change the upper boundary 
            }
        }
        System.out.println(ans);
    }
}

Method 3 ： Pocket calculator algorithm

Is an exponential function  exp  Logarithmic function  ln  Instead of the square root function . We can use finite mathematical functions , Get the result we want to calculate .

 

package main;

import java.util.Scanner;

public class Test1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(" Please enter a value greater than 2 The integer of ");
        int x= sc.nextInt();
        int ans = (int) Math.exp(0.5 * Math.log(x));
        System.out.println(ans);
}
}

Method four ： Newton iteration

Ideas

Newton's iteration It is a method that can be used to quickly solve the zero point of a function .

For narrative purposes , We use it c  Represents the integer for which the square root is to be found . obviously ,c The square root of is a function y=x^2-c Zero point of . The conclusion is

package main;

import java.util.Scanner;

public class Test1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(" Please enter a value greater than 2 The integer of ");
        int x= sc.nextInt();
        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (Math.abs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        System.out.println((int)x0);
}
}