Целочисленный квадратный корень (isqrt) натурального числа n — это положительное число m, которое равно наибольшему целому числу, меньшему либо равному квадратному корню из n,
Например, поскольку и .
Алгоритм Одним из путей вычисления и — использование метода Ньютона для поиска решения уравнения , используя итеративную формулуМетод называется иногда «вавилонским»Fred Akalin, Computing the Integer Square Root , 2014
Последовательность сходится квадратично к при S. G. Johnson, MIT Course 18.335, Square Roots via Newton’s Method , February 4, 2015. Можно доказать, что если выбрано в качестве начального значения, можно останавливаться, как только , чтобы обеспечить, что
Использование только целочисленного деления Для вычисления для очень больших целых чисел n можно использовать частное деления с остатком при обеих операциях деления. Преимуществом является использование только целых чисел для каждого промежуточного значения, что освобождает от использования представления чисел в виде чисел с плавающей запятой. Это эквивалентно использованию итеративной формулы
Основываясь на факте, что
можно показать, что последовательность достигает за конечное число итераций .
Однако не обязательно будет неподвижной точкой итеративной формулы, приведённой выше. Можно показать, что будет неподвижной точкой тогда и только тогда, когда не является полным квадратом. Если является полным квадратом, последовательность не сходится, а переходит в цикл длины два, поочерёдно меняя и . Для прекращения работы достаточно проверить, что либо последовательность сходится (повторение предыдущего значения), либо что следующее значение ровно на единицу больше текущего, в последнем случае новое значение отбрасывается.
Используя битовые операции
Если * означает умножение, << означает сдвиг влево, а >> — логический сдвиг вправо, рекурсивный алгоритм поиска целочисленного квадратного корня из любого натурального числа следующий:
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
Расчётная область Хотя является иррациональным числом для большинства значений , последовательность содержит только рациональные члены, если рационально. Таким образом, используя этот метод, нет необходимости выходить за пределы поля рациональных чисел, чтобы вычислить , что имеет некоторое теоретическое преимущество.
Критерий остановки Можно показать, что является наибольшим числом для критерия остановки , который обеспечивает, что в вышеприведённом алгоритме.
В приложениях, использующих отличные от рациональных чисел форматы (например, плавающую запятую), константу остановки следует выбрать меньшей единицы, чтобы избежать ошибок округления.
См. также Методы вычисления квадратных корней Примечания
Ссылки A geometric view of the square root algorithm
Категория:Теоретико-числовые алгоритмы Категория:Численные методы решения уравнений