Wikipedia / Integer square root
Wikipedia / Integer square root
In number theory, the integer square root (isqrt) of a non-negative integer is the non-negative integer which is the greatest integer less than or equal to the square root of
Introductory remark
be non-negative integers.
Algorithms that compute (the decimal representation run forever which is not a perfect square.
do not run forever.
.
For example
gives an accuracy of decimal digits.
at each pass.
is already defined and for the sake of the argument that all variables can hold integers of unlimited magnitude.
.
The conclusion is that algorithms which compute are computationally equivalent to algorithms which compute sqrt().
is given in section Continued fraction of √c based on isqrt below.
Basic algorithms
The integer square root of a non-negative integer
.
Algorithm using linear search
The following Python programs are straightforward implementations.
Linear search using addition
Algorithm using binary search
A speed-up is achieved by using binary search instead.
Numerical examples
.
Using binary search sequence
sequence
Linear search) needs steps.
Algorithm using Newton's method
is to use Heron's method, which is a special case of Newton's method
The sequence converges quadratically.
Using only integer division
one can use the quotient of Euclidean division for both of the division operations. This has the advantage of only using integers for each intermediate value, thus making the use of floating point representations unnecessary.
. Define the integer sequence:
Proof of convergence
1. Positivity:.
2. Monotonicity:
;
.
Hence the sequence decreases.
;
.
Hence the sequence increases or stays the same.
3. Boundedness:, so it is bounded.
4. Stabilization / Oscillation: A bounded monotone integer sequence either stabilizes or oscillates between two consecutive integers:
.
5. Integer "Fixed-point" Condition: At stabilization or oscillation:
.
.
6. Conclusion:.
Remark:
is a perfect square.
.
Example implementation
Numerical examples
The call isqrt(2000000) in 14 passes through while:
.
One iteration is gained by setting x0 with the call isqrt(2000000, 1000000). Although Heron's method converges quadratically close to the solution, less than one bit precision per iteration is gained at the beginning. This means that the choice of the initial estimate is critical for the performance of the algorithm. When a fast computation for the integer part of the binary logarithm or for the bit-length is available (like e.g. n.bit_length() in Python which is the least power of two. In the example of the integer square root of In this case only four iteration steps are needed. This corresponds to the call isqrt(2000000, 2048).
Digit-by-digit algorithm
The traditional pen-and-paper algorithm. If stopping after the one's place, the result computed will be the integer square root.
Using bitwise operations
If working in base 2, the choice of digit is simplified to that between 0 (the "small candidate") and 1 (the "large candidate"), and digit manipulations can be expressed in terms of binary shift operations. With * being multiplication, being left shift, and being logical right shift, a recursive algorithm to find the integer square root of any natural number is:
Equivalent non-recursive program:
See for an example.
Karatsuba square root algorithm
The Karatsuba square root algorithm applies the same divide-and-conquer principle as the Karatsuba multiplication algorithm to compute integer square roots. The method was formally analyzed by Paul Zimmermann (1999). It recursively splits the input number into high and low halves, computes the square root of the higher half, and then determines the lower half algebraically.
Algorithm
Paul Zimmermann (1999) gives the following algorithm.
in the number of bits. Each level performs only linear-time arithmetic on half-size numbers.
Comparison with Karatsuba multiplication
Use and history
The Karatsuba-style square root is mainly used for arbitrary-precision arithmetic on very large integers, where it combines efficiently with and Karatsuba multiplication. It was first analyzed formally by Paul Zimmermann (1999). Earlier practical work includes Martin Guy (1985), and recursive versions appear in Donald Knuth (1998). Modern GMP and MPIR libraries implement similar recursive techniques.
Implementation in Python
The Python, SqrtRem. The choice of isqrt() is ad libitum.
Example usage
In programming languages
Some programming languages dedicate an explicit operation to the integer square root calculation in addition to the general case or can be extended by libraries to this end.
Continued fraction of √c based on isqrt
The computation of the simple continued fraction serving as the initial term. The algorithm generates continued fraction expansion in canonical form.
.
is a perfect square, the continued fraction terminates immediately:
Otherwise, the continued fraction is periodic:
,
where the overline indicates the repeating part.
The continued fraction can be obtained by the following recurrence, which uses only integer arithmetic:
,
, eventually one repeats, and from that point onward the continued fraction becomes periodic.
Implementation in Python
, a non-negative integer, the following program computes the simple continued fraction is computed once., where the second element is the periodic part.
Example usage
Output
{| class="wikitable"
|- | 4097280036 || colspan="2" | [64009; (1, 1999, 3, 4, 1, 499, 3, 1, 3, 3, 1, 124, ......, 3, 1, 3, 499, 1, 4, 3, 1999, 1, 128018)]period: 13,032 terms |}
See also
Notes
References
External links