Стандартният начин на умножаване две числа (или полиноми) време изисква О (N2). По-долу ще бъде описано как да се намали времето за размножаване на O (п влезте н) използване на бързо преобразувание на Фурие (Фурие Жан Батист Жозеф).
Трябва да се отбележи, че ние се обмисля по-нататъшно умножение на полиноми се дължи на факта, че всяко число може да се изрази като стойността на полином в определен момент. За повечето означения удобно да тази точка, тъй като системата на основа (например, тази точка ще бъде 10 на десетичната система). След дългата брой ще бъде конкатенацията на желаните коефициентите на полинома, и всеки коефициент стойност не е отрицателен, а по-малко от основата на системата. В същото време, броят на ненулевите коефициенти е по-малък от броя на знаците в първоначалния брой.
Представяне на полиноми
Да започнем с това ние определяме ключовото понятие за по-нататъшно обсъждане на полинома. Полином А (х) в променливите х над поле F има формата:
А (х) = 0 х 0 + 1 х 1 + ... + A N -1 х п -1
Стойности принадлежат на поле Е. Тези стойности се наричат коефициентите на полинома. Най-големият експонат в условия с ненулеви коефициенти се нарича степента на полинома. Сборът на две полиноми ще се нарича полином, всеки коефициент на която е равна на сумата на съответните коефициенти на първоначалните полиноми. Това означава, че ако
Резултатът от умножението две полиноми ще им продукт - С (х) = А (х) В (х). Размножаването се извършва както следва: всеки термин на полином А (х) се умножава по всеки термин на полином В (х), след задействане работи подобни условия с равни сили.
одобрение
Степента на полином продукт е равна на сумата от степените на факторите:
степен (C) = степен (А) + степен (В)
Създаване коефициентите на полином вектор
Като се има предвид полином
след това коефициентите ще бъдат вектор = (а 0. 1. ..., с).
Създаване на набор от стойности на полином
Определи различни точки х п х 0. 1. ..., хп -1. Полином А (х) на степен по-малко от п е еднозначно определена от нейните стойности на тези точки, т.е. набор от п стойност двойки аргумент.
където YK = A (ХК), за к = 0, 1, ..., N-1.
полином представителство използване на стойностите на предварително определени места удобни за много операции: особено за умножение на полиноми е достатъчно да се размножават стойност във всяка от точките (стойности на полиномите трябва да бъдат посочени в същите места). Въпреки това, ние трябва да имаме предвид, че се добавят умножение на полиноми на степен, а произведение на две полиноми от степен по-малко от п може да има известна степен на голям п. Въпреки това, той със сигурност е по-малко от 2 п. така че за възстановителни работи доста 2 п точки. Така се умножи две полиноми на степен по-малко от п. полезно от самото начало да имат стойност на полиноми в п. и 2 N точки. След това, тези стойности могат да се умножат по време O (N) и да получите продукт, като набор аргумент стойност двойки.
Теорема (недвусмислието интерполация)
За всеки набор 0. Y 0), (х 1. у 1), ..., (х п -1. Y N -1)> аргумент стойност двойки (х всичко, което е различно) съществува уникален полином А (х) на степен по-малко от п. за които YK = A (ХК), за к = 0, 1, ..., N-1.
Доказателство. За да се докаже тази теорема може да бъде, за представяне на уравнение YK = A (ХК) в матрична форма.
След това е необходимо да се провери, че детерминантата на матрицата, съдържаща всички корените на полином, различна от нула, при условие, че всички XI са различни. От това следва, че матрицата не е в единствено число. Това означава, че матрицата е обратимо. С други думи, ние можем да намерим стойностите на колоната коефициентите на колоните.
забележка
Вие не може да се докаже теоремата, а просто да се позова на истината за интерполация формулата на Лагранж.
Увеличението на броя на полиноми
Ако се научите да се движи бързо по коефициентите на ценностите и обратно, а след това да се умножи полиноми могат да се размножават стойността им в статистическите данни, (коефициентите отиват в стойностите се размножават, се движи назад).
Човек може да използва всеки набор от N точки, но по-удобно им начин, може да се понижи превръщането и в двете посоки до O (п влезте н). Както ще видим по-късно, че е удобно да се взема като точки на комплексни корени на единството, в този случай, както на прехода ще бъде намален до т.нар дискретно преобразувание на Фурие и неговата обратна трансформация, която да вземе O (п влезте н) операции.
Представлява полиноми верига умножение определени векторни коефициенти.
Тук символите со и 2 п означават от сложни корените на единство на степен 2 п. Степенуване аз. Когато се умножи две полиноми на степен по-малко от N, получен полином от степен по-малко от 2 п. така че първо ние добавяме полиноми фактори нулевите коефициенти на по-висока степен. След това трябва да се справим с полиноми от степен по-малко от 2 п. и затова използват сложни корени на степен 2 п единици, предназначени 2 п ω и с I = 0, 1, ..., 2 п -1.
бързо умножаване на две полиноми Алгоритъмът може да се запише като:
- Удвояването на броя на коефициентите. Допълнение полиноми А (х) и В (х) нулеви водещи коефициенти, така че броят на елементите във всяка полином имат 2 п елементи.
- Изчисляване на стойности. С помощта на бърза трансформация на Фурие, за да се изчислят стойностите на полиноми А (х) и В (х) на точките, които са корените на степен 2 N на единство.
- Potochechenoe умножение. Pointwise умножаване на получените стойности на полиноми А (х) и В (х) един към друг. стойности в резултат на полином С (х) = А (х) В (х) в корените на степен 2 N на единство.
- Интерполация. Получаване на коефициентите на полином C (X) с помощта на обратна трансформация на Фурие.
Комплекс корени на единството
Комплекс корени на степен п на единица наречени комплексно число w че ω п = 1. Очевидно е, че има точно п комплексни корени за това уравнение. Тези корени са равномерно разпределени по окръжността на радиус единица центриран в основата, както е показано на илюстрацията.
Разтвори на уравнението ω п = 1, са на EXP на форма (2π IK / о), за к = 0, 1, ..., N-1. Стойност ω = ехр (2π I / о), наречени основната стойност на корен на степен на п единство.
Ние се въведат някои допълнителни отчети.
Лема 1 (намаляване)
За всяко цяло число к ≥ 0, п ≥ 0, г> 0 е вярно