69. Sqrt(x)

• categories: Code, Interview Question, leetcode, Easy
• source: https://leetcode.com/problems/sqrt
• topics: Mathematics

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

• For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Code

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
 
        y0 = x
        y1 = (y0 + x / y0) / 2
        while abs(y0 - y1) >= 1:
            y0 = y1
            y1 = (y0 + float(x) / y0) / 2
 
        return int(y1)

Explanation:

1. Problem Setup

We aim to compute the square root of a number $x$, denoted $\sqrt{x}$. This can be formulated as solving the equation:

$$f(y)=y^2-x=0$$

The solution $y$ to this equation satisfies $y=\sqrt{x}$.

2. Newton’s Method

Newton’s method is an iterative algorithm for finding roots of a differentiable function $f(y)=0$. The iteration formula is:

$$y_{n+1}=y_n-\frac{f(y_n)}{f^{\prime }(y_n)}$$

where:

• $y_n$ is the current estimate of the root,
• $f^{\prime }(y)$ is the derivative of $f(y)$.

3. Applying to $f(y)=y^2-x$

For $f(y)=y^2-x$:

$$f^{\prime }(y)=2y$$

Substituting $f(y)$ and $f^{\prime }(y)$ into the formula:

$$y_{n+1}=y_n-\frac{y_n^2-x}{2y_n}$$

Simplify:

$$y_{n+1}=\frac{2y_n-\frac{y_n^2-x}{y_n}}{2}$$ $$y_{n+1}=\frac{y_n+\frac{x}{y_n}}{2}$$

This gives the iterative formula:

$$y_{n+1}=\frac{y_n+\frac{x}{y_n}}{2}$$

4. Initial Guess

The initial guess $y0=x$ is chosen because $\sqrt{x}$ lies between $0$ and $x$ for $x>1$, making $x$ a reasonable starting point.