Два представления многочлена: коэффициенты и значения

Если ты знаешь, что умножение в значениях линейно, помнишь, сколько точек нужно для произведения, и понимаешь, почему наивный переход всё портит, листай до «Теперь сам».

Как думаешь, где умножать дешевле

Перемножить два многочлена степени 999 по коэффициентам - это миллион умножений: каждый коэффициент с каждым.

А теперь представь, что вместо коэффициентов у тебя есть значения обоих многочленов в двух тысячах точек. Сколько операций нужно, чтобы получить значения произведения в тех же точках?

Две тысячи. Значение произведения в точке - это просто произведение значений: (A·B)(x) = A(x) · B(x). Умножение из квадратичного стало линейным - осталось понять, во что обходится смена представления.

На что это похоже

Сложение в римских цифрах против арабских. XLVII + XXVI - мучение; 47 + 26 - две секунды. Числа те же, операция та же, разница только в ЗАПИСИ. Перевод из одной записи в другую стоит времени, но если операций много, он окупается. Представление многочлена значениями - такая же смена записи под задачу.

Механизм: два представления и цена операций

КОЭФФИЦИЕНТЫ        A = [a₀, a₁, ..., a_{n−1}]          A(x) = a₀ + a₁x + ... + a_{n−1}x^{n−1}
ЗНАЧЕНИЯ            A = [(x₀, A(x₀)), ..., (x_{n−1}, A(x_{n−1}))]   при РАЗЛИЧНЫХ x

многочлен степени n−1 однозначно задаётся n значениями
(через n точек с различными x проходит ровно один многочлен степени НЕ ВЫШЕ n−1:
 через (0,1) и (1,1) - это константа 1, у неё степень 0)

операция              по коэффициентам       по значениям
сложение              O(n)                   O(n)
умножение             O(n²)  свёртка         O(n)   поточечно
значение в ОДНОЙ из
  своих точек         O(n)   схема Горнера   O(1)   оно уже посчитано
значение в НОВОЙ
  точке               O(n)   схема Горнера   O(n²)  сначала интерполировать

схема Горнера: A(x) считают справа налево -
    ((a_{n−1}·x + a_{n−2})·x + a_{n−3})·x + ...  - n умножений и n сложений
интерполяция: восстановить коэффициенты по значениям; способ Лагранжа стоит O(n²)

ПЛАН УМНОЖЕНИЯ ЧЕРЕЗ ЗНАЧЕНИЯ

1. взять 2n−1 точек - столько коэффициентов у произведения (степень 2n−2).
   На практике берут БОЛЬШЕ: округляют вверх до степени двойки
2. вычислить значения A и B в этих точках        ← прямое преобразование
3. перемножить поточечно: C(xᵢ) = A(xᵢ)·B(xᵢ)     O(n)
4. восстановить коэффициенты C по значениям      ← обратное преобразование

Шаги 2 и 4 наивно стоят n² каждый: вычислить многочлен в одной точке - O(n) по Горнеру, а точек n; интерполяция Лагранжа - тоже n². Итого n² + n + n² = O(n²) - ровно столько же, сколько стоила свёртка. Весь замысел держится на том, чтобы переходы стоили меньше.

Правило

Многочлен степени n−1 полностью задаётся либо n коэффициентами, либо значениями в n различных точках. Умножение по коэффициентам - свёртка за O(n²), по значениям - поточечное произведение за O(n). Чтобы перемножить два многочлена степени n−1, значений нужно не n, а 2n−1: у произведения степень 2n−2. План такой: значения → поточечное умножение → обратно. Наивные переходы стоят O(n²) и съедают весь выигрыш; смысл появляется, только если переходы делать за n·log n - и это возможно при СПЕЦИАЛЬНОМ выборе точек.

Разбор: умножаем два многочлена через значения

Возьмём A(x) = 1 + 2x и B(x) = 3 + x. Оба степени 1, у произведения степень 2, значит нужно минимум три значения. Возьмём точки x = 0, 1, 2.

значения A:   A(0) = 1      A(1) = 3      A(2) = 5
значения B:   B(0) = 3      B(1) = 4      B(2) = 5

поточечно:    C(0) = 3      C(1) = 12     C(2) = 25

Теперь восстановим коэффициенты C(x) = c₀ + c₁x + c₂x² из трёх значений:

c₀           = 3                    (из C(0))
c₀ + c₁ + c₂ = 12
c₀ + 2c₁ + 4c₂ = 25

из второго: c₁ + c₂ = 9
из третьего: 2c₁ + 4c₂ = 22 → c₁ + 2c₂ = 11
вычитаем:    c₂ = 2,  c₁ = 7

C(x) = 3 + 7x + 2x²

Проверим прямым умножением: (1 + 2x)(3 + x) = 3 + x + 6x + 2x² = 3 + 7x + 2x². Сходится.

Обрати внимание на третий шаг: поточечное умножение заняло три операции. Вся работа ушла в вычисление значений и в решение системы - то есть в переходы. На маленьком примере это видно особенно ясно: сама «быстрая» часть почти бесплатна, а дорого стоит смена представления.

Разбор: почему точек нужно 2n, а не n

Частая ошибка - взять столько же точек, сколько коэффициентов у сомножителей.

A и B степени n−1 (по n коэффициентов)
произведение имеет степень (n−1) + (n−1) = 2n−2, то есть 2n−1 коэффициент

Если взять только n точек, значения произведения в них посчитаются верно - но восстановить по ним МНОГОЧЛЕН СТЕПЕНИ 2n−2 невозможно: через n точек проходит бесконечно много таких многочленов, и интерполяция вернёт не тот, что нужен, а единственный степени n−1.

пример: A(x) = B(x) = x  (n = 2 коэффициента: [0, 1])
произведение x², его значения в точках 0 и 1: 0 и 1
но через (0,0) и (1,1) проходит и прямая y = x, и парабола y = x²
двух точек мало, чтобы их различить

Поэтому в реализациях оба массива дополняют нулями до длины, не меньшей 2n−1, и только потом преобразуют. Заодно длину округляют вверх до степени двойки - это нужно уже самому быстрому преобразованию, которое делит пополам.

Что ломается без этого

Первое: брать n точек вместо 2n−1 - ответ будет неверным, причём правдоподобным. Второе: брать повторяющиеся точки: значения в них ничего нового не дают, и система становится вырожденной. Третье: считать, что переход в значения бесплатен: наивно он стоит n², и без быстрого преобразования вся затея бессмысленна. Четвёртое: забывать, что интерполяция - это решение системы, и на произвольных точках она численно неустойчива: у системы, связывающей коэффициенты со значениями, матрица составлена из степеней точек (её называют матрицей Вандермонда), и при близких точках её строки почти совпадают - маленькая ошибка в значении даёт большую в коэффициентах. Хорошо подобранные точки решают и эту проблему. Пятое: путать степень и число коэффициентов: у многочлена степени n−1 их n, и на единицу ошибаются постоянно.

Зачем это в работе

Идея «сменить представление, чтобы операция стала дешевле» - одна из самых общих в алгоритмах. Логарифмы превращают умножение в сложение; преобразование Фурье превращает свёртку в поточечное умножение; хеширование превращает сравнение строк в сравнение чисел. Везде схема одна: переход, дешёвая операция, переход обратно - и вопрос только в цене переходов. Конкретно для многочленов это даёт умножение больших чисел, фильтрацию сигналов и изображений, быстрый поиск подстрок и много чего ещё - но всё это работает только потому, что переход удалось сделать за n·log n. Как именно - следующий урок.

Теперь сам

Многочлены A(x) = 2 + x и B(x) = 1 + 3x. Сколько точек нужно взять? Перемножь через значения в точках 0, 1, 2 и проверь прямым умножением.

A(0) = 2   A(1) = 3   A(2) = 4
B(0) = 1   B(1) = 4   B(2) = 7

C(0) = 2   C(1) = 12  C(2) = 28

восстанавливаем C(x) = c₀ + c₁x + c₂x²:
c₀ = 2
c₀ + c₁ + c₂ = 12      →  c₁ + c₂ = 10
c₀ + 2c₁ + 4c₂ = 28    →  2c₁ + 4c₂ = 26  →  c₁ + 2c₂ = 13
вычитаем: c₂ = 3, c₁ = 7

C(x) = 2 + 7x + 3x²