Hello, I’m Code-knocking Xiao Huang, a Java development engineer for Unicorn Enterprise. Thank you for meeting us in the vast sea of people. As the saying goes: When your talent and ability are not enough to support your dream, please calm down and study. I hope you can study with me and work hard together to realize your own dream.

One, the introduction

In today’s daily question, there is a title:

Given a positive integer num, write a function that returns num if num is a perfect squaretrueOtherwise returnfalse. Advanced: Do not use any built-in library functions such as SQRT.Copy the code

The famous square root, the legendary Newton iteration method, this article is to see how to implement it!

Newton iteration method

Newton’s iterative method, also known as the Newton-Raphson method, was actually developed independently by Newton and Raphson (another guy whose name was obscured by Newton)

The idea proposed by Newton-Raphson method is to use the idea that tangent lines are linear approximations of curves.

Newton and Laverson thought, how easy is the tangent line, how easy is it to study, since the tangent line can approximate the curve, WHY don’t I just study the roots of the tangent line?

As shown in the figure:

For the roots of the above function, we know: x = 0

So how do you do that if you use Newtonian iteration?

  • F(x) = x * x
  • F'(x) = 2 * x

So first of all, Newton’s method would find A point, say x0, where you take A line from x0 to the curve, and it intersects at A, and you take the tangent of A to the point X1

In this case, we have three points: x1, x0 and A

Let’s call A x0, x0 times x0, and let’s call x1 x1, 0.

From the coordinates of A and x1, the slope of the line can be obtained: K = (x0 * x0)/(x0-x1)

Simplification shows that:

  • x0 – x1 = ( x0 * x0) / K
  • x0 – x1 = F(x0) / F'(x0)
  • x0 – x1 = x0 / 2
  • x1 = x0 / 2

If we do the same operation with x1, we get:

  • x2 = x1 / 2

If we do this indefinitely, we’ll end up with the formula Xn+1 = Xn / 2

As we iterate, our x value goes to 0

Square root

We said that F of x is equal to x times x, and we get Xn plus 1 is equal to Xn over 2

We think, for square roots: x * x = num

F(x) = x * x-num, F'(x) = 2 * x

Using the Newton iteration method mentioned above, we can know that: 设 F1Points for(x0, x0 * x0-num).x1Points forX1, 0.

Is:

  • K = (x0 * x0 – num) / (x0 – x1)
  • x0 – x1 = (x0 * x0 – num) / K
  • x0 – x1 = F(x0) / F'(x0)
  • x0 – x1 = x0 / 2 – num / (2 * x0)
  • x1 = x0 / 2 + num / (2 * x0)

X2 = x1/2 + num/(2 * x1)

Xn+1 = Xn / 2 + num / 2 * Xn

Simply put, take some initial value of x, iterate indefinitely, and find the square root

If F(x) = x * x-num, x = SQRT (num)

Our initial x can be directly evaluated as num, because num >= SQRT (num).

In general, it is possible to determine whether the difference between the results of two adjacent iterations is less than a minimal non-negative number, usually 1E-6 or 1E-7

Four, code implementation

	public boolean isPerfectSquare(int num) {
        if(num == 1) {return true;
        }
        double ans = num;
        double dir = num;
        while(ans * ans - dir >= 1e-6){
            ans = ans / 2 + dir / (2 * ans);
        }
        int x = (int)ans;
        return x * x == num;
    }
Copy the code

Five, the summary

Simply put, Newtonian iteration approaches a target value by iterating over and over again

Topic 1:367. Valid perfect squares

If you are interested, you can do it. At present, for this kind of square root question, the interviewer most wants to hear is Newton’s iterative method, which gives a wave of reasoning process, and directly carries the interviewer away.

Interested in the source code of small partners, you can pay attention to love knocking code yellow public number, reply: algorithm source code can be obtained algorithm source

That’s all for this installment, and the next installment will cover minimum spanning tree (Prim, Kruskal) algorithms.

I am a Java development engineer of a unicorn enterprise. I hope you can pay attention to it. If you have any questions, you can leave a message or add a private message to my wechat.