How to Find the Integer Square Root of a Number in Python?

Barbara Streisand
Release: 2024-10-31 13:12:47
Original
345 people have browsed it

How to Find the Integer Square Root of a Number in Python?

Finding Integer Square Roots in Python

Python provides several ways to compute the square root of a number. However, none of these methods directly return an integer square root without approximations or exceptions.

One approach, as suggested in the initial code snippet, is to use the math.sqrt() function and round the result to the nearest integer. However, this approach may not be exact for large integers.

A more accurate method involves using Newton's method, which is an iterative technique for finding roots of equations. The following Python function implements Newton's method for integer square roots:

<code class="python">def isqrt(n):
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x</code>
Copy after login

This function initializes two variables, x and y, and iteratively updates them until convergence. x represents the best estimate of the integer square root, while y is an updated estimate that incorporates both the value of x and the integer division of n by x. The iteration stops when y becomes less than x, indicating that further refinement is unnecessary.

The returned value of isqrt() is the largest integer for which its square does not exceed n. To verify if the result is an exact integer square root, multiply the result with itself and compare it to n. Note that this function handles non-perfect squares by design, raising no exceptions.

While several other algorithms exist for calculating integer square roots, Newton's method is generally considered to offer a balance of accuracy, speed, and simplicity.

The above is the detailed content of How to Find the Integer Square Root of a Number in Python?. For more information, please follow other related articles on the PHP Chinese website!

source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Articles by Author
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!