↑ arvau

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

.

The following Python programs are straightforward implementations.

Linear search using addition

Linear search.

A speed-up is achieved by using binary search instead.

Numerical examples

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:

  1. .

5. Integer "Fixed-point" Condition: At stabilization or oscillation:

  1. .

  2. .

6. Conclusion:.

Remark:

  • is a perfect square.

  • .

Example implementation

Numerical examples

The call isqrt(2000000) in 14 passes through while:

  1. .

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:

  1. ,

where the overline indicates the repeating part.

The continued fraction can be obtained by the following recurrence, which uses only integer arithmetic:

  1. ,

, 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

  1. {| 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