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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Целочисленный квадратный корень (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, 2014
  3. S. G. Johnson, MIT Course 18.335, Square Roots via Newton’s Method, 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.

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]