Возведение полинома в степень

Калькулятор вычисляет заданную степень для заданного полинома.

Данный калькулятор возводит полином в степень. Для этого калькулятор производит несколько умножений используя Умножение многочленов. Полином можно задать последовательностью вещественных, рациоанльных или комплексных коэффициентов. Алгоритм описан сразу за калькулятором.

PLANETCALC, Возведение полинома в степень

Возведение полинома в степень

Задача
 
Результат
 
Дерево степеней
 

Алгоритм возведения в степень

Известно несколько алгоритмов, позволяющих оптимально возвести число в целую степень. Один из самых оптимальных: дерево степеней. Он описан в Искусстве программирования Дональда Кнута том 2 1. Алгоритм умножает результирующую величину на значения, полученные на предыдущих шагах, согласно заранее построенному дереву степеней (см. граф Дерево степеней).

К примеру, для того чтобы получить x23 нужно только 6 умножений:

Номер Операция Результат
1 x*x x2
2 x2 * x x3
3 x3 * x2 x5
4 x5 * x5 x10
5 x10 * x3 x13
6 x13 * x10 x23

Реализация алгоритма может использовать заранее просчитанное до какого-нибудь разумного значения дерево степеней.
Само дерево строится следующим алгоритмом:

  • для каждого значения степени на последнем уровне дерева:
  • сохранить показатель степени в переменную e
  • для каждого значения в цепочке степеней pi, (включая e и всех его родителей вплоть до 1) выполняем следующее:
  • к текущему узлу дерева добавим дочерний элемент со степенью pi + e , но только если он до сих пор еще не добавлен в другие узлы дерева

Двоичный алгоритм возведения в степень

Примечателен также двоичный алгоритм. Его производительность не уступает алгоритму дерева степеней до 22 степени включительно, далее он начинает несущественно проигрывать (количество умножений становится больше).

  • представим показатель степени в двоичной форме
  • создадим строку операций путем замены 1 на SX
  • заменим все двоичные нули на X
  • удалим первый SX
  • начиная слева направо выполняем для каждого символа строки операций:
  • умножаем на x если символ = 'X'
  • умножаем само на себя если символ = 'S'

Например, алгоритм требует 7 операций умножения для получения x23. Так как число 23 в двоичной форме это 10111 , то наша строка операций будет выглядеть так: SXXSXSXSX. Шаги умножения представлены далее:

Код Операция Результат
X x * x x2
S (x2 )2 x4
X x4 * x x5
S (x5 )2 x10
X x10 * x x11
S (x11 )2 x22
X x22 * x x23

  1. Дональд Кнут Искусство программирования, том 2, параграф. 4.6.3 Полиномиальная арифметика, Вычисление степеней 

Ссылка скопирована в буфер обмена
PLANETCALC, Возведение полинома в степень

Комментарии