бы уменьшить количество
бы уменьшить количество умножений. Это удается, если воспользоваться следующим свойством операции возведения в степень:
am=(am/2)2 при четных m, am=a(a(m-1)/2)2 при нечетных m.
Следуя ему, получаем улучшенный вариант: будем на каждом шаге до "обнуления" показателя степени
*
при нечетном значении показателя степени второго сомножителя - домножать первый сомножитель на значение основания степени второго сомножителя; уменьшать на 1 и затем делить пополам сам показатель;
*
при четном значении - возводить во вторую степень основание второго сомножителя, уменьшая при этом вдвое показатель степени.
Проиллюстрируем механизм предлагаемого алгоритма на примере. Пусть в качестве показателя степени предложено значение m=15.
am=a15=a1+14 =(a)*(a2)7=(a)*(a2)1+6 =(a*a2)*(a2)6 =(a*a2)*(a2)2*3 =(a*a2)*((a2)2)3 =(a*a2)*((a2)2)1+2 =(a*a2*(a2)2)*((a2) 2)2
Описанный механизм называется дихотомическим алгоритмом возведения в степень. (Заметим, кстати, что с применением
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
