sqrtx
1# @leet start 2class Solution: 3 def mySqrt(self, x: int) -> int: 4 r""" 5 To calculate the square root of a given number rounded down, we can 6 use Newton's method. 7 The algorithm starts with a guess of $x_1 \gt 0$ and iteratively guesses 8 an improved square root. 9 $$ 10 x_{n+1} = \frac{1}{2} \left( x_n + \frac{a}{x_n} \right) 11 $$ 12 13 We start out by checking if x is 1 or 0, since that means its square root 14 would be 1 or 0. 15 16 Then, the algorithm figures out a current and next guess for the square 17 root. The next guess is (curr + x / curr) / 2. If the next guess is 18 sufficiently far away from the current number, we continue on the loop 19 making curr into the next guess and calculating the next guess. 20 If there's not enough progress made during the iteration, we return 21 the next guess. 22 """ 23 if x < 2: 24 return x 25 26 x0 = x 27 x1 = (x0 + x / x0) / 2 28 while abs(x0 - x1) >= 1: 29 print(x0, x1) 30 x0 = x1 31 x1 = (x0 + x / x0) / 2 32 return int(x1) 33 34 35# @leet end 36 37 38def test(): 39 assert 2 + 2 == 4
class
Solution:
3class Solution: 4 def mySqrt(self, x: int) -> int: 5 r""" 6 To calculate the square root of a given number rounded down, we can 7 use Newton's method. 8 The algorithm starts with a guess of $x_1 \gt 0$ and iteratively guesses 9 an improved square root. 10 $$ 11 x_{n+1} = \frac{1}{2} \left( x_n + \frac{a}{x_n} \right) 12 $$ 13 14 We start out by checking if x is 1 or 0, since that means its square root 15 would be 1 or 0. 16 17 Then, the algorithm figures out a current and next guess for the square 18 root. The next guess is (curr + x / curr) / 2. If the next guess is 19 sufficiently far away from the current number, we continue on the loop 20 making curr into the next guess and calculating the next guess. 21 If there's not enough progress made during the iteration, we return 22 the next guess. 23 """ 24 if x < 2: 25 return x 26 27 x0 = x 28 x1 = (x0 + x / x0) / 2 29 while abs(x0 - x1) >= 1: 30 print(x0, x1) 31 x0 = x1 32 x1 = (x0 + x / x0) / 2 33 return int(x1)
def
mySqrt(self, x: int) -> int:
4 def mySqrt(self, x: int) -> int: 5 r""" 6 To calculate the square root of a given number rounded down, we can 7 use Newton's method. 8 The algorithm starts with a guess of $x_1 \gt 0$ and iteratively guesses 9 an improved square root. 10 $$ 11 x_{n+1} = \frac{1}{2} \left( x_n + \frac{a}{x_n} \right) 12 $$ 13 14 We start out by checking if x is 1 or 0, since that means its square root 15 would be 1 or 0. 16 17 Then, the algorithm figures out a current and next guess for the square 18 root. The next guess is (curr + x / curr) / 2. If the next guess is 19 sufficiently far away from the current number, we continue on the loop 20 making curr into the next guess and calculating the next guess. 21 If there's not enough progress made during the iteration, we return 22 the next guess. 23 """ 24 if x < 2: 25 return x 26 27 x0 = x 28 x1 = (x0 + x / x0) / 2 29 while abs(x0 - x1) >= 1: 30 print(x0, x1) 31 x0 = x1 32 x1 = (x0 + x / x0) / 2 33 return int(x1)
To calculate the square root of a given number rounded down, we can use Newton's method. The algorithm starts with a guess of $x_1 \gt 0$ and iteratively guesses an improved square root. $$ x_{n+1} = \frac{1}{2} \left( x_n + \frac{a}{x_n} \right) $$
We start out by checking if x is 1 or 0, since that means its square root would be 1 or 0.
Then, the algorithm figures out a current and next guess for the square root. The next guess is (curr + x / curr) / 2. If the next guess is sufficiently far away from the current number, we continue on the loop making curr into the next guess and calculating the next guess. If there's not enough progress made during the iteration, we return the next guess.
def
test():