Русская Википедия:Целочисленный квадратный корень
Целочисленный квадратный корень (isqrt) натурального числа n — это положительное число m, которое равно наибольшему целому числу, меньшему либо равному квадратному корню из n,
- <math>\mbox{isqrt}( n ) = \lfloor \sqrt n \rfloor.</math>
Например, <math>\mbox{isqrt}(27) = 5</math> поскольку <math>5^2 = 25 < 27</math> и <math>6^2 = 36 > 27</math>.
Алгоритм
Одним из путей вычисления <math>\sqrt{n}</math> и <math>\mbox{isqrt}( n )</math> — использование метода Ньютона для поиска решения уравнения <math>x^{2} - n = 0</math>, используя итеративную формулу[1][2]
- <math>{x}_{k+1} = \frac{1}{2}\left(x_k + \frac{ n }{x_k}\right), \quad k \ge 0, \quad x_0 > 0.</math>
Последовательность <math>\{ x_k \}</math> сходится квадратично к <math>\sqrt{n}</math> при <math>k\to \infty</math>[3]. Можно доказать, что если <math>x_{0} = n</math> выбрано в качестве начального значения, можно останавливаться, как только
- <math>| x_{k+1}-x_{k}| < 1</math>,
чтобы обеспечить, что <math>\lfloor x_{k+1} \rfloor=\lfloor \sqrt n \rfloor.</math>
Использование только целочисленного деления
Для вычисления <math>\lfloor \sqrt n \rfloor</math> для очень больших целых чисел n можно использовать частное деления с остатком при обеих операциях деления. Преимуществом является использование только целых чисел для каждого промежуточного значения, что освобождает от использования представления чисел в виде чисел с плавающей запятой. Это эквивалентно использованию итеративной формулы
- <math>{x}_{k+1} = \left\lfloor \frac{1}{2}\left(x_k + \left\lfloor \frac{ n }{x_k} \right\rfloor \right) \right\rfloor, \quad k \ge 0, \quad x_0 > 0, \quad x_0 \in \mathbb{Z}.</math>
Основываясь на факте, что
- <math>\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,</math>
можно показать, что последовательность достигает <math>\lfloor \sqrt n \rfloor</math> за конечное число итераций [4].
Однако <math>\lfloor \sqrt n \rfloor</math> не обязательно будет неподвижной точкой итеративной формулы, приведённой выше. Можно показать, что <math>\lfloor \sqrt n \rfloor</math> будет неподвижной точкой тогда и только тогда, когда <math>n + 1</math> не является полным квадратом. Если <math>n + 1</math> является полным квадратом, последовательность не сходится, а переходит в цикл длины два, поочерёдно меняя <math>\lfloor \sqrt n \rfloor</math> и <math>\lfloor \sqrt n \rfloor + 1</math>. Для прекращения работы достаточно проверить, что либо последовательность сходится (повторение предыдущего значения), либо что следующее значение ровно на единицу больше текущего, в последнем случае новое значение отбрасывается.
Используя битовые операции
Если * означает умножение, << означает сдвиг влево, а >> — логический сдвиг вправо, рекурсивный алгоритм поиска целочисленного квадратного корня из любого натурального числа следующий:
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
Расчётная область
Хотя <math>\sqrt{n}</math> является иррациональным числом для большинства значений <math>n</math>, последовательность <math>\{ x_k \}</math> содержит только рациональные члены, если <math> x_0 </math> рационально. Таким образом, используя этот метод, нет необходимости выходить за пределы поля рациональных чисел, чтобы вычислить <math>\mbox{isqrt}( n )</math>, что имеет некоторое теоретическое преимущество.
Критерий остановки
Можно показать, что <math>c=1</math> является наибольшим числом для критерия остановки
- <math>|x_{k+1} - x_{k}| < c\ </math>,
который обеспечивает, что <math>\lfloor x_{k+1} \rfloor=\lfloor \sqrt n \rfloor</math> в вышеприведённом алгоритме.
В приложениях, использующих отличные от рациональных чисел форматы (например, плавающую запятую), константу остановки следует выбрать меньшей единицы, чтобы избежать ошибок округления.
См. также
Примечания
Ссылки
Шаблон:Rq Шаблон:Теоретико-числовые алгоритмы
- ↑ Метод называется иногда «вавилонским»
- ↑ Fred Akalin, Computing the Integer Square Root, 2014
- ↑ S. G. Johnson, MIT Course 18.335, Square Roots via Newton’s Method, February 4, 2015
- ↑ Шаблон:Книга
