Целочисленный квадратный корень (Eylkcnvlyuudw tfg;jgmudw tkjyu,)

Перейти к навигации Перейти к поиску

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

Например, поскольку и .

Одним из путей вычисления и — использование метода Ньютона для поиска решения уравнения , используя итеративную формулу[1][2]

Последовательность сходится квадратично к при [3]. Можно доказать, что если выбрано в качестве начального значения, можно останавливаться, как только

,

чтобы обеспечить, что

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

[править | править код]

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

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

можно показать, что последовательность достигает за конечное число итераций [4].

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

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

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

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

[править | править код]

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

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

[править | править код]

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

,

который обеспечивает, что в вышеприведённом алгоритме.

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

Примечания

[править | править код]
  1. Метод называется иногда «вавилонским»
  2. Fred Akalin, Computing the Integer Square Root Архивная копия от 17 октября 2016 на Wayback Machine, 2014
  3. S. G. Johnson, MIT Course 18.335, Square Roots via Newton’s Method Архивная копия от 9 октября 2015 на Wayback Machine, February 4, 2015
  4. Henri Cohen. A Course in Computational Algebraic Number Theory. — Berlin,Heidelberg, New York: Springer, 1996. — Т. 138. — С. 38-49. — (Graduate texts in mathematics). — ISBN 3-540-55640-0.