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

Целочисленный квадратный корень (isqrt) натурального числа n — это положительное число m, которое равно наибольшему целому числу, меньшему либо равному квадратному корню из n,

isqrt(n)=n.
  Например, isqrt(27)=5 поскольку 55=2527 и 66=36>27.

Алгоритм


 Одним из путей вычисления n и isqrt(n) — использование метода Ньютона для поиска решения уравнения x2n=0, используя итеративную формулу

xk+1=12(xk+nxk),k0,x0>0.
  Последовательность {xk} сходится квадратично к n при k. Можно доказать, что если x0=n выбрано в качестве начального значения, можно останавливаться, как только
|xk+1xk|<1
, чтобы обеспечить, что xk+1=n.

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


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

xk+1=12(xk+nxk),k0,x0>0,x0Z.
  Основываясь на факте, что

12(xk+nxk)=12(xk+nxk),
  можно показать, что последовательность достигает n за конечное число итераций .
 Однако n не обязательно будет неподвижной точкой итеративной формулы, приведённой выше. Можно показать, что n будет неподвижной точкой тогда и только тогда, когда n+1 не является полным квадратом. Если n+1 является полным квадратом, последовательность не сходится, а переходит в цикл длины два, поочерёдно меняя n и n+1. Для прекращения работы достаточно проверить, что либо последовательность сходится (повторение предыдущего значения), либо что следующее значение ровно на единицу больше текущего, в последнем случае новое значение отбрасывается.

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


 Если \texttt* означает умножение, \texttt\<\< означает сдвиг влево, а \texttt\>\> — логический сдвиг вправо, рекурсивный алгоритм поиска целочисленного квадратного корня из любого натурального числа следующий:
 \textttfunction integerSqrt(n):\\\texttt    if n \textless 0:\\\texttt        error ``\textttintegerSqrt \textttработает \textttтолько \textttс \textttнеотрицательным \textttвходом''\\\texttt    else if n \textless 2:\\\texttt        return n\\\texttt    else:\\\texttt        smallCandidate = integerSqrt(n \textgreater\textgreater 2) \textless\textless 1\\\texttt        largeCandidate = smallCandidate + 1\\\texttt        if largeCandidate*largeCandidate \textgreater n:\\\texttt            return smallCandidate\\\texttt        else:\\\texttt            return largeCandidate
 Или итерации вместо рекурсии:
 \textttfunction integerSqrt(n):\\\texttt    if n \textless 0:\\\texttt        error ``\textttintegerSqrt \textttработает \textttтолько \textttс \textttнеотрицательным \textttвходом''\texttt     \\\texttt    \# Находим наибольший сдвиг.\\\texttt    shift = 2\\\texttt    nShifted = n \textgreater\textgreater shift\\\texttt    while nShifted ≠ 0 and nShifted ≠ n:\\\texttt        shift = shift + 2\\\texttt        nShifted = n \textgreater\textgreater shift\\\texttt    shift = shift - 2\\\texttt    \\\texttt    \# Находим цифры результата.\\\texttt    result = 0\\\texttt    while shift ≥ 0:\\\texttt        result = result \textless\textless 1\\\texttt        candidateResult = result + 1\\\texttt        if candidateResult*candidateResult ≤ n \textgreater\textgreater shift:\\\texttt            result = candidateResult\\\texttt        shift = shift - 2\\\texttt   \\\texttt    return result

Расчётная область


 Хотя n является иррациональным числом для большинства значений n, последовательность {xk} содержит только рациональные члены, если x0 рационально. Таким образом, используя этот метод, нет необходимости выходить за пределы поля рациональных чисел, чтобы вычислить isqrt(n), что имеет некоторое теоретическое преимущество.

Критерий остановки


 Можно показать, что c=1 является наибольшим числом для критерия остановки
 $$|x_{k+1} - x_{k}| < c\$$, который обеспечивает, что $\lfloor x_{k+1} \rfloor=\lfloor \sqrt n \rfloor$ в вышеприведённом алгоритме.
 В приложениях, использующих отличные от рациональных чисел форматы (например, плавающую запятую), константу остановки следует выбрать меньшей единицы, чтобы избежать ошибок округления.