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

: 

Наприклад, 

Вступне зауваження
Нехай  та  є цілими невід’ємними числами.

Алгоритми, які обчислюють ()  працюють вічно на кожному вході  який не є ідеальним квадратом.

Алгоритми, що обчислюють  працюють не вічно. Проте вони можуть обчислювати  з будь-якою бажаною точністю  .

Можна обрати будь-яке  і обчислити  .

Наприклад (нехай  ):

: 

Порівняйте результати з 

Виявляється, що множення входу алгоритму на  дає точність  десяткових цифр. 

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

Припустимо, що в наступній програмі (  ) процедура  вже визначена, і — заради аргументації — що всі змінні можуть містити цілі числа необмеженої величини.

Тоді  надрукує повне десяткове представлення .
// Друкує 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().

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

:

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

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

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

:  .

// Цілочислельний квадратний корінь
// (лінійний пошук, за зростанням) використовуючи додавання
unsigned int isqrt( unsigned int y )
{
	unsigned int L = 0;
	unsigned int a = 1;
	unsigned int d = 3;

	while( a 

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

Розрахунок , де  є невід’ємним цілим числом, є окремим випадком, який не потребує повного алгоритму. Досить наступної програми. 
// Цілочислельний квадратний корінь (використовуючи віднімання)
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;
}
Числовий приклад

Наприклад, якщо обчислити  використовуючи метод «віднімання», отримуємо  послідовність

: 
: 

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

Алгоритм із використанням бінарного пошуку
Лінійний пошук послідовно перевіряє кожне значення, доки воно не досягне найменшого  де  .

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

Наприклад, якщо обчислити  використовуючи двійковий пошук, можна отримати  послідовність

: 

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

Алгоритм з використанням методу Ньютона
Один спосіб розрахунку  і  полягає у використанні , який є окремим випадком методу Ньютона, щоб знайти розв’язок рівняння , за даною ітераційною формулою

: 

Послідовність  сходиться квадратично до  коли .

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

: 

забезпечує  в наведеному вище алгоритмі.

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

Область обчислень
Хоча  для багатьох  є ірраціональним, послідовність  містить лише раціональні значення, коли  є раціональним. Таким чином, за допомогою цього методу немає необхідності виходити з поля раціональних чисел для обчислення , факт, який має деякі теоретичні переваги.

Використання тільки цілочисельного ділення
Для обчислень  для дуже великих цілих чисел n можна використовувати евклідове ділення для обох операцій ділення. Це має перевагу в тому, що для кожного проміжного значення використовуються лише цілі числа, що робить непотрібним представлення великих чисел з плаваючою комою. Це еквівалентно використанню ітераційної формули

: 

Використовуючи той факт, що

: 

можна показати, що буде досягнуто  протягом скінченної кількості ітерацій.

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

Однак,  не обов’язково є нерухомою точкою наведеної вище ітераційної формули. Дійсно, можна показати, що  є фіксованою точкою тоді і тільки тоді, коли  не є ідеальним квадратом. Якщо  є ідеальним квадратом, послідовність закінчується циклом з періодом два між  і  замість того, щоб сходитись.

Приклад реалізації на 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 

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

: 

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

Якщо доступне швидке обчислення для цілої частини двійкового логарифма або  (наприклад, std::bit_width у C++20), краще починати з

:  ,

що є найменшим ступенем двійки, більшим за . У прикладі цілочисельного квадратного кореня з , , , а результуюча послідовність дорівнює

:  .

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

Поцифровий алгоритм
Традиційний   для обчислення квадратного кореня  заснований на роботі від старших розрядів до нижчих, і з кожною новою цифрою вибирається найбільша, яка все ще дасть квадрат  . Якщо зупинитися після одиниці, обчисленим результатом буде цілочисельний квадратний корінь.

Використання побітових операцій
При роботі в за основою 2 вибір цифри спрощується до числа між 0 («маленький кандидат») і 1 («великий кандидат»), а маніпуляції з цифрами можна виразити в термінах операцій двійкового зсуву. З * — це множення,  — зсув вліво, а >> — логічний зсув вправо, рекурсивний алгоритм для знаходження цілочисельного квадратного кореня з будь-якого натурального числа виглядає так:
def integer_sqrt(n: int) -> int:
  assert n >= 0, "sqrt працює тільки для невід'ємних вхідних даних"
  if n > 2)  n:
    return small_cand
  else:
    return large_cand


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

  # Unroll the bit-setting loop.
  result = 0
  while shift >= 0:
    result = result > shift:
      result = large_cand
    shift -= 2

  return result
Представлення традиційних ручних порозрядних алгоритмів включають різні оптимізації, яких немає в коді вище, зокрема трюк попереднього віднімання квадрата попередніх цифр, що робить непотрібним загальний крок множення. Див.  для прикладу. 

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

* (isqrt x) : Common Lisp.
* math.isqrt(x) : Python.

Див. також

* 

Примітки


Посилання
 

*
*
*
*
*
*







