Перегляд вихідного коду сторінки Цілочисельний квадратний корінь

'''Цілочисельний квадратний корінь''' (isqrt) із [[Натуральні числа|невід’ємного цілого числа]] ''n'' — це невід’ємне ціле число ''m'', яке є [[Ціла частина числа|найбільшим цілим числом, меншим або рівним]] [[Квадратний корінь|квадратному кореню]] з ''n'' ,

: <math>\mbox{isqrt}( n ) = \lfloor \sqrt n \rfloor.</math>

Наприклад, <math>\mbox{isqrt}(27) = \lfloor \sqrt{27} \rfloor = \lfloor 5.19615242270663 ... \rfloor = 5.</math>

== Вступне зауваження ==
Нехай <math>y </math> та <math>k </math> є цілими невід’ємними числами.

Алгоритми, які обчислюють ({{iw|десяткове представлення|||Decimal representation}}) <math>\sqrt y</math> '''працюють вічно''' на кожному вході <math>y</math> який не є ідеальним квадратом.<ref>{{iw|Square root#As decimal expansions|The square roots of the perfect squares (e.g., 0, 1, 4, 9, 16) are integers. In all other cases, the square roots of positive integers are irrational numbers.}}<!-- Проблема вікіфікації: Сторінка [[:en:Square root#As decimal expansions]] перекладена як [[Квадратний корінь]], хоча хотіли [[Square root#As decimal expansions]] (SashkoR0B0T)--></ref>

Алгоритми, що обчислюють <math>\lfloor \sqrt y \rfloor</math> '''працюють не вічно'''. Проте вони можуть обчислювати <math>\sqrt y</math> з будь-якою бажаною точністю <math>k</math> .

Можна обрати будь-яке <math>k</math> і обчислити <math>\lfloor \sqrt {y \times 100^k} \rfloor</math> .

'''Наприклад''' (нехай <math>y = 2</math> ):

: <math>\begin{align}
& 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 \\
& ... \\
& k = 8: \lfloor \sqrt {2 \times 100^{8}} \rfloor = \lfloor \sqrt {20000000000000000} \rfloor = 141421356 \\
& ... \\
\end{align}</math>

Порівняйте результати з <math>\sqrt {2} = 1.41421356237309504880168872420969807856967187537694 ...</math>

Виявляється, що множення входу алгоритму на <math>100^{k}</math> дає точність <math>k</math> десяткових цифр. <ref>It is no surprise that the repeated multiplication by <math>100</math> is a feature in {{Harvtxt|Jarvis|2006}}</ref>

Щоб обчислити (повне) десяткове представлення <math>\sqrt y</math>, можна виконати <math>\mbox{isqrt}( y )</math> нескінченну кількість разів, збільшуючи <math>y</math> в 100 разів при кожному проході.

Припустимо, що в наступній програмі ( <math>\mbox{sqrtForever}</math> ) процедура <math>\mbox{isqrt}( y )</math> вже визначена, і &#x2014; заради аргументації &#x2014; що всі змінні можуть містити цілі числа необмеженої величини.

Тоді <math>\mbox{sqrtForever}(y)</math> надрукує повне десяткове представлення <math>\sqrt y</math>.<ref>The fractional part of square roots of perfect squares is rendered as <math>000...</math>.</ref><syntaxhighlight lang="c">
// Друкує sqrt(y) без зупинки
void sqrtForever( unsigned int y )
{
	unsigned int result = isqrt( y );
	printf( "%d.", result );	// print result, followed by a decimal point

	while( true )	// повторюється вічно  ...
	{
		y = y * 100;	// теоретичний приклад: переповнення ігнорується
		result = isqrt( y );
		printf( "%d", result % 10 );	// надрукувати останню цифру результата
	}
}
</syntaxhighlight>Висновок полягає в тому, що алгоритми, які обчислюють isqrt(), обчислювально еквівалентні алгоритмам, які обчислюють sqrt().<ref>see '[[Methods of computing square roots]]'.</ref>

== Основні алгоритми ==

:

=== Алгоритм з використанням лінійного пошуку ===
Наступні програми мовою C є простими реалізаціями.
 

=== Лінійний пошук ===

==== За допомогою додавання ====
У наведеній вище програмі (лінійний пошук, за зростанням) можна замінити множення на додавання, використовуючи еквівалентність

: <math>(L+1)^2 = L^2 + 2L + 1 = L^2 + 1 + \sum_{i=1}^L 2</math> .
<syntaxhighlight lang="c">
// Цілочислельний квадратний корінь
// (лінійний пошук, за зростанням) використовуючи додавання
unsigned int isqrt( unsigned int y )
{
	unsigned int L = 0;
	unsigned int a = 1;
	unsigned int d = 3;

	while( a <= y )
	{
		a = a + d;	// (a + 1)^2
		d = d + 2;
		L = L + 1;
	}

	return L;
}
</syntaxhighlight>

==== За допомогою віднімання ====
{{Harvtxt|Jarvis|2006}} опублікував метод отримання цілочисельного квадратного кореня з використанням виключно віднімання.

Розрахунок <math>\mbox{isqrt}(y)</math>, де <math>y</math> є невід’ємним цілим числом, є окремим випадком, який не потребує повного алгоритму. Досить наступної програми. <ref>The method was defined for the '''positive''' integers. Te program below computes <math>\mbox{isqrt}(0) = 0</math> as well</ref><syntaxhighlight lang="c">
// Цілочислельний квадратний корінь (використовуючи віднімання)
unsigned int isqrt( unsigned int y )
{
	unsigned int a = 5 * y;
	unsigned int b = 0;

	while( a >= b )
	{
		a = a - b;
		b = b + 10;
	}

	return b / 10;
}
</syntaxhighlight>'''Числовий приклад'''

Наприклад, якщо обчислити <math>\mbox{isqrt}( 200 )</math> використовуючи метод «віднімання», отримуємо <math>[a,b]</math> послідовність

: <math>\begin{align}
& [1000,0] \rightarrow [990,10] \rightarrow [980,20] \rightarrow [960,30] \rightarrow [930,40] \rightarrow [890,50] \rightarrow [840,60] \rightarrow [780,70] \rightarrow [710,80] \\
& \rightarrow [630,90] \rightarrow [540,100] \rightarrow [440,110] \rightarrow [330,120] \rightarrow [210,130] \rightarrow [80,140].
\end{align}</math>
: <math>140 / 10 = 14 = \lfloor \sqrt{200} \rfloor</math>

Це обчислення займає 14 кроків ітерації, як і лінійний пошук (за зростанням, починаючи з <math>0</math> ).

=== Алгоритм із використанням бінарного пошуку ===
[[Двійковий пошук|Лінійний пошук]] послідовно перевіряє кожне значення, доки воно не досягне найменшого <math>x</math> де <math>x^2 > y</math> .

Прискорення досягається за допомогою [[Двійковий пошук|двійкового пошуку]]. Наступна програма мово C є реалізацією.<syntaxhighlight lang="c">
// Цілочисильний квадратний корінь (використовуючи бінарний пошук)
unsigned int isqrt( unsigned int y )
{
	unsigned int L = 0;
	unsigned int M;
	unsigned int R = y + 1;

  while( L != R - 1 )
  {
    M = (L + R) / 2;

		if( M * M <= y )
			L = M;
		else
			R = M;
	}

  return L;
}
</syntaxhighlight>'''Числовий приклад'''

Наприклад, якщо обчислити <math>\mbox{isqrt}( 2000000 )</math> використовуючи двійковий пошук, можна отримати <math>[L,R]</math> послідовність

: <math>\begin{align}
& [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{align}</math>

Це обчислення займає 21 крок ітерації, тоді як лінійний пошук (за зростанням, починаючи з <math>0</math> ) потрібно {{Val|1414}} кроків.

== Алгоритм з використанням методу Ньютона ==
Один спосіб розрахунку <math>\sqrt{n}</math> і <math>\mbox{isqrt}( n )</math> полягає у використанні {{iw|Методи обчислення квадратних коренів|методу Герона||Methods_of_computing_square_roots}}, який є окремим випадком [[Метод Ньютона|методу Ньютона]], щоб знайти розв’язок рівняння <math>x^{2} - n = 0</math>, за даною ітераційною формулою

: <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> .

=== Критерій зупинки ===
Можна довести  це <math>c=1</math> є найбільшим можливим числом, для якого критерій зупинки

: <math>|x_{k+1} - x_{k}| < c</math>

забезпечує <math>\lfloor x_{k+1} \rfloor=\lfloor \sqrt n \rfloor</math> в наведеному вище алгоритмі.

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

=== Область обчислень ===
Хоча <math>\sqrt{n}</math> для багатьох <math>n</math> є [[Ірраціональні числа|ірраціональним]], послідовність <math>\{ x_k \}</math> містить лише [[Раціональне число|раціональні]] значення, коли <math> x_0 </math> є раціональним. Таким чином, за допомогою цього методу немає необхідності виходити з [[Поле (алгебра)|поля]] раціональних чисел для обчислення <math>\mbox{isqrt}( n )</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> протягом скінченної кількості ітерацій.

У оригінальній версії дано <math>{x}_{k}\ge \sqrt n</math> для <math>k \ge 1</math>, і <math>{x}_{k}> {x}_{k+1}</math> для <math>{x}_{k}> \sqrt n</math> . Отже, у цілочисельній версії є <math>\lfloor {x}_{k}\rfloor \ge \lfloor\sqrt n\rfloor</math> і <math>{x}_{k}\ge \lfloor {x}_{k}\rfloor > {x}_{k+1} \ge \lfloor {x}_{k+1}\rfloor </math> поки остаточне рішення <math> {x}_{s}</math> не буде досягнуто. Для остаточного рішення <math> {x}_{s}</math> виконується <math>\lfloor \sqrt n\rfloor\le\lfloor {x}_{s}\rfloor \le \sqrt n</math> і <math>\lfloor{x}_{s+1}\rfloor \ge \lfloor{x}_{s}\rfloor </math>, тому критерій зупинки такий <math>\lfloor{x}_{k+1}\rfloor \ge \lfloor{x}_{k}\rfloor </math>.

Однак, <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> замість того, щоб сходитись.

=== Приклад реалізації на C ===
<syntaxhighlight lang="c">
// Ціллочисельний квадратний корінь
unsigned int int_sqrt ( unsigned int s )
{
	unsigned int x0 = s / 2;			// Початкова оцінка
	            			// Уникнути переповнгення коли s є максимальним значенням, яке можна представити value

	// Перевірка
	if ( x0 != 0 )
	{
		unsigned int x1 = ( x0 + s / x0 ) / 2;	// Оновлення
		
		while ( x1 < x0 )				// Це також перевірка цикла
		{
			x0 = x1;
			x1 = ( x0 + s / x0 ) / 2;
		}
		
		return x0;
	}
	else
	{
		return s;
	}
}
</syntaxhighlight>

=== Числовий приклад ===
Наприклад, якщо обчислити цілочисельний квадратний корінь з <math>2000000</math> використовуючи наведений вище алгоритм, можна отримати послідовність

: <math>\begin{align}
& 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{align}</math>

Загалом потрібно 13 кроків ітерації. Хоча метод Герона сходиться квадратично близько до розв’язку, на початку досягається менше ніж один біт точності на ітерацію. Це означає, що вибір початкової оцінки є критичним для продуктивності алгоритму.

Якщо доступне швидке обчислення для цілої частини [[Двійковий логарифм|двійкового логарифма]] або {{iw|Бітова довжина|бітової довжини||Bit-length}} (наприклад, <code>std::bit_width</code> у [[C++20]]), краще починати з

: <math>x_0 = 2^{\lfloor (\log_2 n) /2 \rfloor+1}</math> ,

що є найменшим ступенем двійки, більшим за <math>\sqrt n</math>. У прикладі цілочисельного квадратного кореня з <math>2000000</math>, <math>\lfloor \log_2 n \rfloor=20</math>, <math>x_0=2^{11}=2 048</math>, а результуюча послідовність дорівнює

: <math> 2048\rightarrow 1512\rightarrow 1417\rightarrow 1414 \rightarrow 1414</math> .

У цьому випадку потрібні лише 4 кроки ітерації.

== Поцифровий алгоритм ==
Традиційний  {{iw|Методи обчислення квадратних коренів|ручний алгоритм||Methods_of_computing_square_roots}} для обчислення квадратного кореня <math>\sqrt{n}</math> заснований на роботі від старших розрядів до нижчих, і з кожною новою цифрою вибирається найбільша, яка все ще дасть квадрат <math>\leq n</math> . Якщо зупинитися після одиниці, обчисленим результатом буде цілочисельний квадратний корінь.

=== Використання побітових операцій ===
При роботі в [[Двійкова система числення|за основою 2]] вибір цифри спрощується до числа між 0 («маленький кандидат») і 1 («великий кандидат»), а маніпуляції з цифрами можна виразити в термінах операцій двійкового зсуву. З <code>*</code> — це множення, <code>&#x3C;&#x3C;</code> — зсув вліво, а <code>&#x3E;&#x3E;</code> — логічний зсув вправо, [[Рекурсія (програмування)|рекурсивний]] алгоритм для знаходження цілочисельного квадратного кореня з будь-якого [[Натуральні числа|натурального числа]] виглядає так:<syntaxhighlight lang="python">
def integer_sqrt(n: int) -> int:
  assert n >= 0, "sqrt працює тільки для невід'ємних вхідних даних"
  if n < 2:
    return n

  # Рекрсивний виклик:
  small_cand = integer_sqrt(n >> 2) << 1
  large_cand = small_cand + 1
  if large_cand * large_cand > n:
    return small_cand
  else:
    return large_cand


# еквівалентно:
def integer_sqrt_iter(n: int) -> int:
  assert n >= 0, "sqrt працює тільки для невід'ємних вхідних даних"
  if n < 2:
    return n

  # Find the shift amount. See also [[find first set]],
  # shift = ceil(log2(n) * 0.5) * 2 = ceil(ffs(n) * 0.5) * 2
  shift = 2
  while (n >> shift) != 0:
    shift += 2

  # Unroll the bit-setting loop.
  result = 0
  while shift >= 0:
    result = result << 1
    large_cand = (
      result + 1
    ) # Same as result ^ 1 (xor), because the last bit is always 0.
    if large_cand * large_cand <= n >> shift:
      result = large_cand
    shift -= 2

  return result
</syntaxhighlight>Представлення традиційних ручних порозрядних алгоритмів включають різні оптимізації, яких немає в коді вище, зокрема трюк попереднього віднімання квадрата попередніх цифр, що робить непотрібним загальний крок множення. Див. {{Section link|Methods of computing square roots|Binary numeral system (base 2)}} для прикладу. {{Sfn|Woo|1985}}

== У мовах програмування ==
Деякі мови програмування мають явну операцію обчисленню цілочисельного квадратного кореня на додаток до загального випадку або можуть бути розширені бібліотеками для цієї мети.

* <code>(isqrt x)</code> : [[Common Lisp]].{{Sfn|LispWorks Ltd|1996}}
* <code>math.isqrt(x)</code> : [[Python]].{{Sfn|Python Software Foundation|2001}}

== Див. також ==

* {{iw|Методи обчислення квадратних коренів|||Methods of computing square roots}}

== Примітки ==
<references group="" responsive="1"></references>

== Посилання ==
 {{Refbegin}}

*{{cite journal|last=Jarvis|first=Ashley Frazer|year=2006|title=Square roots by subtraction|url=http://www.afjarvis.staff.shef.ac.uk/maths/jarvisspec02.pdf|journal=Mathematical Spectrum|volume=37|pages=119-122}}
*{{cite web|author=LispWorks Ltd|url=http://www.lispworks.com/documentation/lw50/CLHS/Body/f_sqrt_.htm|title=CLHS: Function SQRT, ISQRT|date=1996|website=www.lispworks.com}}
*{{cite book
|url=https://archive.org/details/computationfinit0000mins
|title=Computation: Finite and Infinite Machines
|last=Minsky
|first=Marvin
|year=1967
|publisher=Prentice-Hall
|chapter=9. The Computable Real Numbers
|isbn=0-13-165563-9
|oclc=0131655639
|author-link=Marvin Minsky
|url-access=registration
}}
*{{cite web|author=Python Software Foundation|url=https://docs.python.org/3/library/math.html#math.isqrt|title=Mathematical functions|date=2001|website=Python Standard Library documentation|postscript=&nbsp;(since version 3.8)}}
*{{cite web|last=Woo|first=C|title=Square root by abacus algorithm (archived)|date=June 1985|url=https://web.archive.org/web/20120306040058/http://medialab.freaknet.org/martin/src/sqrt/sqrt.c}}
*{{cite web|url=http://mathcentral.uregina.ca/RR/database/RR.09.95/grzesina1.html|title=A geometric view of the square root algorithm|url-status=dead}}

{{Refend}}
{{Алгоритми теорії чисел}}

[[Категорія:Чисельні методи розв'язування рівнянь]]
[[Категорія:Теорія чисел]]
[[Категорія:Алгоритми теорії чисел]]
[[Категорія:Сторінки з неперевіреними перекладами]]