Существуют ли какие-либо известные субквадратичные алгоритмы для вычисления минимального значения квадратного корня из n
целого бита?
Наивный алгоритм будет что-то вроде
def sqrt(x):
r = 0
i = x.bit_length() // 2
while i >= 0:
inc = (r << (i+1)) + (1 << (i*2))
if inc <= x:
x -= inc
r += 1 << i
i -= 1
return r
Это требует O(n)
итераций, каждая из которых включает в себя дополнения, которые являются O(n)
временем, так что это O(n^2)
общее время. Есть ли что-нибудь быстрее? Я знаю, что для случая умножения есть специальные алгоритмы, которые работают лучше, чем квадратичное время, но я не могу найти ничего для квадратных корней.
Ответы:
Вы можете использовать метод Ньютона или любой из ряда других методов для нахождения приближений к корням полинома .р ( х ) = х2- с
Скорость сходимости для метода Ньютона будет квадратичной, что означает, что число правильных битов удваивается в каждой итерации. Это означает, что итераций метода Ньютона достаточно.O ( LGн )
Каждая итерация метода Ньютона вычисляет
Битовая сложность умножения равна , чтобы умножить два разрядных целых числа (игнорируя факторы ). Битовая сложность для деления (до бит точности) одинакова. Следовательно, каждая итерация может быть вычислена в операциях . Умножая на итераций, мы находим, что общее время выполнения для вычисления квадратного корня до битов точности равно . Это субквадратичное.blglgbb O (nlgn)O(lgn)n O (n(lgn)2)О ( b lgб ) б Л.Г.Л.Г.б б O (nlgn) O(lgn) n O (n(lgn)2)
Я думаю, что более тщательный анализ показывает, что это можно улучшить до времени выполнения (принимая во внимание, что нам нужно знать только каждый с точностью до бит точности, а не бит точности). Тем не менее, даже более базовый анализ уже показывает время выполнения, которое явно субквадратично.xjjnO (nlgn) xj j n
источник
Одна из проблем метода Ньютона заключается в том, что он требует операции деления в каждой итерации, которая является самой медленной базовой целочисленной операцией.
Метод Ньютона для обратного квадратного корня, однако, не делает. Если - это число, для которого вы хотите найти , выполните итерацию:1x 1x√
Это часто выражается как:
d i = 1 - w i x r i + 1 = r i + r i d i
Это три операции умножения. Деление на два может быть реализовано как сдвиг вправо.
Теперь проблема в том, что не является целым числом. Тем не менее, вы можете манипулировать им как таковым, реализуя с плавающей запятой вручную и выполняя кучу операций сдвига, чтобы компенсировать, когда это необходимо.r
Во-первых, давайте изменим масштаб :x
где мы хотели бы, чтобы было больше, но близко к . Если мы запустим вышеупомянутый алгоритм на вместо , мы найдем . Тогда . 1 x ′ x r = 1x′ 1 x′ x √r=1x√′ x−−√=2erx′
Теперь давайте разделим на мантиссу и показатель степени:r
где - целое число Интуитивно , что представляет точность ответа. e ir′i ei
Мы знаем, что метод Ньютона примерно удваивает количество точных значащих цифр. Таким образом, мы можем выбрать:
С небольшой манипуляцией мы находим:
На каждой итерации:
В качестве примера, давайте попробуем вычислить квадратный корень из . Мы знаем, что ответ . Обратный квадратный корень равен , поэтому мы установим (это масштаб проблемы) и для нашего начального предположения выберем и . (То есть мы выбираем для нашей начальной оценки .)x=263 2312–√ 12√2−31 e=31 r′0=3 e0=2 34 12√
Затем:
Мы можем решить, когда прекратить итерации, сравнив с ; если я правильно рассчитал, должно быть достаточно хорошим. Мы остановимся здесь и найдем:ei e ei>2e
Правильный целочисленный квадратный корень - , поэтому мы довольно близки. Мы можем сделать еще одну итерацию или оптимизированную последнюю итерацию, которая не удваивает . Детали оставлены в качестве упражнения.3037000499 ei
Чтобы проанализировать сложность этого метода, обратите внимание, что умножение двух разрядных целых чисел требует операций. Тем не менее, мы упорядочили вещи так, чтобы . Таким образом, умножение для вычисления умножает два числа бит, чтобы получить число -бит, а два других умножения умножают два числа -бит, чтобы получить -битный номер.b O(blogb) r′i<2ei wi ei ei+1 ei+1 2ei+1
В каждом случае число операций на итерацию равно , и требуется итераций. Окончательное умножение порядка операций. Таким образом, общая сложность состоит из операций, которые субквадратичны по числу битов в . Это помечает все коробки.O(eilogei) O(loge) O(2elog2e) O(elog2e) x
Однако этот анализ скрывает важный принцип, который должен иметь в виду каждый, кто работает с большими целыми числами: поскольку умножение является суперлинейным по количеству битов, любые операции умножения должны выполняться только с целыми числами, которые имеют приблизительную величину текущей точности (и Я мог бы добавить, что вы должны попытаться умножить числа вместе, которые имеют схожий порядок). Использование целых чисел больше, чем это пустая трата усилий. Постоянные факторы имеют значение, а для больших целых они имеют большое значение.
В качестве последнего замечания, два умножения имеют вид . Очевидно, что расточительно вычислять все биты только для того, чтобы выбросить из них со сдвигом вправо. Реализация умного метода умножения, который учитывает это, также оставлена в качестве упражнения.ab2c ab c
источник