Editing Integer square root (section)

==Digit-by-digit algorithm==

The traditional [[Methods of computing square roots#Digit-by-digit calculation|pen-and-paper algorithm]] for computing the square root <math>\sqrt{n}</math> is based on working from higher digit places to lower, and as each new digit pick the largest that will still yield a square <math>\leq n</math>. 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 <code>*</code> being multiplication, <code>&lt;&lt;</code> being left shift, and <code>&gt;&gt;</code> being logical right shift, a [[Recursion (computer science)|recursive]] algorithm to find the integer square root of any [[natural number]] is:

<syntaxhighlight lang="python" line="1">
def integer_sqrt(n: int) -> int:
    assert n >= 0, "sqrt works for only non-negative inputs"
    if n < 2:
        return n

    # Recursive call:
    small_cand = integer_sqrt(n >> 2) << 1
    large_cand = small_cand + 1
    if large_cand * large_cand > n:
        return small_cand
    else:
        return large_cand


# equivalently:
def integer_sqrt_iter(n: int) -> int:
    assert n >= 0, "sqrt works for only non-negative inputs"
    if n < 2:
        return n

    # Find the shift amount. See also [[find first set]],
    # shift = ceil(log2(n) * 0.5) * 2 = ceil(ffs(n) * 0.5) * 2
    shift = 2
    while (n >> shift) != 0:
        shift += 2

    # Unroll the bit-setting loop.
    result = 0
    while shift >= 0:
        result = result << 1
        large_cand = (
            result + 1
        )  # Same as result ^ 1 (xor), because the last bit is always 0.
        if large_cand * large_cand <= n >> shift:
            result = large_cand
        shift -= 2

    return result
</syntaxhighlight>

Traditional pen-and-paper presentations of the digit-by-digit algorithm include various optimizations not present in the code above, in particular the trick of pre-subtracting the square of the previous digits which makes a general multiplication step unnecessary. See {{section link|Methods of computing square roots|Binary numeral system (base 2)}} for an example.<ref>{{cite web | last= Woo |first= C |title= Square root by abacus algorithm (archived) |date = June 1985 | url = http://medialab.freaknet.org/martin/src/sqrt/sqrt.c | archive-url = https://web.archive.org/web/20120306040058/http://medialab.freaknet.org/martin/src/sqrt/sqrt.c | archive-date = 2012-03-06 }}</ref>