Одним из действий с многочленами является умножение многочлена на многочлен. В данной статье рассмотрим правило такого умножения и применим его при решении задач.
Правило умножения многочлена на многочлен
Зададим два многочлена a + b и c + d и выполним их умножение.
В первую очередь запишем произведение исходных многочленов: поставим между ними знак умножения, предварительно заключив многочлены в скобки. Получим: (a + b) · (c + d) . Теперь обозначим множитель (c + d) как x , тогда выражение получит вид: (a + b) · x , что по сути является произведением многочлена и одночлена. Осуществим умножение: (a + b) · x = a · x + b · x , а затем обратно заменим х на (c + d) : a · (c + d) + b · (c + d) . И вновь применив правило умножения многочлена на одночлен, преобразуем выражение в: a · c + a · d + b · c + b · d . Резюмируя: произведению заданных многочленов a + b и c + d соответствует равенство (a + b) · (c + d) = a · c + a · d + b · c + b · d .
Рассуждения, которые мы привели выше, дают возможность сделать важные выводы:
- Результат умножения многочлена на многочлен - многочлен. Данное утверждение справедливо для любых перемножаемых многочленов.
- Произведение многочленов есть сумма произведений каждого члена одного многочлена на каждый член другого. Откуда можно сделать заключение, что при умножении многочленов, содержащих m и n членов соответственно, указанная сумма произведений членов состоит из m · n слагаемых.
Теперь можем сформулировать правило умножения многочленов:
Определение 1
Для осуществления умножения многочлена на многочлен, необходимо каждый член одного многочлена умножить на каждый член другого многочлена и найти сумму полученных произведений.
Примеры умножения многочлена на многочлен
В практическом решении задач нахождение произведения многочленов раскладывается на несколько последовательных действий:
- запись произведения умножаемых многочленов (многочлены заключаются в скобки и между ними записывается знак умножения);
- выстраивание суммы произведений каждого члена первого многочлена на каждый член второго. С этой целью первый член первого многочлена умножается на каждый член второго многочлена, затем второй член первого многочлена перемножается с каждым членом второго многочлена и так далее;
- если это возможно, полученная сумма записывается в виде многочлена стандартного вида.
Заданы многочлены: 2 − 3 · x и x 2 − 7 · x + 1
Решение
Запишем произведение исходных многочленов. Получим: (2 − 3 · x) · (x 2 − 7 · x + 1) .
Следующим шагом составим сумму произведений каждого члена многочлена 2 − 3 · x на каждый член многочлена x 2 − 7 · x + 1 . Рассмотрим подробно: умножаем первый член первого многочлена (число 2) на каждый член второго многочлена, получим: 2 · x 2 , 2 · (− 7 · x) и 2 · 1 . Затем умножаем второй член первого многочлена на каждый член второго многочлена и получаем: − 3 · x · x 2 , − 3 · x · (− 7 · x) и − 3 · x · 1 . Все полученные выражения собираем в сумму: 2 · x 2 + 2 · (− 7 · x) + 2 · 1 − 3 · x · x 2 − 3 · x · (− 7 · x) − 3 · x · 1 .
Проверим, не пропустили ли мы произведение каких-либо членов: для этого пересчитаем количество членов в записанной сумме, получим 6 . Это верно, поскольку исходные многочлены состоят из 2 и 3 членов, что в общем дает 6 .
Последним действием преобразуем записанную сумму в многочлен стандартного вида: 2 · x 2 + 2 · (− 7 · x) + 2 · 1 − 3 · x · x 2 − 3 · x · (− 7 · x) − 3 · x · 1 = = 2 · x 2 − 14 · x + 2 − 3 · x 3 + 21 · x 2 − 3 · x = = (2 · x 2 + 21 · x 2) + (− 14 · x − 3 · x) + 2 − 3 · x 3 = 23 · x 2 − 17 · x + 2 − 3 · x 3
Кратко без пояснений решение будет выглядеть так:
(2 − 3 · x) · (x 2 − 7 · x + 1) = 2 · x 2 + 2 · (− 7 · x) + 2 · 1 − 3 · x · x 2 − 3 · x · (− 7 · x) − 3 · x · 1 = = 2 · x 2 − 14 · x + 2 − 3 · x 3 + 21 · x 2 − 3 · x = = (2 · x 2 + 21 · x 2) + (− 14 · x − 3 · x) + 2 − 3 · x 3 = 23 · x 2 − 17 · x + 2 − 3 · x 3
Ответ: (2 − 3 · x) · (x 2 − 7 · x + 1) = 23 · x 2 − 17 · x + 2 − 3 · x 3 .
Уточним, что, когда исходные многочлены заданы в нестандартном виде, перед тем, как найти их произведение, желательно привести их к стандартному виду. Результат, конечно, будет тот же, но решение станет удобнее и короче.
Пример 2
Заданы многочлены 1 7 · x 2 · (- 3) · y + 3 · x - 2 7 · x · y · x и x · y − 1 . Необходимо найти их произведение.
Решение
Один из заданных многочленов записан в нестандартном виде. Исправим это, приведя его к стандартному виду:
1 7 · x 2 · (- 3) · y + 3 · x - 2 7 · x · y · x = - 3 7 · x 2 + 3 · x - 2 7 · x 2 · y = = - 3 7 · x 2 · y - 2 7 · x 2 · y + 3 · x = - 5 7 · x 2 · y + 3 · x
Теперь найдем искомое произведение:
5 7 · x 2 · y + 3 · x · x · y - 1 = = - 5 7 · x 2 · y · x · y - 5 7 · x 2 · y · (- 1) + 3 · x · x · y + 3 · x · (- 1) = = - 5 7 · x 3 · y 2 + 5 7 · x 2 · y + 3 · x 2 · y - 3 · x = - 5 7 · x 3 · y 2 + 3 5 7 · x 2 · y - 3 · x
Ответ: - 5 7 · x 2 · y + 3 · x · x · y - 1 = - 5 7 · x 3 · y 2 + 3 5 7 · x 2 · y - 3 · x
Напоследок проясним ситуацию, в которой есть необходимость перемножить три и более многочленов. В этом случае нахождение произведения сводится к последовательному перемножению многочленов по два: т.е. сначала перемножаются первые два многочлена; полученный результат умножается на третий многочлен; итог этого умножения – на четвертый многочлен и так далее.
Пример 3
Заданы многочлены: x 2 + x · y − 1 , x + y и 2 · y − 3 . Необходимо найти их произведение.
Решение
Сделаем запись произведения: (x 2 + x · y − 1) · (x + y) · (2 · y − 3) .
Перемножим первые два многочлена, получим: (x 2 + x · y − 1) · (x + y) = x 2 · x + x 2 · y + x · y · x + x · y · y − 1 · x − 1 · y = = x 3 + 2 · x 2 · y + x · y 2 − x − y .
Первоначальная запись произведения принимает вид: (x 2 + x · y − 1) · (x + y) · (2 · y − 3) = (x 3 + 2 · x 2 · y + x · y 2 − x − y) · (2 · y − 3) .
Найдем результат этого умножения:
(x 3 + 2 · x 2 · y + x · y 2 − x − y) · (2 · y − 3) = = x 3 · 2 · y + x 3 · (− 3) + 2 · x 2 · y · 2 · y + 2 · x 2 · y · (− 3) + x · y 2 · 2 · y + + x · y 2 · (− 3) − x · 2 · y − x · (− 3) − y · 2 · y − y · (− 3) = = 2 · x 3 · y − 3 · x 3 + 4 · x 2 · y 2 − 6 · x 2 · y + 2 · x · y 3 - − 3 · x · y 2 − 2 · x · y + 3 · x − 2 · y 2 + 3 · y
Ответ:
(x 2 + x · y − 1) · (x + y) · (2 · y − 3) = 2 · x 3 · y − 3 · x 3 + 4 · x 2 · y 2 − 6 · x 2 · y + + 2 · x · y 3 − 3 · x · y 2 − 2 · x · y + 3 · x − 2 · y 2 + 3 · y
Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter
Для умножения многочлена на многочлен существует очень легкое правило. Чтобы умножить два многочлена между собой, надо каждый член первого многочлена умножить на каждый член второго многочлена. После это полученные произведения сложить и привести подобные.
На рисунке представлена общая схема перемножения.
Решим пример представленный на рисунке.
(4*x + 8*x*y) * (2*x + 3*y - 4) =
4*x*2*x + 4*x*3*y + 4*x*(-4) + 8*x*y*2*x + 8*x*y*3*y + 8*x*y*(-4) =
8*x^2 + 12*x*y - 16*x + 16*x^2*y + 24*x*y^2 - 32*x*y
Теперь приводим подобные слагаемые и получаем многочлен в стандартном виде.
8*x^2-20* x*y - 16*x + 16*x^2*y + 24*x*y^2
Если необходимо перемножить многочлены, у которых только одна переменная то можно умножение производить с помощью таблицы.
Рассмотрим пример:
Требуется перемножить два полинома x^5 +x^3 - 2*x^2 +3 и 2*x^4 - 3*x^3 + 4*x^2 - 1.
Для начала выпишем их коэффициенты. При чем в порядке убывания степеней неизвестных переменных, то есть от большей степени к меньшей. Если переменной в какой-то степени нет, то коэффициент взять равным нулю.
Таким образом, для полинома x^5 +x^3 - 2*x^2 +3 коэффициенты следующие 1; 0; 1; -2; 0; 3
Для полинома 2*x^4 - 3*x^3 + 4*x^2 - 1 коэффициенты 2; -3; 4; 0; -1.
Теперь записываем одни коэффициенты горизонтально, а другие вертикально. Теперь каждый из элемент из вертикального столбца умножаем на каждый элемент из горизонтального. И при каждом новом элементе сдвигаем на одну позицию вправо. Далее полученные ряды суммируем по столбцам. Как при умножении чисел в столбик, но только результат полученный после сложения не переносятся в следующий разряд.
Посмотрите на рисунке какая таблица должна получится.
Теперь остается записать ответ.
2*x^9 - 3*x^8 + 6*x^7 - 7*x^6 + 9*x^5 - 2*x^4 - 10*x^3 + 14*x^2 -3.
Нужна помощь в учебе?
Предыдущая тема:
Среди различных выражений, которые рассматриваются в алгебре, важное место занимают суммы одночленов.
Приведем примеры таких выражений:
\(5a^4 - 2a^3 + 0,3a^2 - 4,6a + 8 \)
\(xy^3 - 5x^2y + 9x^3 - 7y^2 + 6x + 5y - 2 \)
Сумму одночленов называют многочленом. Слагаемые в многочлене называют членами многочлена. Одночлены также относят к многочленам, считая одночлен многочленом, состоящим из одного члена.
Например, многочлен
\(8b^5 - 2b \cdot 7b^4 + 3b^2 - 8b + 0,25b \cdot (-12)b + 16 \)
можно упростить.
Представим все слагаемые в виде одночленов стандартного вида:
\(8b^5 - 2b \cdot 7b^4 + 3b^2 - 8b + 0,25b \cdot (-12)b + 16 = \)
\(= 8b^5 - 14b^5 + 3b^2 -8b -3b^2 + 16 \)
Приведем в полученном многочлене подобные члены:
\(8b^5 -14b^5 +3b^2 -8b -3b^2 + 16 = -6b^5 -8b + 16 \)
Получился многочлен, все члены которого являются одночленами стандартного вида, причем среди них нет подобных.
Такие многочлены называют многочленами стандартного вида
.
За степень многочлена стандартного вида принимают наибольшую из степеней его членов. Так, двучлен \(12a^2b - 7b \) имеет третью степень, а трехчлен \(2b^2 -7b + 6 \) - вторую.
Обычно члены многочленов стандартного вида, содержащих одну переменную, располагают в порядке убывания показателей ее степени.
Например:
\(5x - 18x^3 + 1 + x^5 = x^5 - 18x^3 + 5x + 1 \)
Сумму нескольких многочленов можно преобразовать (упростить) в многочлен стандартного вида.
Иногда члены многочлена нужно разбить на группы, заключая каждую группу в скобки. Поскольку заключение в скобки - это преобразование, обратное раскрытию скобок, то легко сформулировать правила раскрытия скобок:
Если перед скобками ставится знак «+», то члены, заключаемые в скобки, записываются с теми же знаками.
Если перед скобками ставится знак «-», то члены, заключаемые в скобки, записываются с противоположными знаками.
Преобразование (упрощение) произведения одночлена и многочлена
С помощью распределительного свойства умножения можно преобразовать (упростить) в многочлен произведение одночлена и многочлена. Например:
\(9a^2b(7a^2 - 5ab - 4b^2) = \)
\(= 9a^2b \cdot 7a^2 + 9a^2b \cdot (-5ab) + 9a^2b \cdot (-4b^2) = \)
\(= 63a^4b - 45a^3b^2 - 36a^2b^3 \)
Произведение одночлена и многочлена тождественно равно сумме произведений этого одночлена и каждого из членов многочлена.
Этот результат обычно формулируют в виде правила.
Чтобы умножить одночлен на многочлен, надо умножить этот одночлен на каждый из членов многочлена.
Мы уже неоднократно использовали это правило для умножения на сумму.
Произведение многочленов. Преобразование (упрощение) произведения двух многочленов
Вообще, произведение двух многочленов тождественно равно сумме произведении каждого члена одного многочлена и каждого члена другого.
Обычно пользуются следующим правилом.
Чтобы умножить многочлен на многочлен, надо каждый член одного многочлена умножить на каждый член другого и сложить полученные произведения.
Формулы сокращенного умножения. Квадраты суммы, разности и разность квадратов
С некоторыми выражениями в алгебраических преобразованиях приходится иметь дело чаще, чем с другими. Пожалуй, наиболее часто встречаются выражения \((a + b)^2, \; (a - b)^2 \) и \(a^2 - b^2 \), т. е. квадрат суммы, квадрат разности и разность квадратов. Вы заметили, что названия указанных выражений как бы не закончены, так, например, \((a + b)^2 \) - это, конечно, не просто квадрат суммы, а квадрат суммы а и b. Однако квадрат суммы а и b встречается не так уж часто, как правило, вместо букв а и b в нем оказываются различные, иногда довольно сложные выражения.
Выражения \((a + b)^2, \; (a - b)^2 \) нетрудно преобразовать (упростить) в многочлены стандартного вида, собственно, вы уже встречались с
таким заданием при умножении многочленов:
\((a + b)^2 = (a + b)(a + b) = a^2 + ab + ba + b^2 = \)
\(= a^2 + 2ab + b^2 \)
Полученные тождества полезно запомнить и применять без промежуточных выкладок. Помогают этому краткие словесные формулировки.
\((a + b)^2 = a^2 + b^2 + 2ab \) - квадрат суммы равен сумме квадратов и удвоенного произведения.
\((a - b)^2 = a^2 + b^2 - 2ab \) - квадрат разности равен сумме квадратов без удвоенного произведения.
\(a^2 - b^2 = (a - b)(a + b) \) - разность квадратов равна произведению разности на сумму.
Эти три тождества позволяют в преобразованиях заменять свои левые части правыми и обратно - правые части левыми. Самое трудное при этом - увидеть соответствующие выражения и понять, чем в них заменены переменные а и b. Рассмотрим несколько примеров использования формул сокращенного умножения.
Добрый вечер.
Этот пост посвящён быстрому преобразованию Фурье. Будут рассмотрены прямое и обратное преобразования (в комплексных числах). В следующей части я планирую рассмотреть их применения в некоторых задачах олимпиадного программирования (в частности, одна задача про «похожесть» строк), а также рассказать про реализацию преобразования в целых числах.
БПФ - это алгоритм, вычисляющий значения многочлена степени n
=2
k
в некоторых n
точках за время O
(n
⋅logn
) («наивный» метод выполняет ту же задачу за время O
(n
2
)). За то же время можно выполнить и обратное преобразование. Так как складывать, вычитать и умножать массивы чисел гораздо легче, чем многочлены (особенно умножать), БПФ часто применяется для ускорения вычислений с многочленами и длинными числами.
Определения и способы применения
Для начала давайте определимся, что такое многочлен:P (x )=a 0 +x a 1 +x 2 a 2 +x 3 a 3 +... +x n -1 a n -1
Комплексные числа
Если Вы знакомы с комплексными числами, то можете пропустить этот пункт, в противном случае, вот краткое определение:x =a +i b , где i 2 =-1
Здесь a называется вещественной (Real ) частью, а b - мнимой (Imaginary ). В этих числах, как нетрудно заметить, можно извлекать корень из отрицательных (да и вообще любых) чисел - это очень удобно при работе с многочленам - как следует из основной теоремы алгебры, у каждого многочлена степени n имеется ровно n комплексных корней (с учётом кратности).
Также их очень удобно представлять в виде точек на плоскости:
Еще одним замечательным свойством комплексных чисел является то, что их можно представить в виде x
=(cosα+i
sinα)r
, где α - полярный угол «числа» (называется аргументом
), а r
- расстояние от нуля до него (модуль
). А при умножении двух чисел:
a
=(cosα+i
⋅sinα)r
a
b
=(cosβ+i
⋅sinβ)r
b
a
b
=(cosα+i
⋅sinα)(cosβ+i
⋅sinβ)r
a
r
b
a
b
=(cosα⋅cosβ-sinα⋅sinβ+i
(sinα⋅cosβ+cosβ⋅sinα))r
a
r
b
a
b
=(cos(α+β)+i
⋅sin(α+β))r
a
r
b
Их модули перемножаются, а аргументы складываются.
Комплексные корни из 1
Теперь давайте поймём, как выглядят комплексные корни n -ой степени из 1 . Пусть x n =1 , тогда его модуль, очевидно, равен единице, а n ⋅argx =2 πk , где k - целое. Это обозначает, что после n умножений числа на самого себя (т.е. возведения в n -ю степень) его аргумент станет «кратен» 2 π (360 градусам).Вспомним формулу числа, если известен аргумент и модуль, получаем:
α=2 π⋅x /n , где 0 x
ω i =cosα+i ⋅sinα
Т.е. если порисовать, то мы получим просто точки на окружности через равные промежутки:
Прошу заметить три вещи, которыми мы будем активно пользоваться (без них ничего не получится):
ω a ⋅ω b =ω (a +b )modn
ω 0 +ω 1 +ω 2 +... +ω n -1 =0
ω 0 n /2 =ω 2 n /2 =ω 4 n /2 =... =1 (при чётном n )
Из-за этих свойств именно в этих точках мы и будем считать значение многочлена. Разумеется, результаты необязательно будут вещественными, поэтому в программе потребуется работать с комплексными числами.
Почему сумма корней - ноль
Доказательство очень простое: пусть φ=ω 0 +ω 1 +... . Домножим обе части на ω 1 (!= 1). Т.к. ω i ⋅ω 1 =ω i +1 , то φ⋅ω 1 =ω 1 +ω 2 +... +ω n -1 +ω 0 . От перестановки слагаемых сумма не меняется, поэтому φ=φ⋅ω 1 , соответственно φ⋅(ω 1 -1 )=0 . Т.к. ω 1 != 1, то φ=0 .Как работает
Будем считать, что наш многочлен имеет степень n =2 k . Если нет, дополним старшие коэффициенты нулями до ближайшей степени двойки.Основная идея БПФ очень проста:
Пусть:
A (x )=a 0 +x a 2 +x 2 a 4 +... +x n /2 -1 a n -2 (четные коэффициэнты P )
B (x )=a 1 +x a 3 +x 2 a 5 +... +x n /2 -1 a n -1 (нечётные коэффициенты P ).
Тогда P (x )=A (x 2 )+x ⋅B (x 2 ).
Теперь применим принцип «разделяй и властвуй»: чтобы посчитать значения P в n точках (ω 0 ,ω 1 ,... ), посчитаем значения A и B рекурсивно в n /2 точках (ω 0 ,ω 2 ,... ). Теперь значение P (ω i ) восстановить достаточно просто:
P (ω i )=A (ω 2 i )+ω i ⋅B (ω 2 i )
Если обозначить за ξ i =ω 2 i точки, в которых мы считаем значения многочлена степени n /2 , формула преобразится:
P (ω i )=A (ξ i )+ω i ⋅B (ξ i )
Её уже можно загонять в программу, не забыв что i принимает значения от 0 до n -1 , а ξ i определено лишь от 0 до n /2 -1 . Вывод - надо будет взять i по модулю n /2 .
Время работы выражается рекуррентной формулой T (n )=O (n )+2 T (n /2 ). Это довольно известное соотношение и оно раскрывается в O (n ⋅log 2 n ) (грубо говоря, глубина рекурсии - log 2 n уровней, на каждом уровне суммарно по всем вызовам выполняется O (n ) операций).
Напишем что-нибудь
Вот пример неэффективной рекурсивной реализации БПФ:Slow FFT
#includeМожете добавить ввод-вывод и проверить правильность своей реализации. Для многочлена P (x )=4 +3 x +2 x 2 +x 3 +0 ⋅x 4 +0 ⋅x 5 +0 ⋅x 6 +0 ⋅x 7 значения должны получиться такими:
P (w 0 )=(1 0 .0 0 0 ,0 .0 0 0 )
P (w 1 )=(5 .4 1 4 ,4 .8 2 8 )
P (w 2 )=(2 .0 0 0 ,2 .0 0 0 )
P (w 3 )=(2 .5 8 6 ,0 .8 2 8 )
P (w 4 )=(2 .0 0 0 ,0 .0 0 0 )
P (w 5 )=(2 .5 8 6 ,-0 .8 2 8 )
P (w 6 )=(2 .0 0 0 ,-2 .0 0 0 )
P (w 7 )=(5 .4 1 4 ,-4 .8 2 8 )
Если это так - можете засекать время рекурсивного и наивного метода на больших тестах.
У меня на многочлене степени 2 12 эта реализация работает 62 мс, наивная - 1800 мс. Разница налицо.
Избавляемся от рекурсии
Для того, чтобы сделать процедуру нерекурсивной, придётся подумать. Легче всего, как мне кажется, провести аналогию с MergeSort (сортировка слиянием) и нарисовать картинку, на которой показаны все рекурсивные вызовы:
Как мы видим, можно сделать один массив, заполнить его изначально значениями fft(a 0 ), fft(a 4 ), fft(a 2 ), ... . Как несложно понять, номера a i - это «развёрнутые» в двоичном представлении числа 0 ,1 ,2 ,3 ,... . Например, 1 1 0 =0 0 1 2 ,4 1 0 =1 0 0 2 или 6 =1 1 0 2 ,3 =0 1 1 2 . Понять это можно следующим образом: при спуске на нижний уровень рекурсии у нас определяется еще один младший бит (с конца). А при «нормальной» нумерации бит определяется с начала. Поэтому нужно «развернуть» число. Это можно сделать «в лоб» за O (n ⋅log 2 n ), а можно динамическим программированием за O (n ) по следующему алгоритму:
- Пробежимся циклом от 0 до n -1
- Будем хранить и динамически пересчитывать номер старшего единичного бита числа. Он меняется, только когда текущее число - степень двойки: увеличивается на 1.
- Когда мы знаем старший бит числа, перевернуть всё число не составляет труда: «отрезаем» старший бит (XOR), переворачиваем остаток (уже посчитанное значение) и добавляем «отрезанную» единицу
Аргументами процедуры для слияния двух блоков будут два vector"а (естесственно, по ссылке, исходный и результат), номер стартового элемента первого блока (второй идёт сразу после) и длина блоков. Можно было бы конечно сделать и iterator"ами - для большей STL"ности, но мы ведь всё равно будем переносить эту процедуру внутрь основной для краткости.
Объединение блоков
void fft_merge(const vcd &src, vcd &dest, int start, int len) { int p1 = start; // Позиция в первом блоке int en1 = start + len; // Конец первого блока int p2 = start + len; // Позиция во втором блоке int en2 = star + len * 2; // Конец второго блока int pdest = start; // Текущая позиция в результатирующем массиве int nlen = len * 2; // Длина нового блока for (int i = 0; i < nlen; i++) { double alpha = 2 * M_PI * i / nlen; cd w = cd(cos(alpha), sin(alpha)); // Текущий корень dest = src + w * src; if (++p1 >= en1) p1 = start; if (++p2 >= en2) p2 = start + len; } }И основная процедура преобразования:
<< k) < n) k++; vi rev(n); rev = 0; int high1 = -1; for (int i = 1; i < n; i++) { if ((i & (i - 1)) == 0) // Проверка на степень двойки. Если i ей является, то i-1 будет состоять из кучи единиц. high1++; rev[i] = rev; // Переворачиваем остаток rev[i] |= (1 << (k - high1 - 1)); // Добавляем старший бит } vcd cur(n); for (int i = 0; i < n; i++) cur[i] = as]; for (int len = 1; len < n; len <<= 1) { vcd ncur(n); for (int i = 0; i < n; i += len * 2) fft_merge(cur, ncur, i, len); cur.swap(ncur); } return cur; }
Оптимизация
На многочлене степени 2 1 6 рекурсия работает 640 мс, без рекурсии - 500. Улучшение есть, но программу можно сделать еще быстрее. Воспользуемся тем свойством, что ω i =-ω i +n /2 . Значит, можно не считать два раза корень и a i ⋅ω j - синус, косинус и умножение комплексных чисел очень затратные операции.fft_merge()
for (int i = 0; i < len; i++) { double alpha = 2 * M_PI * i / nlen; cd w = cd(cos(alpha), sin(alpha)); // Текущий корень cd val = w * src; dest = src + val; dest = src - val; pdest++; if (++p1 >= en1) p1 = start; if (++p2 >= en2) p2 = start + len; }Перехо с такой оптимизацией называется «преобразованием бабочки». Программа стала работать 260 мс. Для закрепления успеха давайте предподсчитаем все корни из 1 и запишем их в массив:
fft_merge()
int rstep = roots.size() / nlen; // Шаг в массиве с корнями for (int i = 0; i < len; i++) { cd w = roots; cd val = w * src;fft()
roots = vcd(n); for (int i = 0; i < n; i++) { double alpha = 2 * M_PI * i / n; roots[i] = cd(cos(alpha), sin(alpha)); }Теперь скорость работы - 78 мс. Оптимизация в 8 раз по сравнению с первой реализацией!
Оптимизация по коду
На данный момент весь код преобразования занимает порядка 55 строк. Не сотню, но это достаточно много - можно короче. Дляначала избавимся от кучи лишних переменных и операций в fft_merge :void fft_merge(const vcd &src, vcd &dest, int start, int len) { int p1 = start; //int en1 = start + len; // Не используется, см. конец цикла int p2 = start + len; //int en2 = start + len * 2; // Аналогично int pdest = start; //int nlen = len * 2; // Используется только в следующей строчке //int rstep = roots.size() / nlen; int rstep = roots.size() / (len * 2); for (int i = 0; i < len; i++) { //cd w = roots; // Также используется только в следующей строчке //cd val = w * src; cd val = roots * src; dest = src + val; dest = src - val; pdest++, p1++, p2++; //if (++p1 >= en1) p1 = start; // Так как у нас теперь цикл не до 2len, а только до len, переполнения быть не может //if (++p2 >= en2) p2 = start + len; // Убираем } }
Теперь можно переместить цикл из fft_merge в основную процедуру (также можно убрать p2 , поскольку p2=p1+len - у меня это также дало небольшой выигрыш по времени. Что любопытно, если убрать p1=pdest , то у меня лично выигрыш по времени убивается):
fft()
for (int len = 1; len < n; len <<= 1) { vcd ncur(n); int rstep = roots.size() / (len * 2); for (int pdest = 0; pdest < n;) { int p1 = pdest; for (int i = 0; i < len; i++) { cd val = roots * cur; ncur = cur + val; ncur = cur - val; pdest++, p1++; } pdest += len; } cur.swap(ncur); }Как видите, само преобразование занимает не так много - 17 строк. Всё остальное - предподсчёт корней и разворот чисел. Если Вы готовы сэкономить код в обмен на время работы (O (n ⋅log 2 n ) вместо O (n )), можете заменить 13 строк разворота чисел на следующие шесть:
В начале процедуры fft()
vcd cur(n); for (int i = 0; i < n; i++) { int ri = 0; for (int i2 = 0; i2 < k; i2++) // Перебираем биты от младших к старшим ri = (ri << 1) | !!(i & (1 << i2)); // И приписываем в конец числа cur[i] = as; }В результате теперь код выглядит так:
vcd fft(const vcd &as) { int n = as.size(); int k = 0; // Длина n в битах while ((1 << k) < n) k++; vector
Обратное преобразование
Получить значения многочлена в точках - это, конечно, хорошо, но преобразование Фурье умеет больше - по этим значениям построить сам многочлен, причём за то же самое время! Оказывается, что если применить преобразование Фурье к массиву значений, как к коэффициентам многочлена, потом разделить результат на n и перевернуть отрезок с 1 до n -1 (нумерация с 0 ), то мы получим коэффициенты исходного многочлена.Код тут предельно простой - всё уже написано. Думаю, Вы справитесь.
Доказательство
Пусть мы применяем обратное преобразование к многочлену P (x ) с коэффициентами v i (исходный многочлен имел коэффициенты a i ):v i =a 0 +ω i a 1 +ω 2 i a 2 +ω 3 i a +...
Посмотрим на результат преобразования:
b i =v 0 +ω i v 1 +ω 2 i v 2 +ω 3 i v 3 +...
Подставим значения v j (помним, что ω a ω b =ω a +b m o d n :
Теперь давайте докажем один замечательный факт: при x ≠0 , ω 0 +ω x +ω 2 x +... +ω (n -1 )x =0 .
Доказывается аналогично тому, что сумма корней - ноль: обозначим за φ сумму, домножим обе части на ω x и посмотрим, что получилось.
Теперь применим этот факт к вычислению значения b i . Заметим, что все строки, кроме одной, в которой содержится a n -i , обнулятся.
Таким образом:
b i =a n -i ⋅(ω 0 +ω 0 +ω 0 +ω 0 +... )
b i =a n -i ⋅n
Что и требовалось доказать.
Применение
Вообще говоря, о применении я уже чуть-чуть говорил в начале статьи. В частности, теперь перемножение многочленов можно выполнять следующим образом:Быстрое перемножение многочленов
vcd a, b; // Многочлены // Чтение многочленов vcd a_vals = fft(a); vcd b_vals = fft(b); vcd c_vals(a_vals.size()); for (int i = 0; i < a_vals.size(); i++) c_vals[i] = a_vals[i] * b_vals[i]; vcd c = fft_rev(c_vals); // Вывод ответаЛегко заметить, что время работы этой программы - O (n ⋅log 2 n ) и самые трудоёмкие операции - преобразования Фурье. Также можно заметить, что если нам требуется вычислить более сложное выражение с двумя многочленами, то по-прежнему можно выполнять лишь три приобразования - сложение и вычитание также будут работать за линейное время. К сожалению, с делением не всё так просто, поскольку многочлен может случайно принять значение 0 в какой-нибудь из точек. UPD2: не забудьте, что степень произведения двух многочленов степени n будет равна 2n , поэтому при вводе следует добавить «лишние» нулевые старшие коэффициенты.
Если представить число в десятичной (или более) системе счисления, как многочлен с коэффициентами - цифрами, то умножение длинных чисел также можно выполнять очень быстро.
И, напоследок, задача, которую я разберу в следующем посте: у вас есть две строки одинаковой длины порядка 1 0 5 из букв A, T, G, C. Требуется найти такой циклический сдвиг одной из строк, чтобы совпало максимальное количество символов. Очевидно наивное решение за O (n 2 ), но есть решение при помощи БПФ.
Удачи!
UPD: Выложил код целиком на
Правило вычисления произведения многочленов.
Для того чтобы рассмотреть произведение многочленов, для начала вспомним, как умножить одночлен на многочлен.
Произведение одночлена и многочлена находится следующим образом:
- составляется произведение одночлена и многочлена.
- раскрываются скобки.
- группируются числа с числами, одинаковые переменные друг с другом.
- перемножаются числа и складываются степени соответствующих одинаковых переменных.
Рассмотрим теперь умножение двух многочленов на примере:
Пример 1
Умножим многочлен $x-y+z$ на многочлен $\ {xy}^5+y^6-{xz}^5$.
Вначале запишем произведение многочленов:
\[\left(x-y+z\right)({xy}^5+y^6-{xz}^5)\]
Сделаем следующую замену. Пусть $x-y+z=t$, получим:
Получили произведение одночлена на многочлен. Найдем его по выше изложенному правилу.
Раскроем скобки:
Сделаем обратную замену:
\[{\left(x-y+z\right)xy}^5+{\left(x-y+z\right)y}^6-{\left(x-y+z\right)xz}^5\]
В данном выражении мы видим присутствие трех произведений одночленов на многочлен. Найдем их по отдельности по выше изложенному правилу:
\[{\left(x-y+z\right)xy}^5=x{xy}^5-y{xy}^5+z{xy}^5={x^2y}^5-{xy}^6+z{xy}^5\] \[{\left(x-y+z\right)y}^6=xy^6-yy^6+zy^6=xy^6-y^7+zy^6\] \[{\left(x-y+z\right)xz}^5=x{xz}^5-y{xz}^5+z{xz}^5=x^2z^5-xyz^5+{xz}^6\]
Перепишем наше выражение:
\[\left({x^2y}^5-{xy}^6+z{xy}^5\right)+\left(xy^6-y^7+zy^6\right)-(x^2z^5-xyz^5+{xz}^6)\]
Раскроем скобки. Напомним, что если перед скобками стоит знак плюс, то знаки в скобках остаются неизменными, а если перед скобками стоит знак минус, то знаки в скобках изменятся на противоположные. Получим
\[{x^2y}^5-{xy}^6+z{xy}^5+xy^6-y^7+zy^6-x^2z^5+xyz^5-{xz}^6\]
Получили многочлен. Осталось только привести его к стандартному виду. Итого, в ответе, получим:
\[{x^2y}^5+xy^5z-y^7+zy^6-x^2z^5+xyz^5-{xz}^6\]
Присмотревшись к полученному результату, мы получим следующее правило умножения многочлена на многочлен:
Правило: Для того, чтобы умножить многочлен на многочлен, необходимо каждый член первого многочлена умножить на каждый член второго многочлен, сложить полученные произведения и полученный многочлен привести к стандартному виду.
Пример 2
Выполнить умножение $2x+y$ и $x^2+2y+3$.
Запишем произведение:
\[\left(2x+y\right)(x^2+2y+3)\]
\[\left(2x+y\right)\left(x^2+2y+3\right)=2x^3+4xy+6x+x^2y+2y^2+3y\]
Видим, что полученный многочлен имеет стандартный вид, значит умножение закончено.
Примеры задач на произведение многочленов
Пример 3
Выполнить умножение многочлена на многочлен:
а) $(2z+1)\ и\ (z^2-7z-3)$
б) $(1-4x^2)\ и\ (5y^2-3x-2)$
Решение:
а) $(2z+1)\ и\ (z^2-7z-3)$
Составим произведение:
\[(2z+1)\cdot (z^2-7z-3)\]
Раскроем скобки по правилу произведения многочленов:
б) $(1-4x^2)\ и\ (5y^2-3x-2)$
Составим произведение:
\[(1-4x^2)\cdot (5y^2-3x-2)\]
Раскроем скобки по правилу произведения многочленов:
Видим, что полученный многочлен имеет стандартный вид, следовательно:
Ответ: $5y^2-3x-2-20x^2y^2+12x^3+8x^2$.
в) $(2n-5n^3)\ и\ (3n^2-n^3+n)$
Составим произведение:
\[(2n-5n^3)\cdot (3n^2-n^3+n)\]
Раскроем скобки по правилу произведения многочленов:
Приведем данный многочлен к стандартному виду:
г) $(a^2+a+1)\ и\ (a^2-24a+6)$
Составим произведение:
\[(a^2+a+1)\cdot (a^2-24a+6)\]
Раскроем скобки по правилу произведения многочленов:
Приведем данный многочлен к стандартному виду.