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

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

{\mbox{isqrt}}(n)=\lfloor {\sqrt {n}}\rfloor .

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

Вступне зауваження[ред. | ред. код]

Нехай $y$ та $k$ є цілими невід’ємними числами.

Алгоритми, які обчислюють (десяткове представлення^[en]) ${\sqrt {y}}$ працюють вічно на кожному вході $y$ який не є ідеальним квадратом.^[1]

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

Можна обрати будь-яке $k$ і обчислити $\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\\&...\\&k=8:\lfloor {\sqrt {2\times 100^{8}}}\rfloor =\lfloor {\sqrt {20000000000000000}}\rfloor =141421356\\&...\\\end{aligned}}

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

Виявляється, що множення входу алгоритму на $100^{k}$ дає точність $k$ десяткових цифр. ^[2]

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

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

Тоді ${\mbox{sqrtForever}}(y)$ надрукує повне десяткове представлення ${\sqrt {y}}$ .^[3]

// Друкує 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 );	// надрукувати останню цифру результата
	}
}

Висновок полягає в тому, що алгоритми, які обчислюють isqrt(), обчислювально еквівалентні алгоритмам, які обчислюють sqrt().^[4]

Основні алгоритми[ред. | ред. код]

Алгоритм з використанням лінійного пошуку[ред. | ред. код]

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

Лінійний пошук[ред. | ред. код]

За допомогою додавання[ред. | ред. код]

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

(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;
	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;
}

За допомогою віднімання[ред. | ред. код]

Jarvis, (2006) опублікував метод отримання цілочисельного квадратного кореня з використанням виключно віднімання.

Розрахунок ${\mbox{isqrt}}(y)$ , де $y$ є невід’ємним цілим числом, є окремим випадком, який не потребує повного алгоритму. Досить наступної програми. ^[5]

// Цілочислельний квадратний корінь (використовуючи віднімання)
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;
}

Числовий приклад

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

{\begin{aligned}&[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{aligned}}

140/10=14=\lfloor {\sqrt {200}}\rfloor

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

Алгоритм із використанням бінарного пошуку[ред. | ред. код]

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

Прискорення досягається за допомогою двійкового пошуку. Наступна програма мово 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;
}

Числовий приклад

Наприклад, якщо обчислити ${\mbox{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}}$ і ${\mbox{isqrt}}(n)$ полягає у використанні методу Герона^[en], який є окремим випадком методу Ньютона, щоб знайти розв’язок рівняння $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$ в наведеному вище алгоритмі.

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

Область обчислень[ред. | ред. код]

Хоча ${\sqrt {n}}$ для багатьох $n$ є ірраціональним, послідовність $\{x_{k}\}$ містить лише раціональні значення, коли $x_{0}$ є раціональним. Таким чином, за допомогою цього методу немає необхідності виходити з поля раціональних чисел для обчислення ${\mbox{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 )
{
	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;
	}
}

Числовий приклад[ред. | ред. код]

Наприклад, якщо обчислити цілочисельний квадратний корінь з $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 кроків ітерації. Хоча метод Герона сходиться квадратично близько до розв’язку, на початку досягається менше ніж один біт точності на ітерацію. Це означає, що вибір початкової оцінки є критичним для продуктивності алгоритму.

Якщо доступне швидке обчислення для цілої частини двійкового логарифма або бітової довжини^[en] (наприклад, 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

.

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

Поцифровий алгоритм[ред. | ред. код]

Традиційний ручний алгоритм^[en] для обчислення квадратного кореня ${\sqrt {n}}$ заснований на роботі від старших розрядів до нижчих, і з кожною новою цифрою вибирається найбільша, яка все ще дасть квадрат $\leq n$ . Якщо зупинитися після одиниці, обчисленим результатом буде цілочисельний квадратний корінь.

Використання побітових операцій[ред. | ред. код]

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

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

Представлення традиційних ручних порозрядних алгоритмів включають різні оптимізації, яких немає в коді вище, зокрема трюк попереднього віднімання квадрата попередніх цифр, що робить непотрібним загальний крок множення. Див. Methods of computing square roots § Binary numeral system (base 2) для прикладу. ^[6]

У мовах програмування[ред. | ред. код]

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

(isqrt x) : Common Lisp.^[7]
math.isqrt(x) : Python.^[8]

Див. також[ред. | ред. код]

Методи обчислення квадратних коренів^[en]

Примітки[ред. | ред. код]

↑ 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]
↑ It is no surprise that the repeated multiplication by $100$ is a feature in Jarvis, (2006)
↑ The fractional part of square roots of perfect squares is rendered as $000...$ .
↑ see 'Methods of computing square roots'.
↑ The method was defined for the positive integers. Te program below computes ${\mbox{isqrt}}(0)=0$ as well
↑ Woo, 1985.
↑ LispWorks Ltd, 1996.
↑ Python Software Foundation, 2001.

Посилання[ред. | ред. код]

Jarvis, Ashley Frazer (2006). Square roots by subtraction (PDF). Mathematical Spectrum. 37: 119—122.
LispWorks Ltd (1996). CLHS: Function SQRT, ISQRT. www.lispworks.com.
Minsky, Marvin (1967). 9. The Computable Real Numbers. Computation: Finite and Infinite Machines. Prentice-Hall. ISBN 0-13-165563-9. OCLC 0131655639.
Python Software Foundation (2001). Mathematical functions. Python Standard Library documentation (since version 3.8)
Woo, C (June 1985). Square root by abacus algorithm (archived).
A geometric view of the square root algorithm.{{cite web}}: Обслуговування CS1: Сторінки з параметром url-status, але без параметра archive-url (посилання)

[1] 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]

[2] It is no surprise that the repeated multiplication by $100$ is a feature in Jarvis, (2006)

[3] The fractional part of square roots of perfect squares is rendered as $000...$ .

[4] see 'Methods of computing square roots'.

[5] The method was defined for the positive integers. Te program below computes ${\mbox{isqrt}}(0)=0$ as well

[FOOTNOTEWoo1985-6] Woo, 1985.

[FOOTNOTELispWorks_Ltd1996-7] LispWorks Ltd, 1996.

[FOOTNOTEPython_Software_Foundation2001-8] Python Software Foundation, 2001.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

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

Зміст

Вступне зауваження[ред. | ред. код]

Основні алгоритми[ред. | ред. код]

Алгоритм з використанням лінійного пошуку[ред. | ред. код]

Лінійний пошук[ред. | ред. код]

За допомогою додавання[ред. | ред. код]

За допомогою віднімання[ред. | ред. код]

Алгоритм із використанням бінарного пошуку[ред. | ред. код]

Алгоритм з використанням методу Ньютона[ред. | ред. код]

Критерій зупинки[ред. | ред. код]

Область обчислень[ред. | ред. код]

Використання тільки цілочисельного ділення[ред. | ред. код]

Приклад реалізації на C[ред. | ред. код]

Числовий приклад[ред. | ред. код]

Поцифровий алгоритм[ред. | ред. код]

Використання побітових операцій[ред. | ред. код]

У мовах програмування[ред. | ред. код]

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

Посилання[ред. | ред. код]

Навігаційне меню

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

Вступне зауваження[ред. | ред. код]

Основні алгоритми[ред. | ред. код]

Алгоритм з використанням лінійного пошуку[ред. | ред. код]

Лінійний пошук[ред. | ред. код]

За допомогою додавання[ред. | ред. код]

За допомогою віднімання[ред. | ред. код]

Алгоритм із використанням бінарного пошуку[ред. | ред. код]

Алгоритм з використанням методу Ньютона[ред. | ред. код]

Критерій зупинки[ред. | ред. код]

Область обчислень[ред. | ред. код]

Використання тільки цілочисельного ділення[ред. | ред. код]

Приклад реалізації на C[ред. | ред. код]

Числовий приклад[ред. | ред. код]

Поцифровий алгоритм[ред. | ред. код]

Використання побітових операцій[ред. | ред. код]

У мовах програмування[ред. | ред. код]

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

Посилання[ред. | ред. код]

Навігаційне меню

Пошук