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

В теории чисел целочисленный квадратный корень (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$ что не является идеальным квадратом . ^{[примечание 1]}

Алгоритмы, которые вычисляют $\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$ десятичных цифр. ^{[примечание 2]}

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

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

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

// Print sqrt(y), without halting
void sqrtForever(unsigned int y)
{
	unsigned int result = isqrt(y);
	printf("%d.", result);	// print result, followed by a decimal point

	while (true)	// repeat forever ...
	{
		y = y * 100;	// theoretical example: overflow is ignored
		result = isqrt(y);
		printf("%d", result % 10);	// print last digit of result
	}
}

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

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

Целый квадратный корень из неотрицательного целого числа $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 представляют собой простую реализацию.

// Integer square root
// (using linear search, ascending)
unsigned int isqrt(unsigned int y)
{
	// initial underestimate, L <= isqrt(y)
	unsigned int L = 0;

	while ((L + 1) * (L + 1) <= y)
		L = L + 1;

	return L;
}

// Integer square root
// (using linear search, descending)
unsigned int isqrt(unsigned int y)
{
	// initial overestimate, isqrt(y) <= R
	unsigned int R = y;

	while (R * R > y)
		R = R - 1;

	return R;
}

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

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

// Integer square root
// (linear search, ascending) using addition
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;
}

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

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

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

// Integer square root (using binary search)
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;
}

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

Например, если вычислить $\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

// Square root of integer
unsigned int int_sqrt(unsigned int s)
{
	// Zero yields zero
    // One yields one
	if (s <= 1) 
		return s;

    // Initial estimate (must be too high)
	unsigned int x0 = s / 2;

	// Update
	unsigned int x1 = (x0 + s / x0) / 2;

	while (x1 < x0)	// Bound check
	{
		x0 = x1;
		x1 = (x0 + s / x0) / 2;
	}		
	return x0;
}

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

Например, если вычислить целый квадратный корень из $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 integer_sqrt(n: int) -> int:
    assert n >= 0, "sqrt works for only non-negative inputs"
    if n < 2:
        return n

    # Recursive call:
    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


# equivalently:
def integer_sqrt_iter(n: int) -> int:
    assert n >= 0, "sqrt works for only non-negative inputs"
    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

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

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

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

(isqrt x): Общий Лисп . ^[3]
math.isqrt(x): Питон . ^[4]

См. также

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

Примечания

^ Квадратные корни идеальных квадратов (например, 0, 1, 4, 9, 16) являются целыми числами. Во всех остальных случаях квадратные корни натуральных чисел являются иррациональными числами.
^ Неудивительно, что повторное умножение на $100$ является особенностью Джарвиса (2006).
^ Дробная часть квадратных корней из полных квадратов отображается как $000...$ .

Ссылки

^ см. « Методы вычисления квадратных корней ».
^ Ву, К. (июнь 1985 г.). «Квадратный корень по алгоритму счетов (в архиве)» . Архивировано из оригинала 06 марта 2012 г.
^ ЛиспВоркс Лтд. (1996). «CLHS: Функция SQRT, ISQRT» . www.lispworks.com .
^ Фонд программного обеспечения Python (2001). «Математические функции» . Документация стандартной библиотеки Python . (начиная с версии 3.8).

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

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

[1] Квадратные корни идеальных квадратов (например, 0, 1, 4, 9, 16) являются целыми числами. Во всех остальных случаях квадратные корни натуральных чисел являются иррациональными числами.

[2] Неудивительно, что повторное умножение на $100$ является особенностью Джарвиса (2006).

[3] Дробная часть квадратных корней из полных квадратов отображается как $000...$ .

[4] см. « Методы вычисления квадратных корней ».

[5] Ву, К. (июнь 1985 г.). «Квадратный корень по алгоритму счетов (в архиве)» . Архивировано из оригинала 06 марта 2012 г.

[6] ЛиспВоркс Лтд. (1996). «CLHS: Функция SQRT, ISQRT» . www.lispworks.com .

[7] Фонд программного обеспечения Python (2001). «Математические функции» . Документация стандартной библиотеки Python . (начиная с версии 3.8).

[примечание 1]

[примечание 2]

[примечание 3]

[1]

[2]

[3]

[4]

v т и Теоретико-числовые алгоритмы
Тесты на примитивность	АКС АПРЕЛЬ Бэйли – PSW Эллиптическая кривая Поклингтон Ферма Лукас Лукас-Лемер Лукас-Лемер-Ризель Теорема Прота Пепина Квадратичный Фробениус Solovay–Strassen Миллер-Рабин
Прайм-генерирующий	Сито Аткина Решето Эратосфена Сито Причарда Решето Сундарама Факторизация колес
Целочисленная факторизация	Непрерывная дробь (CFRAC) Диксона Эллиптическая кривая Ленстры (ECM) Эйлера Ро Полларда п - 1 р + 1 Квадратное сито (QS) Сито общего числового поля (GNFS) Сито специального числового поля (SNFS) Рациональное сито Ферма Квадратные формы Шанкса Пробное подразделение Шора
Умножение	Древний Египет Длинный Карацуба Тум-Кук Улицы Шенхаге Фюрера
Евклидово деление	Двоичный Разбивка на части Фурье Гольдшмидт Ньютон-Рафсон Длинный Короткий СТО
Дискретный логарифм	Бэби-шаг, гигантский шаг Поллард Ро Поллард кенгуру Полиг-Хеллман Индексное исчисление Функциональное поле сита
Наибольший общий делитель	Двоичный евклидов Расширенный евклидов Лемерс
Модульный квадратный корень	Лук Поклингтон Тонелли – Шанкс Берлекамп Кунерт
Другие алгоритмы	Чакравала Ворона Возведение в степень возведением в степень Целочисленный квадратный корень Целочисленное отношение ( LLL ; KZ ) Модульное возведение в степень Сокращение Монтгомери Пучок Система Трахтенберга
Курсивом обозначено, что алгоритм предназначен для чисел специальных форм.