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

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

${\displaystyle {\mbox{isqrt}}(n)=\lfloor {\sqrt {n}}\rfloor .}$

Например, ${\displaystyle {\mbox{isqrt}}(27)=5}$ поскольку ${\displaystyle 5^{2}=25<27}$ и ${\displaystyle 6^{2}=36>27}$.

Алгоритм

Одним из путей вычисления ${\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 }$ в вышеприведённом алгоритме.

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

См. также

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