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

В теории чисел целочисленный квадратный корень (isqrt) из неотрицательного целого числа n — это неотрицательное целое число m, которое является наибольшим целым числом, меньшим или равным квадратному корню из n , $$\operatorname {isqrt} (n)=\lfloor {\sqrt {n}}\rfloor .$$

Например, $\operatorname {isqrt} (27)=\lfloor {\sqrt {27}}\rfloor =\lfloor 5.19615242270663...\rfloor =5.$

Вступительное замечание

Позволять $y$ и $k$ быть неотрицательными целыми числами.

Алгоритмы вычисления ( десятичное представление ) ${\sqrt {y}}$ работать вечно на каждом входе $y$ что не является идеальным квадратом .

Алгоритмы, которые вычисляют $\lfloor {\sqrt {y}}\rfloor$ не бегай вечно . Тем не менее, они способны вычислять ${\sqrt {y}}$ с любой желаемой точностью $k$.

Выбирайте любой $k$ и вычислить ${\textstyle \lfloor {\sqrt {y\times 100^{k}}}\rfloor }$.

Например (установка $y=2$): $${\begin{aligned}&k=0:\lfloor {\sqrt {2\times 100^{0}}}\rfloor =\lfloor {\sqrt {2}}\rfloor =1\\&k=1:\lfloor {\sqrt {2\times 100^{1}}}\rfloor =\lfloor {\sqrt {200}}\rfloor =14\\&k=2:\lfloor {\sqrt {2\times 100^{2}}}\rfloor =\lfloor {\sqrt {20000}}\rfloor =141\\&k=3:\lfloor {\sqrt {2\times 100^{3}}}\rfloor =\lfloor {\sqrt {2000000}}\rfloor =1414\\&\vdots \\&k=8:\lfloor {\sqrt {2\times 100^{8}}}\rfloor =\lfloor {\sqrt {20000000000000000}}\rfloor =141421356\\&\vdots \\\end{aligned}}$$

Сравните результаты с ${\sqrt {2}}=1.41421356237309504880168872420969807856967187537694...$

Оказывается, что умножение входных данных на $100^{k}$ дает точность k десятичных цифр.

Чтобы вычислить (полное) десятичное представление ${\sqrt {y}}$, можно выполнить $\operatorname {isqrt} (y)$ бесконечное число раз, увеличивая $y$ по фактору $100$ на каждом проходе.

Предположим, что в следующей программе ( $\operatorname {sqrtForever}$) процедура $\operatorname {isqrt} (y)$ уже определено и — ради аргумента — что все переменные могут содержать целые числа неограниченной величины.

Затем $\operatorname {sqrtForever} (y)$ напечатает все десятичное представление ${\sqrt {y}}$.

// Печатаем sqrt(y), не останавливаясь  void   sqrtForever  (  unsigned   int   y  )  { 	 unsigned   int   result   =   isqrt  (  y  ); 	 printf  (  "%d."  ,   результат  ); 	 // вывести результат, за которым следует десятичная точка 	 while   (  true  ) 	 // повторять вечно ... 	 { 		 y   =   y   *   100  ; 	 // теоретический пример: переполнение игнорируется 		 result   =   isqrt  (  y  ); 		 printf  (  "%d"  ,   результат   %   10  ); 	 // выводим последнюю цифру результата 	 }  } 

Вывод состоит в том, что алгоритмы, вычисляющие isqrt() вычислительно эквивалентны алгоритмам, которые вычисляют sqrt().

Основные алгоритмы

Целый квадратный корень из неотрицательного целого числа $y$ можно определить как $$\lfloor {\sqrt {y}}\rfloor =x:x^{2}\leq y<(x+1)^{2},x\in \mathbb {N}$$

Например, $\operatorname {isqrt} (27)=\lfloor {\sqrt {27}}\rfloor =5$ потому что $6^{2}>27{\text{ and }}5^{2}\ngtr 27$.

Алгоритм с использованием линейного поиска

Следующие программы на языке C представляют собой простую реализацию.

// Целочисленный квадратный корень  // (с использованием линейного поиска по возрастанию)  unsigned   int   isqrt  (  unsigned   int   y  )  { 	 // начальное занижение, L <= isqrt(y) 	 unsigned   int   L   =   0  ; 	 в то время как   ((  L   +   1  )   *   (  L   +   1  )   <=   y  ) 		 L знак   равно   L   +   1  ; 	 вернуть   Л  ;  } 

// Целочисленный квадратный корень  // (с использованием линейного поиска по убыванию)  unsigned   int   isqrt  (  unsigned   int   y  )  { 	 // начальное завышение, isqrt(y) <= R 	 unsigned   int   R   =   y  ; 	 в то время как   (  р   *   р   >   y  ) 		 р   знак равно   р   -   1  ; 	 вернуть   Р  ;  } 

Линейный поиск с использованием сложения

В приведенной выше программе (линейный поиск по возрастанию) можно заменить умножение сложением, используя эквивалентность $$(L+1)^{2}=L^{2}+2L+1=L^{2}+1+\sum _{i=1}^{L}2.$$

// Целочисленный квадратный корень  // (линейный поиск, по возрастанию) с использованием сложения  unsigned   int   isqrt  (  unsigned   int   y  )  { 	 unsigned   int   L   =   0  ; 	 беззнаковое   целое   число   =   1  ; 	 беззнаковое   целое число   d   =   3  ; 	 в то время как   (  а   <=   y  ) 	 { 		 а знак   равно   а   +   d  ; 	 // (а + 1) ^ 2 		 d   =   d   +   2  ; 		 Л   =   Л   +   1  ; 	 } 	 Вернуть   Л  ;  } 

Алгоритм, использующий бинарный поиск

Линейный поиск последовательно проверяет каждое значение, пока не достигнет наименьшего. $x$ где $x^{2}>y$.

Ускорение достигается за счет использования вместо этого двоичного поиска . Следующая C-программа является реализацией.

// Целочисленный квадратный корень (с использованием двоичного поиска)  unsigned   int   isqrt  (  unsigned   int   y  )  { 	 unsigned   int   L   =   0  ; 	 беззнаковый   интервал   M  ; 	 беззнаковый   int   R   =   y   +   1  ;      в то время как   (  L   !=   р   -   1  )      {          M   знак равно   (  L   +   р  )   /   2  ; 		 если   (  M   *   M   <=   y  ) 			 L знак   равно   M  ; 		 иначе 			 Р   =   М  ; 	 }      Вернуть   Л  ;  } 

Численный пример

Например, если вычислить $\operatorname {isqrt} (2000000)$ используя бинарный поиск, можно получить $[L,R]$ последовательность $${\begin{aligned}&[0,2000001]\rightarrow [0,1000000]\rightarrow [0,500000]\rightarrow [0,250000]\rightarrow [0,125000]\rightarrow [0,62500]\rightarrow [0,31250]\rightarrow [0,15625]\\&\rightarrow [0,7812]\rightarrow [0,3906]\rightarrow [0,1953]\rightarrow [976,1953]\rightarrow [976,1464]\rightarrow [1220,1464]\rightarrow [1342,1464]\rightarrow [1403,1464]\\&\rightarrow [1403,1433]\rightarrow [1403,1418]\rightarrow [1410,1418]\rightarrow [1414,1418]\rightarrow [1414,1416]\rightarrow [1414,1415]\end{aligned}}$$

Это вычисление занимает 21 итерацию, тогда как линейный поиск (по возрастанию, начиная с $0$) нужно 1414 шагов.

Алгоритм с использованием метода Ньютона

Один из способов расчета ${\sqrt {n}}$ и $\operatorname {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$.

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

Можно доказать что $c=1$ — максимально возможное число, для которого критерий остановки $$|x_{k+1}-x_{k}|<c$$обеспечивает $\lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n}}\rfloor$ в алгоритме выше.

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

Область вычислений

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

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

Для вычислений $\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$ за конечное число итераций.

В оригинальной версии есть $x_{k}\geq {\sqrt {n}}$ для $k\geq 1$, и $x_{k}>x_{k+1}$ для $x_{k}>{\sqrt {n}}$. Итак, в целочисленной версии имеем $\lfloor x_{k}\rfloor \geq \lfloor {\sqrt {n}}\rfloor$ и $x_{k}\geq \lfloor x_{k}\rfloor >x_{k+1}\geq \lfloor x_{k+1}\rfloor$ до окончательного решения $x_{s}$ достигается. Для окончательного решения $x_{s}$, у одного есть $\lfloor {\sqrt {n}}\rfloor \leq \lfloor x_{s}\rfloor \leq {\sqrt {n}}$ и $\lfloor x_{s+1}\rfloor \geq \lfloor x_{s}\rfloor$, поэтому критерием остановки является $\lfloor x_{k+1}\rfloor \geq \lfloor x_{k}\rfloor$.

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

Пример реализации на C

// Квадратный корень из целого числа  unsigned   int   int_sqrt  (  unsigned   int   s  )  { 	 // Ноль дает ноль      // Единица дает единицу 	 if   (  s   <=   1  )  		 return   s  ;      // Начальная оценка (должна быть слишком высокой) 	 unsigned   int   x0   =   s   /   2  ; 	 // Обновляем 	 unsigned   int   x1   =   (  x0   +   s   /   x0  )   /   2  ; 	 while   (  x1   <   x0  ) 	 // Проверка границ 	 { 		 x0   =   x1  ; 		 х1   знак равно   (  х0   +   s   /   х0  )   /   2  ; 	 } 			 Вернуть   х0  ;  } 

Численный пример

Например, если вычислить целый квадратный корень из 2000000 , используя приведенный выше алгоритм, можно получить последовательность $${\begin{aligned}&1000000\rightarrow 500001\rightarrow 250002\rightarrow 125004\rightarrow 62509\rightarrow 31270\rightarrow 15666\rightarrow 7896\\&\rightarrow 4074\rightarrow 2282\rightarrow 1579\rightarrow 1422\rightarrow 1414\rightarrow 1414\end{aligned}}$$Всего необходимо 13 итераций. Хотя метод Герона сходится квадратично близко к решению, в начале достигается точность менее одного бита на итерацию. Это означает, что выбор начальной оценки имеет решающее значение для производительности алгоритма.

быстрое вычисление целой части двоичного логарифма или длины бита (например, Когда доступно std::bit_width в C++20 ), лучше начать с $$x_{0}=2^{\lfloor (\log _{2}n)/2\rfloor +1},$$что является наименьшей степенью двух больше, чем ${\sqrt {n}}$. В примере целочисленного квадратного корня из 2000000 , $\lfloor \log _{2}n\rfloor =20$, $x_{0}=2^{11}=2048$, и результирующая последовательность $$2048\rightarrow 1512\rightarrow 1417\rightarrow 1414\rightarrow 1414.$$В этом случае необходимо всего четыре шага итерации.

Поразрядный алгоритм

Традиционный с помощью ручки и бумаги. алгоритм вычисления квадратного корня ${\sqrt {n}}$ основан на работе от более высоких цифр к меньшим, и по мере того, как каждая новая цифра выбирает самую большую, которая по-прежнему дает квадрат $\leq n$. Если остановиться после единицы, вычисленный результат будет целым квадратным корнем.

Использование побитовых операций

При работе с базой 2 выбор цифры упрощается до выбора между 0 («маленький кандидат») и 1 («большой кандидат»), а манипуляции с цифрами могут быть выражены с помощью операций двоичного сдвига. С * будучи умножением, << будучи левой сменой, и >> будучи логическим сдвигом вправо, рекурсивный алгоритм нахождения целого квадратного корня из любого натурального числа :

def   целое_sqrt  (  n  :   int  )   ->   int  :      утверждать   n   >=   0  ,   «sqrt работает только для неотрицательных входных данных»,      если   n   <   2  :          return   n      # Рекурсивный вызов:      small_cand   =   целое_sqrt  (  n   >>   2  )   <<   1      big_cand   =   small_cand   +   1      if   big_cand   *   big_cand   >   n  :          return   small_cand      else  :          return   big_cand  # эквивалентно:  def   целое_sqrt_iter  (  n  :   int  )   ->   int  :      утверждать   n   >=   0  ,   «sqrt работает только для неотрицательных входных данных»      , если   n   <   2  :          return   n      # Найти сумму сдвига. См. также [[найти первый набор]],      # сдвиг = ceil(log2(n) * 0,5) * 2 = ceil(ffs(n) * 0,5) * 2      сдвиг   =   2      while   (  n   >>   сдвиг  )   !=   0  :          сдвиг   +=   2      # Разворачиваем цикл установки битов.      result   =   0      whileshift   )   >=   0  :          result   =   result   <<   1          big_cand   =   (              result   +   1          if    что и result ^ 1 (xor), потому что последний бит всегда равен 0.          # То же ,   big_cand   *   big_cand   <=   n   >>   сдвиг  :              result   =   big_cand          сдвиг   -=   2      возвращает   результат 

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

В языках программирования

Некоторые языки программирования выделяют явную операцию для вычисления квадратного корня целого числа в дополнение к общему случаю или могут быть расширены с этой целью библиотеками.

• (isqrt x): Общий Лисп .
• math.isqrt(x): Питон .

См. также

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

Внешние ссылки

• Джарвис, Эшли Фрейзер (2006). «Квадратные корни путем вычитания» (PDF) . Математический спектр . 37 : 119–122.
• Мински, Марвин (1967). «9. Вычислимые действительные числа». Вычисления: конечные и бесконечные машины . Прентис-Холл. ISBN  0-13-165563-9 . OCLC   0131655639 .
• «Геометрический взгляд на алгоритм извлечения квадратного корня» .