Стандартний спосіб множення двох чисел (або полиномов) вимагає часу O (n 2). Нижче буде описано, як зменшити час множення до O (n log n) за допомогою швидкого перетворення Фур'є (Fourier Jean Baptiste Joseph).
Потрібно відзначити, що далі ми розглядаємо множення саме полиномов через те, що будь-яке ціле число можна представити як значення деякого полінома в конкретній точці. Для більшості систем числення зручно брати в якості цієї точки підставу системи (наприклад, для десяткової системи цією точкою буде 10). Тоді довге число буде конкатенацией коефіцієнтів шуканого полінома, а значення кожного коефіцієнта буде невід'ємним і менше підстави системи. У той же час, кількість ненульових коефіцієнтів буде не більше кількості символів у вихідному числі.
подання полиномов
Для початку визначимо ключове для подальших міркувань поняття полінома. Поліном A (x) від змінної x над полем F має вигляд:
A (x) = a 0 x 0 + a 1 x 1 + ... + a n -1 x n -1
Значення належать полю F. Ці значення називаються коефіцієнтами полінома. Найбільший показник ступеня в членах з ненульовими коефіцієнтами називається ступенем полінома. Сумою двох поліномів будемо називати такий поліном, кожен коефіцієнт якої дорівнює сумі відповідних коефіцієнтів вихідних полиномов. Тобто, якщо
Результатом множення двох поліномів буде їхній колективний витвір - C (x) = A (x) B (x). Множення виконується так: кожний доданок многочлена A (x) множиться на кожний доданок многочлена B (x), після чого виконується приведення подібних доданків з однаковими ступенями.
затвердження
Ступінь многочлена-твори дорівнює сумі ступенів співмножників:
degree (C) = degree (A) + degree (B)
Завдання многочлена вектором коефіцієнтів
Нехай дано поліном
тоді вектором коефіцієнтів буде a = (a 0. a 1. ..., an).
Завдання многочлена набором значень
Фіксуємо n різних точок x 0. x 1. ..., x n -1. Многочлен A (x) ступеня нижче n однозначно визначається своїми значеннями в цих точках, тобто набором з n пар аргумент-значення.
де yk = A (xk), для k = 0, 1, ..., n -1.
Подання многочлена за допомогою значень в заданих точках зручно для багатьох операцій: зокрема, для множення досить помножити значення многочленів в кожній з точок (значення многочленів повинні бути задані в одних і тих же точках). Однак, треба мати на увазі, що при множенні ступеня многочленів складаються, і твір двох многочленів ступеня менше n може мати ступінь більше n. При цьому вона свідомо менше 2 n. так що для відновлення твори досить 2 n точок. Таким чином, множачи два многочлена ступеня менше n. корисно з самого початку мати значення многочленів не в n. а в 2 n точках. Потім ці значення можна перемножити за час O (n) і отримати уявлення твори у вигляді набору пар аргумент-значення.
Теорема (однозначність інтерполяції)
Для будь-якого безлічі 0. y 0), (x 1. y 1), ..., (x n -1. Y n -1)> пар аргумент-значення (всі x i різні) існує єдиний многочлен A (x) ступеня нижче n. для якого yk = A (xk), для k = 0, 1, ..., n -1.
Доведення. Довести цю теорему можна, представивши рівняння yk = A (xk) в матричному вигляді.
Потім потрібно перевірити, що визначник даної матриці, що містить всі корені полінома, ненульовий за умови, що всі xi різні. З цього випливає, що дана матриця невирождени. А це означає, що матриця оборотна. Інакше кажучи, ми можемо по стовпчику значень знайти стовпець коефіцієнтів.
Примітка
Можна не доводити цю теорему, а просто послатися на істинність інтерполяційної формули Лагранжа.
множення полиномов
Якщо навчитися швидко переходити від коефіцієнтів до значень і назад, то для множення многочленів можна буде множити їх значення в даних точках (від коефіцієнтів переходимо до значень, перемножуємо, переходимо назад).
При цьому можна використовувати будь-який набір з n точок, але вибравши їх зручним чином, можна скоротити час перетворення в ту і іншу сторону до O (n log n). Як ми побачимо пізніше, зручно взяти в якості точок комплексні корені з одиниці, в цьому випадку обидва переходу зведуться до так званого дискретного перетворення Фур'є і зворотного до нього перетворення, які виконуються за O (n log n) операцій.
Уявімо схему множення поліномів, заданих вектором коефіцієнтів.
Тут символи ω i 2 n позначають комлексного коріння з одиниці ступеня 2 n. зведені в ступінь i. При множенні двох многочленів ступеня менше n виходить багаточлен ступеня менше 2 n. тому для початку ми доповнюємо многочлени-співмножники нульовими коефіцієнтами старших ступенів. Після цього ми маємо справу з многочленами ступеня менше 2 n. і тому використовуємо комплексні коріння ступеня 2 n з одиниці, що позначаються ω i 2 n при i = 0, 1, ..., 2 n -1.
Алгоритм швидкого множення двох поліномів можна записати так:
- Подвоєння кількість коефіцієнтів. Доповнюємо поліноми A (x) і B (x) нульовими старшими коефіцієнтами так, щоб кількість елементів в кожному поліномі було 2 n елементів.
- Обчислення значень. За допомогою швидкого перетворення Фур'є обчислити значення многочленів A (x) і B (x) в точках, які є країнами ступеня 2 n з одиниці.
- Поточеченое множення. Крапка до крапки помножити отримані значення многочленів A (x) і B (x) один на одного. В результаті виходять значення многочлена C (x) = A (x) B (x) в коренях ступеня 2 n з одиниці.
- Інтерполяція. Отримати коефіцієнти многочлена C (x) за допомогою зворотного перетворення Фур'є.
Комплексні коріння з одиниці
Комплексним коренем ступеня n з одиниці називають таке комплексне число ω, що ω n = 1. Очевидно, що є рівно n комплексних коренів для даного рівняння. Ці корені рівномірно розподілені на окружності одиничного радіуса з центром в нулі, як показано нижче на ілюстрації.
Рішення рівняння ω n = 1 мають вигляд exp (2π ik / n), для k = 0, 1, ..., n -1. Значення ω = exp (2π i / n) називають головним значенням кореня ступеня n з одиниці.
Введемо декілька допоміжних тверджень.
Лемма 1 (про скорочення)
Для будь-яких цілих k ≥ 0, n ≥ 0, d> 0 вірно