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

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

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

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

Алгоритм

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

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

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

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

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

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

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

${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} .$

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

$\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 ,$

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

Однако $\lfloor {\sqrt {n}}\rfloor$ не обязательно будет неподвижной точкой итеративной формулы, приведённой выше. Можно показать, что $\lfloor {\sqrt {n}}\rfloor$ будет неподвижной точкой тогда и только тогда, когда $n+1$ не является полным квадратом. Если $n+1$ является полным квадратом, последовательность не сходится, а переходит в цикл длины два, поочерёдно меняя $\lfloor {\sqrt {n}}\rfloor$ и $\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

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

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

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

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

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

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

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

См. также

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

Ссылки

• A geometric view of the square root algorithm