Имитация алгоритма Шеханге-Штрассена

Перемножение полиномов и чисел с помощью преобразования Фурье ()

44. (1 задача, действ.Фурье2)ипредставить в виде вектора значений на точках. Перемножить значения, восстановить полином 4й степени по значениям, перевести в число с помощью поразрядного сдвига.

Схема решения:

Подставим наши аргументы, чтобы найти четыре уравнения на четыре (не известные нам пока) коэффициента:

(известно, для ускорения процесса второе уравнение вычесть из 4-гои посчитать их сумму найдетсяи связьи, подставив в первую строку найдетеи).

45. (1,5 задачи, комп. Фурье, Ш.Ш.) Перемножить алгоритмом типа Шеханге-Штрассена и. Использовать корни четвертой степени из 1:. (- они образуют геометрическую прогрессию с коэффициентом) Пусть

46. (0,5 задачи, действ.Фурье - начало) иперемножить как полиномы. Восстановить с помощью поразрядного сдвига. Сопоставить результат с прямым перемножением чисел. Пример

Подставляем 10 вместо х, чтобы найти результат перемножения

Проверка прямым перемножением

(т.е. решение верно).

//Пример2: ,