Формула умножения многочлена на многочлен. Калькулятор онлайн.Упрощение многочлена.Умножение многочленов
Назад
Вперёд
Внимание! Предварительный просмотр слайдов используется исключительно в ознакомительных целях и может не давать представления о всех возможностях презентации. Если вас заинтересовала данная работа, пожалуйста, загрузите полную версию.
Цели урока: (Презентация. Слайд 2)
Образовательные:
- вывести правило умножения многочлена на многочлен;
- формировать умение применять это правило.
Развивающие:
- развитие внимания;
- формирование умения анализировать и обобщать знания по теме;
- развитие навыков устного счёта.
Воспитательные:
- воспитание аккуратности;
- воспитание устойчивого интереса к предмету.
Тип урока: Урок изучения и первичного закрепления новых знаний.
Ход урока
I. Устная работа (Презентация. Слайд 3)
Выполните умножение.
а) а (х – у);
б) 2p (3 – q);
в) –2х (х – 4);
г) 4y(у 3 + 0,25);
д) – 0,5 c 2 (c 3 + 2);
е) –5х (3х 2 – 4);
ж) 2a 4 (а 3 – 0,5);
з) –q 7 (q 3 – q 5).
II. Объяснение нового материала (Презентация. Слайд 4)
Объяснение проводится в несколько этапов согласно материалу учебника.
1. Вывести правило умножения многочлена на многочлен и наглядно представить его на слайде (или доске):
2. Сформулировать полученное правило, попросить нескольких учащихся повторить его.
3. Разобрать примеры применения правила.
Поскольку данная тема является новой для учащихся, целесообразно привести несколько несложных примеров непосредственного применения правила умножения двух многочленов. Примеры использования этого правила при решении ряда задач лучше рассмотреть на следующих уроках.
Пример 1. (Презентация. Слайд 5) Умножить многочлен (3a – 2b) на многочлен (2a + 3b).
Решение: (3a – 2b)(2a + 3b) = 3a * 2a + 3a * 3b + (– 2b) * 2a + (– 2b) * 3b = 6a 2 + 9ab – 4 ab – 6b 2 = 6a 2 + 5ab – 6b 2 .
Пример 2. (Презентация. Слайд 6) Упростите выражение: (2х – 3)(5 – х) – 3х(4 – х).
Решение: (2х – 3)(5 – х) – 3х(4 – х) = 10х – 2х 2 – 15 + 3х – 12х + 3х 2 = х 2 + х – 15.
Пример 3. (Презентация. Слайд 7) Докажем, что при любом натуральном значении п значение выражения (п + 1)(п + 2) – (3п – 1)(п + 3) + 5п(п + 2) + п +7 кратно 3.
Решение: (п + 1)(п + 2) – (3п – 1)(п + 3) + 5п(п + 2) + п +7 = п 2 + 2п + п + 2 – 3п 2 – 9п + п + 3 + 5п 2 + 10п + п +7 = 3п 2 + 6п + 12 = 3 (п 2 + 2п + 4).
III. Формирование умений и навыков (Презентация. Слайд 8)
За урок следует опросить как можно больше учащихся, чтобы убедиться, что они усвоили правило умножения многочлена на многочлен. Поэтому для выполнения каждого задания к доске можно вызывать сразу трёх учащихся.
1. № 677, № 678.
В этих заданиях на умножение многочленов каждый из множителей является линейным. Важно, чтобы учащиеся следили за точностью применения соответствующего правила и не ошибались в знаках.
2. № 680.
Эти задания несколько сложнее, поскольку помимо применения правила умножения многочленов учащиеся должны помнить свойства степеней.
в) 12a 4 – a 2 b 2 – b 4 ;
е) 56p 3 – 51p 2 + 10p.
3. № 682 (а, в).
а) (х + 10) 2 = (х + 10) (х + 10) = х 2 + 10х + 10х + 100 = х 2 + 20х + 100;
в) (3а – 1) 2 = (3а – 1) (3а – 1) = 9а 2 – 3а – 3а – 1 = 9а 2 – 6а + 1.
IV. Итоги урока (Презентация. Слайд 9)
– Как умножить одночлен на многочлен?
– Сформулируйте правило умножения многочлена на многочлен.
– Какие знаки будут иметь слагаемые, полученные при умножении многочленов:
а) (х + у) (а – b);
б) (n – m) (p – q)?
V. Домашнее задание: (Презентация. Слайд 10)
№ 679; № 681; № 682 (б, г).
Используемые учебники и учебные пособия: (Презентация. Слайд 11)
- Учебник “Алгебра 7”. Ю.Н.Макарычев, Н.Г.Миндюк, К.И.Нешков, С.Б.Суворова под редакцией С.А.Теляковского. Москва “Просвещение”.2010г.
- Рурукин А.Н., Лупенко Г.В., Масленникова И.А. Поурочные разработки по алгебре: 7 класс.
Использованное оформление.
Если числа обозначены различными буквами, то можно лишь обозначить из произведение; пусть, напр., надо число a умножить на число b, – мы можем это обозначить или a ∙ b или ab, но не может быть и речи о том, чтобы как-нибудь выполнить это умножение. Однако, когда имеем дело с одночленами, то, благодаря 1) присутствию коэффициентов и 2) тому обстоятельству, что в состав этих одночленов могут входить множители, обозначенные одинаковыми буквами, является возможность говорить о выполнении умножения одночленов; еще шире такая возможность при многочленах. Разберем ряд случаев, где возможно выполнять умножение, начиная с простейшего.
1. Умножение степеней с одинаковыми основаниями . Пусть, напр., требуется a 3 ∙ a 5 . Напишем, зная смысл возведения в степень, то же самое подробнее:
a ∙ a ∙ a ∙ a ∙ a ∙ a ∙ a ∙ a
Рассматривая эту подробную запись, мы видим, что у нас написано a множителем 8 раз, или, короче, a 8 . Итак, a 3 ∙ a 5 = a 8 .
Пусть требуется b 42 ∙ b 28 . Пришлось бы написать сначала множитель b 42 раза, а затем опять множитель b 28 раз – в общем, получили бы, что b берется множителем 70 раз. т. е. b 70 . Итак, b 42 ∙ b 28 = b 70 . Отсюда уже ясно, что при умножении степеней с одинаковыми основаниями основание степени остается без перемены, а показатели степеней складываются. Если имеем a 8 ∙ a, то придется иметь в виду, что у множителя a подразумевается показатель степени 1 («a в первой степени»), – следовательно, a 8 ∙ a = a 9 .
Примеры: x ∙ x 3 ∙ x 5 = x 9 ; a 11 ∙ a 22 ∙ a 33 = a 66 ; 3 5 ∙ 3 6 ∙ 3 = 3 12 ; (a + b) 3 ∙ (a + b) 4 = (a + b) 7 ; (3x – 1) 4 ∙ (3x – 1) = (3x – 1) 5 и т. д.
Иногда приходится иметь дело со степенями, показатели которых обозначены буквами, напр., xn (x в степени n). С такими выражениями надо привыкнуть обращаться. Вот примеры:
Поясним некоторые из этих примеров: b n – 3 ∙ b 5 надо основание b оставить без перемены, а показатели сложить, т. е. (n – 3) + (+5) = n – 3 + 5 = n + 2. Конечно, подобные сложения должно научиться выполнять быстро в уме.
Еще пример: x n + 2 ∙ x n – 2 , – основание x надо оставить без перемены, а показатель сложить, т. е. (n + 2) + (n – 2) = n + 2 + n – 2 = 2n.
Можно выше найденный порядок, как выполнять умножение степеней с одинаковыми основаниями, выразить теперь равенством:
a m ∙ a n = a m + n
2. Умножение одночлена на одночлен. Пусть, напр., требуется 3a²b³c ∙ 4ab²d². Мы видим, что здесь обозначено точкою одно умножение, но мы знаем, что этот же знак умножения подразумевается между 3 и a², между a² и b³, между b³ и c, между 4 и a, между a и b², между b² и d². Поэтому мы можем здесь видеть произведение 8 множителей и можем перемножить их любыми группами в любом порядке. Переставим их так, чтобы коэффициенты и степени с одинаковыми основаниями оказались рядом, т. е.
3 ∙ 4 ∙ a² ∙ a ∙ b³ ∙ b² ∙ c ∙ d².
Тогда мы сможем перемножить 1) коэффициенты и 2) степени с одинаковыми основаниями и получим 12a³b5cd².
Итак, при умножении одночлена на одночлен мы можем перемножить коэффициенты и степени с одинаковыми основаниями, а остальные множители приходится переписывать без изменения.
Еще примеры:
3. Умножение многочлена на одночлен. Пусть надо сначала какой-нибудь многочлен, напр., a – b – c + d умножить на положительное целое число, напр., +3. Так как положительные числа считаются совпадающими с арифметическими, то это все равно, что (a – b – c + d) ∙ 3, т. е. a – b – c + d взять 3 раза слагаемым, или
(a – b – c + d) ∙ (+3) = a – b – c + d + a – b – c + d + a – b – c + d = 3a – 3b – 3c + 3d,
т. е. в результате пришлось каждый член многочлена умножить на 3 (или на +3).
Отсюда вытекает:
(a – b – c + d) ÷ (+3) = a – b – c + d,
т. е. пришлось каждый член многочлена разделить на (+3). Также, обобщая, получим:
и т. п.
Пусть теперь надо (a – b – c + d) умножить на положительную дробь, напр., на +. Это все равно, что умножить на арифметическую дробь , что значит взять части от (a – b – c + d). Взять одну пятую часть от этого многочлена легко: надо (a – b – c + d) разделить на 5, а это уже умеем делать, – получим 
. Остается повторить полученный результат 3 раза или умножить на 3, т. е.
В результате мы видим, что пришлось каждый член многочлена умножить на или на +.
Пусть теперь надо (a – b – c + d) умножить на отрицательное число, целое или дробное,
т. е. и в этом случае пришлось каждый член многочлена умножить на –.
Таким образом, какое бы ни было число m, всегда (a – b – c + d) ∙ m = am – bm – cm + dm.
Так как каждый одночлен представляет собою число, то здесь мы видим указание, как умножать многочлен на одночлен – надо каждый член многочлена умножить на этот одночлен.
4. Умножение многочлена на многочлен . Пусть надо (a + b + c) ∙ (d + e). Так как d и e означают числа, то и (d + e) выражает какое-либо одно число.
(a + b + c) ∙ (d + e) = a(d + e) + b(d + e) + c(d + e)
(мы можем объяснить это и так: мы вправе d + e временно принять за одночлен).
Ad + ae + bd + be + cd + ce
В этом результате можно изменить порядок членов.
(a + b + c) ∙ (d + e) = ad + bd + ed + ae + be + ce,
т. е. для умножения многочлена на многочлен приходится каждый член одного многочлена умножать на каждый член другого. Удобно (для этого и был выше изменен порядок полученных членов) умножить каждый член первого многочлена сперва на первый член второго (на +d), затем на второй член второго (на +e), затем, если бы он был, на третий и т. д.; после этого следует сделать приведение подобных членов.
В этих примерах двучлен умножается на двучлен; в каждом двучлене члены расположены по нисходящим степеням буквы, общей для обоих двучленов. Подобные умножения легко выполнять в уме и сразу писать окончательный результат.
От умножения старшего члена первого двучлена на старший член второго, т. е. 4x² на 3x, получим 12x³ старший член произведения – ему подобных, очевидно, не будет. Далее мы ищем, от перемножения каких членов получатся члены с меньшею на 1 степенью буквы x, т. е. с x². Легко видим, что такие члены получатся от умножения 2-го члена первого множителя на 1-й член второго и от умножения 1-го члена первого множителя на 2-ой член второго (скобки внизу примера это указывают). Выполнить эти умножения в уме и выполнить также приведение этих двух подобных членов (после чего получим член –19x²) – дело нетрудное. Затем замечаем, что следующий член, содержащий букву x в степени еще на 1 меньшей, т. е. x в 1-ой степени, получится только от умножения второго члена на второй, и ему подобных не будет.
Еще пример: (x² + 3x)(2x – 7) = 2x³ – x² – 21x.
Также в уме легко выполнять примеры, вроде следующего:
Старший член получается от умножения старшего члена на старший, ему подобных членов не будет, и он = 2a³. Затем ищем, от каких умножений получатся члены с a² – от умножения 1-го члена (a²) на 2-ой (–5) и от умножения второго члена (–3a) на 1-ый (2a) – это указано внизу скобками; выполнив эти умножения и соединив полученные члены в один, получим –11a². Затем ищем, от каких умножений получатся члены с a в первой степени – эти умножения отмечены скобками сверху. Выполнив их и соединив полученные члены в один, получим +11a. Наконец, замечаем, что младший член произведения (+10), вовсе не содержащий a, получается от перемножения младшего члена (–2) одного многочлена на младший член (–5) другого.
Еще пример: (4a 3 + 3a 2 – 2a) ∙ (3a 2 – 5a) = 12a 5 – 11a 4 – 21a 3 + 10a 2 .
Из всех предыдущих примеров мы также получим общий результат: старший член произведения получается всегда от перемножения старших членов множителей, и подобных ему членов быть не может; также младший член произведения получается от перемножения младших членов множителей, и подобных ему членов также быть не может.
Остальным членам, получаемым при умножении многочлена на многочлен, могут быть подобные, и может даже случиться, что все эти члены взаимно уничтожатся, а останутся лишь старший и младший.
Вот примеры:
(a² + ab + b²) (a – b) = a³ + a²b + ab² – a²b – ab² – b³ = a³ – b³
(a² – ab + b²) (a – b) = a³ – a²b + ab² + a²b – ab² + b³ = a³ + b³
(a³ + a²b + ab² + b³) (a – b) = a 4 – b 4 (пишем только результат)
(x 4 – x³ + x² – x + 1) (x + 1) = x 5 + 1 и т. п.
Эти результаты достойны внимания и их полезно запомнить.
Особенно важен следующий случай умножения:
(a + b) (a – b) = a² + ab – ab – b² = a² – b²
или (x + y) (x – y) = x² + xy – xy – y² = x² – y²
или (x + 3) (x – 3) = x² + 3x – 3x – 9 = x² – 9 и т. п.
Во всех этих примерах, применяясь к арифметике, мы имеем произведение суммы двух чисел на их разность, а в результате получается разность квадратов этих чисел.
Если мы увидим подобный случай, то уже нет нужды выполнять умножение подробно, как это делалось выше, а можно сразу написать результат.
Напр., (3a + 1) ∙ (3a – 1). Здесь первый множитель, с точки зрения арифметики, есть сумма двух чисел: первое число есть 3a и второе 1, а второй множитель есть разность тех же чисел; потому в результате должно получиться: квадрат первого числа (т. е. 3a ∙ 3a = 9a²) минус квадрат второго числа (1 ∙ 1 = 1), т. е.
(3a + 1) ∙ (3a – 1) = 9a² – 1.
Также 
(ab – 5) ∙ (ab + 5) = a²b² – 25 и т. п.
Итак, запомним
(a + b) (a – b) = a² – 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: Выложил код целиком на
Одним из действий с многочленами является умножение многочлена на многочлен. В данной статье рассмотрим правило такого умножения и применим его при решении задач.
Правило умножения многочлена на многочлен
Зададим два многочлена 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