MAXimal

добавлено: 10 Jun 2008 16:41
редактировано: 3 May 2012 2:34

Бинарное возведение в степень

Бинарное (двоичное) возведение в степень — это приём, позволяющий возводить любое число в n-ую степень за O(\log n) умножений (вместо n умножений при обычном подходе).

Более того, описываемый здесь приём применим к любой ассоциативной операции, а не только к умножению чисел. Напомним, операция называется ассоциативной, если для любых a, b, c выполняется:

 (a \cdot b) \cdot c = a \cdot (b \cdot c)

Наиболее очевидное обобщение — на остатки по некоторому модулю (очевидно, ассоциативность сохраняется). Следующим по "популярности" является обобщение на произведение матриц (его ассоциативность общеизвестна).

Алгоритм

Заметим, что для любого числа a и чётного числа n выполнимо очевидное тождество (следующее из ассоциативности операции умножения):

 a^n = (a^{n/2})^2 = a^{n/2} \cdot a^{n/2}

Оно и является основным в методе бинарного возведения в степень. Действительно, для чётного n мы показали, как, потратив всего одну операцию умножения, можно свести задачу к вдвое меньшей степени.

Осталось понять, что делать, если степень n нечётна. Здесь мы поступаем очень просто: перейдём к степени n-1, которая будет уже чётной:

 a^n = a^{n-1} \cdot a

Итак, мы фактически нашли рекуррентную формулу: от степени n мы переходим, если она чётна, к n/2, а иначе — к n-1. Понятно, что всего будет не более 2 \log n переходов, прежде чем мы придём к n = 0 (базе рекуррентной формулы). Таким образом, мы получили алгоритм, работающий за O (\log n) умножений.

Реализация

Простейшая рекурсивная реализация:

int binpow (int a, int n) {
	if (n == 0)
		return 1;
	if (n % 2 == 1)
		return binpow (a, n-1) * a;
	else {
		int b = binpow (a, n/2);
		return b * b;
	}
}

Нерекурсивная реализация, также оптимизированная (деления на 2 заменены битовыми операциями):

int binpow (int a, int n) {
	int res = 1;
	while (n)
		if (n & 1) {
			res *= a;
			--n;
		}
		else {
			a *= a;
			n >>= 1;
		}
	return res;
}

Эту реализацию можно ещё несколько упростить, заметив, что возведение a в квадрат осуществляется всегда, независимо от того, сработало условие нечётности n или нет:

int binpow (int a, int n) {
	int res = 1;
	while (n) {
		if (n & 1)
			res *= a;
		a *= a;
		n >>= 1;
	}
	return res;
}

Наконец, стоит отметить, что бинарное возведение в степень уже реализовано в языке Java, но только для класса длинной арифметики BigInteger (функция pow этого класса работает именно по алгоритму бинарного возведения).

Примеры решения задач

Эффективное вычисление чисел Фибоначчи

Условие. Дано число n. Требуется вычислить F_n, где F_iпоследовательность чисел Фибоначчи.

Решение. Более подробно это решение описано в статье о последовательности Фибоначчи. Здесь же мы лишь кратко приведём суть этого решения.

Основная идея следующая. Вычисление очередного числа Фибоначчи основывается на знании двух предыдущих чисел Фибоначчи: а именно, каждое следующее число Фибоначчи получается как сумма двух предыдущих. Это означает, что мы можем построить матрицу 2 \times 2, которая будет соответствовать этому преобразованию: как по двум числам Фибоначчи F_i и F_{i+1} вычислить следующее число, т.е. перейти к паре F_{i+1}, F_{i+2}. Например, применяя это преобразование n раз к паре F_0 и F_1, мы получим пару F_n и F_{n+1}. Таким образом, возведя матрицу этого преобразования в n-ую степень, мы тем самым найдём искомое F_n за время O (\log n), что нам и требовалось.

Возведение перестановки в k-ую степень

Условие. Дана перестановка p длины n. Требуется возвести её в k-ую степень, т.е. найти, что получится, если к тождественной перестановке k раз применить перестановку p.

Решение. Просто применим к перестановке p описанный выше алгоритм бинарного возведения в степень. Никаких отличий по сравнению с возведением чисел в степень — нет. Решение получается с асимптотикой O (n \log k).

(Примечание. Данную задачу можно решить и более эффективно, за линейное время. Для этого достаточно выделить в перестановке все циклы, после чего рассмотреть по отдельности каждый цикл и, взяв k по модулю длины текущего цикла, найти ответ для этого цикла.)

Быстрое применение набора геометрических операций к точкам

Условие. Даны n точек p_i, и даны m преобразований, которые надо применить к каждой из этих точек. Каждое преобразование — это либо сдвиг на заданный вектор, либо масштабирование (умножение координат на заданные коэффициенты), либо вращение вокруг заданной оси на заданный угол. Кроме того, имеется составная операция циклического повторения: она имеет вид "повторить заданное число раз заданный список преобразований" (операции циклического повторения могут вкладываться друг в друга).

Требуется вычислить результат применения указанных операций ко всем точкам (эффективно, т.е. за время, меньшее чем O(n \cdot length), где length — общее количество операций, которые необходимо сделать).

Решение. Посмотрим на разные виды преобразований с точки зрения того, как они изменяют координаты:

  • Операция сдвига — она просто прибавляет ко всем координатам единицу, домноженную на некоторые константы.

  • Операция масштабирования — она умножает каждую координату на некоторую константу.

  • Операция вращения вокруг оси — её можно представить следующим образом: новые получаемые координаты можно записать как линейную комбинацию старых.

    (Мы не будем здесь уточнять, каким образом это производится. Например, можно для простоты представить это в виде комбинации пяти двумерных поворотов: сначала в плоскостях OXY и OXZ так, чтобы ось вращения совпала с положительным направлением оси OX, затем требуемый поворот вокруг оси в плоскости YZ, затем обратные повороты в плоскостях OXZ и OXY так, чтобы ось вращения вернулась в своё исходное положение.)

Как легко видеть, каждое из этих преобразований — это пересчёт координат по линейным формулам. Таким образом, любое такое преобразование можно записать в виде матрицы 4 \times 4:

 \begin{pmatrix}
a_11 & a_{12} & a_{13} & a_{14} [...]

которое при умножении (слева) на строку из старых координат и константы-единицы даёт строку из новых координат и константы-единицы:

 \begin{pmatrix} x & y & z & 1 \end{pmatrix} \cdot[...]

(Почему понадобилось вводить фиктивную четвёртую координату, всегда равную единице? Без этого не получилось бы реализовать операцию сдвига: ведь сдвиг — это как раз прибавление к координатам единицы, домноженной на некоторые коэффициенты. Без фиктивной единицы мы бы смогли только реализовывать линейные комбинации самих координат, а прибавлять к ним заданные константы — не смогли бы.)

Теперь решение задачи становится почти тривиальным. Раз каждая элементарная операция описывается матрицей, то последовательность операций описывается произведением этих матриц, а операция циклического повторения — возведением этой матрицы в степень. Таким образом, мы за время O (m \cdot \log repetition) можем предпосчитать матрицу 4 \times 4, описывающую все преобразования, и затем просто умножить каждую точку p_i на эту матрицу — тем самым, мы ответим на все запросы за время O (n).

Количество путей фиксированной длины в графе

Условие. Дан неориентированный граф G с n вершинами, и дано число k. Требуется для каждой пары вершин i и j найти количество путей между ними, содержащих ровно k рёбер.

Решение. Более подробно эта задача рассматривается в отдельной статье. Здесь же лишь напомним суть этого решения: мы просто возводим в k-ую степень матрицу смежности этого графа, и элементы этой матрицы и будут являться решениями. Итоговая асимптотика — O (n^3 \log k).

(Примечание. В той же статье рассматривается и другая вариация этой задачи: когда граф взвешенный, и требуется найти путь минимального веса, содержащий ровно k рёбер. Как показано в этой статье, данная задача также решается с помощью бинарного возведения в степень матрицы смежности графа, однако вместо обычной операции перемножения двух матриц следует использовать модифицированную: вместо умножений берётся сумма, а вместо суммирования — взятие минимума.)

Вариация бинарного возведения в степень: перемножение двух чисел по модулю

Приведём здесь интересную вариацию бинарного возведения в степень.

Пусть перед нами стоит такая задача: перемножить два числа a и b по модулю m:

 a \cdot b \pmod m

Предположим, что числа могут быть достаточно велики: настолько, что сами числа помещаются во встроенные типы данных, а вот их непосредственное произведение a \cdot b — уже нет (отметим, что нам также потребуется, чтобы сумма чисел помещалась во встроенный тип данных). Соответственно, задача в том, чтобы посчитать искомую величину (a \cdot b) \pmod m, не прибегая к помощи длинной арифметики.

Решение таково. Мы просто применяем алгоритм бинарного возведения, описанный выше, только вместо операции умножения мы будем производить сложения. Иными словами, перемножение двух чисел мы свели к O (\log m) операций сложения и умножения на два (что тоже, по сути, есть сложение).

(Примечание. Данную задачу можно решить и по-другому, прибегнув к помощи операций с числами с плавающей точкой. А именно, посчитаем в числах с плавающей точкой выражение a \cdot b / m, и округлим его к ближайшему целому. Так мы найдём приблизительное частное. Отняв его от произведения a \cdot b (проигнорировав переполнения), мы, скорее всего, получим относительно небольшое число, которое можно взять по модулю m — и вернуть его в качестве ответа. Это решение выглядит довольно ненадёжным, но оно весьма быстрое, и очень кратко реализуется.)

Задачи в online judges

Список задач, которые можно решить, используя бинарное возведение в степень: