Возведение полинома в степень
Калькулятор вычисляет заданную степень для заданного полинома.
Данный калькулятор возводит полином в степень. Для этого калькулятор производит несколько умножений используя Умножение многочленов. Полином можно задать последовательностью вещественных, рациоанльных или комплексных коэффициентов. Алгоритм описан сразу за калькулятором.
Возведение полинома в степень
Алгоритм возведения в степень
Известно несколько алгоритмов, позволяющих оптимально возвести число в целую степень. Один из самых оптимальных: дерево степеней. Он описан в Искусстве программирования Дональда Кнута том 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 |
-
Дональд Кнут Искусство программирования, том 2, параграф. 4.6.3 Полиномиальная арифметика, Вычисление степеней ↩
Комментарии