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

Целочисленный квадратный корень (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$ в вышеприведённомалгоритме.
 В приложениях, использующих отличные от рациональных чисел форматы(например, плавающую запятую), константу остановки следует выбратьменьшей единицы, чтобы избежать ошибок округления.