Целочисленный квадратный корень

Одним из путей вычисления ${\displaystyle {\sqrt {n}}}$ и ${\displaystyle {\mbox{isqrt}}(n)}$ — использование метода Ньютона для поиска решения уравнения ${\displaystyle x^{2}-n=0}$ , используя итеративную формулу^[1][2]

${\displaystyle {x}_{k+1}={\frac {1}{2}}\left(x_{k}+{\frac {n}{x_{k}}}\right),\quad k\geq 0,\quad x_{0}>0.}$

Последовательность ${\displaystyle \{x_{k}\}}$ сходится квадратично к ${\displaystyle {\sqrt {n}}}$ при ${\displaystyle k\to \infty }$ ^[3]. Можно доказать, что если ${\displaystyle x_{0}=n}$ выбрано в качестве начального значения, можно останавливаться, как только

${\displaystyle |x_{k+1}-x_{k}|<1}$ ,

чтобы обеспечить, что ${\displaystyle \lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n}}\rfloor .}$

Использование только целочисленного деления

Для вычисления ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$ для очень больших целых чисел n можно использовать частное деления с остатком при обеих операциях деления. Преимуществом является использование только целых чисел для каждого промежуточного значения, что освобождает от использования представления чисел в виде чисел с плавающей запятой. Это эквивалентно использованию итеративной формулы

${\displaystyle {x}_{k+1}=\left\lfloor {\frac {1}{2}}\left(x_{k}+\left\lfloor {\frac {n}{x_{k}}}\right\rfloor \right)\right\rfloor ,\quad k\geq 0,\quad x_{0}>0,\quad x_{0}\in \mathbb {Z} .}$

Основываясь на факте, что

${\displaystyle \left\lfloor {\frac {1}{2}}\left(x_{k}+\left\lfloor {\frac {n}{x_{k}}}\right\rfloor \right)\right\rfloor =\left\lfloor {\frac {1}{2}}\left(x_{k}+{\frac {n}{x_{k}}}\right)\right\rfloor ,}$

можно показать, что последовательность достигает ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$ за конечное число итераций ^[4].

Однако ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$ не обязательно будет неподвижной точкой итеративной формулы, приведённой выше. Можно показать, что ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$ будет неподвижной точкой тогда и только тогда, когда ${\displaystyle n+1}$ не является полным квадратом. Если ${\displaystyle n+1}$ является полным квадратом, последовательность не сходится, а переходит в цикл длины два, поочерёдно меняя ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$ и ${\displaystyle \lfloor {\sqrt {n}}\rfloor +1}$ . Для прекращения работы достаточно проверить, что либо последовательность сходится (повторение предыдущего значения), либо что следующее значение ровно на единицу больше текущего, в последнем случае новое значение отбрасывается.

Используя битовые операции

Если * означает умножение, << означает сдвиг влево, а >> — логический сдвиг вправо, рекурсивный алгоритм поиска целочисленного квадратного корня из любого натурального числа следующий:

function integerSqrt(n):    if n < 0:        error "integerSqrt работает только с неотрицательным входом"    else if n < 2:        return n    else:        smallCandidate = integerSqrt(n >> 2) << 1        largeCandidate = smallCandidate + 1        if largeCandidate*largeCandidate > n:            return smallCandidate        else:            return largeCandidate

Или итерации вместо рекурсии:

function integerSqrt(n):    if n < 0:        error "integerSqrt работает только с неотрицательным входом"         # Находим наибольший сдвиг.    shift = 2    nShifted = n >> shift    while nShifted ≠ 0 and nShifted ≠ n:        shift = shift + 2        nShifted = n >> shift    shift = shift - 2        # Находим цифры результата.    result = 0    while shift ≥ 0:        result = result << 1        candidateResult = result + 1        if candidateResult*candidateResult ≤ n >> shift:            result = candidateResult        shift = shift - 2       return result

Хотя ${\displaystyle {\sqrt {n}}}$ является иррациональным числом для большинства значений ${\displaystyle n}$ , последовательность ${\displaystyle \{x_{k}\}}$ содержит только рациональные члены, если ${\displaystyle x_{0}}$ рационально. Таким образом, используя этот метод, нет необходимости выходить за пределы поля рациональных чисел, чтобы вычислить ${\displaystyle {\mbox{isqrt}}(n)}$ , что имеет некоторое теоретическое преимущество.

Можно показать, что ${\displaystyle c=1}$ является наибольшим числом для критерия остановки

${\displaystyle |x_{k+1}-x_{k}|<c\ }$ ,

который обеспечивает, что ${\displaystyle \lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n}}\rfloor }$ в вышеприведённом алгоритме.

В приложениях, использующих отличные от рациональных чисел форматы (например, плавающую запятую), константу остановки следует выбрать меньшей единицы, чтобы избежать ошибок округления.

• Методы вычисления квадратных корней

• A geometric view of the square root algorithm