В Ы Ч И С Л Е Н И Е С Т Е П Е Н Н О Й Ф У Н К Ц И И

Рассмотрим вычисление функции , где - целое неотрицательное значение (переменная может быть вещественного или целого типа).

Если , то вычисляется , после чего . При имеем .

Пусть . Для получения значения в виде

требуется выполнить 164 умножения. Однако возможна и другая схема вычислений:

½ 1-я степень

½ 2-я степень

½ 4-я степень

½ 8-я степень

½ 16-я степень

½ 32-я степень

½ 64-я степень

½ 128-я степень

=

Здесь требуется только 10 умножений.

В приведенной схеме используется разложение показателя по степеням числа 2:

165 = 128 + 32 + 4 + 1 .

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

Начальные значения переменных

Описание алгоритма:

1) если нечетное, то значение включается в состав произведения , после чего показатель степени уменьшается на 1;

2) если четное, то значение возводится в квадрат, после чего показатель степени уменьшается в 2 раза;

3) работа алгоритма продолжается до тех пор, пока

Проиллюстрируем работу алгоритма при рассмотренном выше значении

1) нечетное

2) четное

3) четное

4) нечетное

5) четное

6) четное

7) четное

8) нечетное

9) четное

10) четное

11) нечетное

Примечание. Деление на 2 осуществляется путем сдвига целочисленной двоичной переменной на один разряд вправо. Следовательно, здесь мы имеем 11 умножений, 7 операций сдвига и 3 вычитания, на что затрачивается значительно меньше машинного времени по сравнению с многократным умножением (164 операции умножения)..

Блок-схема программы:

Легко убедиться, что эта программа дает правильный результат при любом .

ProgramExponent;

Varm,n : word;

x,y,b : real;

Begin

Read(x,n);

y:=1; b:=x; m:=n;

Whilem>0 do

Begin

While not odd(m) do

Begin

m:=m div 2; b:=sqr(b);

End;

Dec(m); y:=y*b;

End;

Writeln('y = ',y:12);

End.

Комментарии к программе.

1. Проверка четности целой переменной m возможна двумя способами:

a) с помощью функции odd(m);

б) путем вычисления логического выражения m mod 2 = 1.

Первый способ более эффективен по скорости выполнения и размеру объектного кода.

Четность двоичного числа определяется значением его последнего разряда (0 или 1). Работа функции odd(m) сводится к логическому умножению значения m на целочисленную константу 0000 0000 0000 0001 и анализу полученного результата (0 или 1, что соответствует машинному представлению значений false и true). Другими словами, здесь имеет место . Такие действия выполняются быстрее, чем операция деления mod.

2. Процедура Writeln('y=',y:12). Печать вещественных значений в общем случае целесообразно выполнять в форме целой и дробной частей, разделенных точкой. Изображение вещественного числа в виде мантиссы и порядка предпочтительнее в тех случаях, когда диапазон возможных изменений соответствующей переменной очень большой, что имеет место в данной программе (здесь для печати всего числа отводится 12 позиций, при этом мантисса будет иметь 12 - 6 = 6 цифр).

3. В программе Exponent используется итерационный цикл. Количество его повторений зависит от значения показателя степени n.