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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 17:44, 29 апреля 2016.
TemplateDifinitionIcon.svg Определение «Определение - Быстрое возведение в степень (Fast exponentiation)»

(как правило, - ключевые параметры).

Алгоритм "слева направо"

Алгоритм "справа налево"

Сложность

Количество необходимых операций

  • Если не надо умножать одна операция (возведение)
  • Если 2 операции (возведение + умножение на предыдущ.)
в среднем 1,5 опер./бит

Трудоемкость

(рассмотрим группу мультипликативного кольца)
операция полиномиальна (полином первой степени от входа)

НО: операции умножения/деления занимают много времени создают спец. устройства, платы.