Решение задачи о возведении в степень

Решение 1. Первое, что приходит в голову, это просто умножить число 1 n раз на x. Для этого введем накопитель p, который инициализируем значением 1, и выполним умножения в цикле FOR i := 1 TO n. Тут возникает вопрос: а что, если n отрицательно? Тогда бы надо вместо умножения делить! Но это более трудоемкая для процессора операция. Поэтому мы сначала возведем в (положительную!) степень -n, а затем, в момент формирования возвращаемого функцией значения, один раз произведем деление. Разумеется, для этого факт отрицательности показателя надо запомнить - в логической переменной positive. Получается следующий алгоритм:

positive := TRUE, если n > 0, и FALSE, если n < 0
n := |n|, если n < 0
p := 1
n раз p := p * x
Если positive, то ЗНАЧЕНИЕ := p,
иначе ЗНАЧЕНИЕ := 1 / p

А что произойдет при n=0?

Вот, наконец, реализация алгоритма:
 

 
Можно взять готовый файл power1.pas для проверки этой функции и оценки ее быстродействия.

Решение 2. Гораздо быстрее можно вычислить степень, используя двоичное разложение числа n. Например, чтобы возвести x в степень 10 = 1*8 + 0*4 + 1*2 + 0*1, достаточно перемножить восьмую и четвертую степени числа x. При этом, если действовать справа налево, то показатель степени числа x каждый раз удваивается, а не увеличивается на 1, как в прошлом решении. Сомножитель же берется в произведение только в том случае, если соответствующая цифра в двоичном разложении показателя n отлична от 0. Иначе говоря, только если частное от деления числа n на соответствующую степень двойки нечетно (Odd). Все это дает заметный выигрыш в производительности. Попробуйте разобрать алгоритм этого решения по тексту на Pascal (n SHR 1 для положительных n дает такой же результат, что и n DIV 2, но работает быстрее):
 

 
Вы можете взять готовый файл power2.pas для сравнения с предыдущим решением и убедиться, насколько это решение работает быстрее.

Решение 3. А теперь держитесь крепче за стул. Вот такое простое решение:
 

 
- дает еще большее быстродействие! Вы можете проверить это (файл power3.pas).
Хотя можно ожидать, что оно менее точное - отклонение от точного значения в каких-то там последних знаках больше, чем в предыдущих решениях.

Что доказывает этот пример? Вовсе не то, что использованные для вычисления Exp и Ln алгоритмы эффективнее, алгоритм Решения 2 наверняка быстрее. Но реализация этих алгоритмов оказалась быстрее за счет того, что они запрограммированы на языке Ассемблера, а не на Pascal, и сделано это профессионалами в программировании, а не простыми математиками.
Кроме того, третье решение гораздо серьезнее использует сопроцессор. А попробуйте-ка его отключить! Как тогда изменится быстродействие?

Разумеется, с учебной точки зрения это решение менее содержательно, чем предыдущие.