Глава 8. Быстрое возведение в степень :: Идеи реализации

Идеи реализации
	Глава 8. Быстрое возведение в степень

Идеи реализации

Представим, что оператора возведения в степень нет в нашем распоряжении, так что остаётся лишь умножать. Определение степени с целым неотрицательным показателем $x^{n}$ позволяет сделать вычисление с использованием $n - 1$ умножения. Но умножение — достаточно затратная операция (вспомним умножение в столбик). Поэтому постараемся свести к минимуму число выполняемых умножений.

К примеру, если показатель степени сам является степенью двойки, $n = 2^{m}$ , то потребуется всего лишь $m$ умножений, точнее, возведений в квадрат: $x^{2^{m}} = {({({(x^{2})}^{2})}^{2} \dots)}^{2} .$ Это полезное наблюдение можно распространить на общий случай, воспользовавшись очевидными равенствами: $x^{n} = \{\begin{cases} {(x^{2})}^{\frac{n}{2}} & при чётном n, \\ x {(x^{2})}^{\frac{n - 1}{2}} & при нечётном n . \end{cases}$ Можно отнестись к этим формулам как к рекурсивному способу вычисления степени. Конечно же эти соотношения нужно дополнить граничными условиями $x^{0} = 1$ , $x^{1} = x$ .

Оказывается, количество умножений, которое следует выполнить для возведения в степень в соответствии с описанной рекурсивной процедурой, вычисляется по формуле $μ_{n} = ζ_{n} + 2 ε_{n} - 2$ , где $ζ_{n}$ и $ε_{n}$ — количества соответственно нулей и единиц в двоичной записи числа $n$ . Эта величина растёт крайне медленно с ростом $n$ , о чём свидетельствует таблица:

$n$	$μ_{n}$
$1$	$0$
$10$	$4$
$100$	$8$
$1000$	$14$
$10000$	$17$
$100000$	$21$
$1000000$	$25$
$10000000$	$30$
$100000000$	$37$
$1000000000$	$41$
$10000000000$	$43$

Очень маловероятно, что нам придётся возводить что-то в $10000000000$ -ю степень, но, если бы пришлось, то мы обошлись бы всего сорока тремя умножениями!

Формула находится в полном согласии с рассмотренным ранее частным случаем, когда $n = 2^{m}$ и $ζ = m$ , $ε = 1$ . В общем же случае заметим, что цифры в двоичном разложении числа равны остаткам от многократного деления этого числа на два. Появление нулевой цифры пускает рекурсивный алгоритм по первому (чётному) пути, что добавляет одно лишнее умножение. Цифра один выбирает нечётную ветвь алгоритма, что требует двух дополнительных умножений.

Мы разберём, помимо наивной версии программы, не заслуживающей отдельного разговора из-за её тривиальности, ещё две: рекурсивную и итеративную. Оба варианта основаны на быстром методе возведения в степень.

Итеративные версии

Раньше мы обсуждали преимущества нерекурсивных алгоритмов перед рекурсивными. Было бы заманчиво реализовать быстрое возведение в степень без рекурсии, при помощи одного цикла. Эта задача оказывается не такой простой, как хотелось бы. Нам стоит вооружиться методом, который позволял бы строить циклы не в результате божественного откровения (оно посещает нас довольно редко), а целенаправленно. Метод построения цикла при помощи инварианта — как раз то, что нам сейчас нужно.

Построение цикла при помощи инварианта

Цель каждой команды в программе — приближать нас к решению поставленной задачи, то есть к ситуации, когда нужные переменные получат наконец нужные, правильно вычисленные значения. Единственная возможность достичь такой цели — менять значения переменных на новые, это делается путём присваивания. Посмотрим с этой точки зрения на команды, образующие тело цикла.

Пусть в программе задействован набор переменных $X = (x, y, \dots, z)$ . Назовём его состоянием программы. Цикл считается правильным, если в результате его работы выполнено нужное соотношение между переменными. Под соотношением понимается некоторое утверждение про переменные. Что значит утверждение? Рассмотрим функцию $G (X)$ , зависящую от состояния, и принимающую логическое значение. Равенство $G (X) = да$ означает, что утверждение выполняется, а в противном случае не выполняется. Функцию $G$ будем называть целевой функцией цикла.

Тело цикла состоит из команд, присваивающих переменным $X$ новые значения $F (X)$ : $X \leftarrow F (X)$ Таким образом строится рекуррентная последовательность состояний программы. Цель цикла достигнута, когда целевая функция примет истинное значение, так что в качестве условия цикла можно взять выражение $\neg G (X)$ : $\begin{array}{l} цикл пока \neg G (X) \\ X \leftarrow F (X) \\ конец цикла \end{array}$ Мы предполагаем, что к моменту входа в цикл переменные $X$ имели начальные значения $X_{0}$ .

Зачастую бывает неудобно вычислять условие завершения цикла $G (X)$ . Тогда, если повезёт, можно попытаться подобрать более сильное условие $Q (X)$ (то есть такое, что для всех $X$ выполняется $Q (X) \Rightarrow G (X)$ ), которое проще вычислить.

Весь этот формализм не отвечает на вопросы о том, как найти преобразование $F$ такое, чтобы цикл рано или поздно завершился, и как построить условие окончания цикла $Q (X)$ . Метод инвариантов помогает найти и преобразование, и условие.

Ключевую роль в методе играет инвариант цикла — ещё одна функция состояния, принимающая логические значения. Функция $I (X)$ называется инвариантом цикла, если выполнены условия:

$I (X_{0})$ — инвариант принимает истинное значение в начальном состоянии;
$I (X) \Rightarrow I (F (X))$ — истинность инварианта сохраняется при проходе цикла;
$I (X) \land Q (X) \Rightarrow G (X)$ — одновременная истинность инварианта и условия окончания цикла влекут истинность целевого условия.

Если перед входом в цикл позаботиться о выполнении условия $I (X)$ и подобрать преобразование $F (X)$ , при котором сохраняется истинность инварианта, а цикл когда-нибудь завершится, цель будет достигнута по завершении цикла.

Наивная версия

От абстрактных идей пора перейти к конкретным примерам. Построим алгоритм наивного вычисления степени $p = x^{n}$ .

Предусмотрим в программе набор переменных $X = (p, x, n)$ . Их начальные значения (перед входом в цикл) равны $X_{0} = (p_{0}, x_{0}, n_{0})$ . Значения $x_{0}$ и $n_{0}$ являются входными параметрами алгоритма.

Придумаем цикл, по завершении которого переменная $p$ получит значение ${x_{0}}^{n_{0}}$ , так что в качестве целевой функции примем $G (p, x, n) = (p = {x_{0}}^{n_{0}})$ .

Простейший (но отнюдь не самый быстрый) алгоритм сводит задачу о возведении в степень $n$ к задаче о возведении в степень $n - 1$ , так что в цикле переменная $n$ будет уменьшаться на единицу до своего обнуления. Поэтому условием окончания сделаем $Q (p, x, n) = (n = 0)$ .

Теперь нужно подобрать инвариант. Пусть в теле цикла переменным $(p, x, n)$ присваиваются новые значения $(p^{'}, x^{'}, n^{'})$ , причём, как мы решили ранее, $n^{'} = n - 1$ . Нетрудно проверить, что функция $I (p, x, n) = ({x_{0}}^{n_{0}} = p x^{n})$ годится на роль инварианта.

Действительно, $I (p_{0}, x_{0}, n_{0}) = ({x_{0}}^{n_{0}} = p_{0} {x_{0}}^{n_{0}})$ истинно, если положить $p_{0} = 1$ . Второе условие, которому должен удовлетворять инвариант, также выполнено. Поскольку должно выполняться $I (p, x, n) \Rightarrow I (p^{'}, x^{'}, n^{'})$ , то есть $({x_{0}}^{n_{0}} = p x^{n}) \Rightarrow ({x_{0}}^{n_{0}} = p^{'} {(x^{'})}^{n - 1})$ , достаточно положить $p^{'} = p x$ и $x^{'} = x$ , чтобы обеспечить инвариантность. Наконец, проверим третье условие, $I (p, x, n) \land Q (p, x, n) \Rightarrow Q (p, x, n)$ , то есть $({x_{0}}^{n_{0}} = p x^{n}) \land (n = 0) \Rightarrow (p = {x_{0}}^{n_{0}})$ . Очевидно, и оно выполняется. Проверяя условия, мы заодно нашли преобразования, происходящие в теле цикла.

Мы пришли к алгоритму $\begin{array}{l} p \leftarrow 1 \\ цикл пока n \neq 0 \\ (p, n) \leftarrow (p x, n - 1) \\ конец цикла \end{array}$

Читатель, возможно, недоумевает, зачем понадобились столь сложная подготовка для получения столь очевидного алгоритма. Возможно, быстрый вариант итеративного алгоритма более убедительно продемонстрирует мощь метода инвариантов.

Быстрая итеративная версия

Отличие быстрого алгоритма от наивного состоит в том, что в цикле переменная $n$ вместо того, чтобы уменьшаться на единицу, уменьшается примерно вдвое. Точнее, если $n$ чётно, оно делится пополам, а если нечётно — уменьшается на единицу и затем делится пополам. Понятно, что со временем $n$ обратится в нуль, и это станет, как и в наивном алгоритме, условием завершения цикла.

Возьмём без изменений из наивного алгоритма инвариант $I (p, x, n) = ({x_{0}}^{n_{0}} = p x^{n})$ , и станем добиваться, чтобы выполнялось $I (p, x, n) \Rightarrow I (p^{'}, x^{'}, n^{'})$ , где на этот раз $n^{'} = \{\begin{cases} \frac{n}{2} & при чётном n, \\ \frac{n - 1}{2} & при нечётном n . \end{cases}$ Тогда придётся обеспечить выполнение условия $({x_{0}}^{n_{0}} = p x^{n}) \Rightarrow \{\begin{cases} {x_{0}}^{n_{0}} = p^{'} {(x^{'})}^{\frac{n}{2}} & при чётном n, \\ {x_{0}}^{n_{0}} = p^{'} {(x^{'})}^{\frac{n - 1}{2}} & при нечётном n, \end{cases}$ то есть $p x^{n} = \{\begin{cases} p^{'} {(x^{'})}^{\frac{n}{2}} & при чётном n, \\ p^{'} {(x^{'})}^{\frac{n - 1}{2}} & при нечётном n . \end{cases}$ Чтобы это равенство выполнялось, достаточно положить $p^{'} = \{\begin{cases} p & при чётном n, \\ p x & при нечётном n, \end{cases} x^{'} = x^{2} .$

Результатом наших изысканий стал алгоритм $\begin{array}{l} p \leftarrow 1 \\ цикл пока n \neq 0 \\ если n mod 2 = 1 \\ p \leftarrow p x \\ n \leftarrow n - 1 \\ конец если \\ x \leftarrow x^{2} \\ n \leftarrow \frac{n}{2} \\ конец цикла \end{array}$

Следует признаться, что этот алгоритм мы первоначально составили, не прибегая к методу инвариантов. Программа хорошо работала, но, несмотря на её краткость, оказалась трудной для понимания. Мы никак не могли подобрать нужных слов, чтобы объяснить её читателю и доказать её правильность. И только метод инвариантов дал и объяснение, и доказательство.

Не стоит считать, что метод инвариантов делает создание любого цикла рутинной задачей. Остаётся ещё большой простор для творчества. Например, построение инварианта во многих случаях является не самым очевидным делом. Поэтому расскажем, какие соображения привели нас к инварианту $I (p, x, n) = ({x_{0}}^{n_{0}} = p x^{n})$ . В поисках инвариантного соотношения между переменными программы, сохраняющего истинность при повторениях тела цикла, мы составили таблицу значений этого набора переменных. Для примера мы выбрали возведение двойки в тринадцатую степень: $\begin{array}{r} p & x & n \\ 1 & 2 & 13 \\ 2 & 4 & 6 \\ 2 & 16 & 3 \\ 32 & 256 & 1 \\ 8192 & 65536 & 0 \end{array}$

Закономерность, выполняемая в каждой строке таблицы, была быстро найдена: значение выражения $p x^{n}$ оказалось одним и тем же, и равным как раз $2^{13}$ .

Оказывается, задача о быстром возведении числа в степень $n$ тесно связана вот с какой задачей. Представим вычислительную машину, которая располагает лишь одним регистром (ячейкой памяти), способным хранить целое неотрицательное число. Набор команд этой воображаемой машины содержит только две инструкции: $D$ удваивает содержимое регистра (от слова Double — удвоить) и $I$ увеличивает регистр на единицу (Increment — увеличить). Изначально регистр содержит ноль. Требуется найти наиболее короткую программу для машины, после выполнения которой в регистре окажется число $n$ . Программа — это некоторая конечная последовательность инструкций $D$ и $I$ .

Для любого заданного $n$ существует бесконечно много программ. К примеру, всегда годится программа $〈I⁣ I⁣ I⁣ \dots⁣ I〉$ (всего $n$ инструкций $I$ ). Кроме того, приписывание любого количества инструкций $D$ к началу правильной программы, очевидно, не меняет её правильность.

Получается своеобразная система счисления: каждому целому неотрицательному числу можно поставить в соответствие программу для его получения — слово над алфавитом из двух букв (или лучше сказать, цифр), $D$ и $I$ . Недостатком этой системы счисления является её многозначность: для каждого числа найдётся бесконечно много представлений. Можно попытаться устранить этот недостаток, если среди всевозможных представлений выбирать самое короткое. Но даже самое короткое представление не является единственным. Понятно, кратчайшее представление следует искать среди начинающихся с $I$ , так как если оно начинается с $D$ , его можно укоротить, выкинув это $D$ . Теперь заметим, что если $〈I⁣ I⁣ \dots〉$ — кратчайшее представление, то $〈I⁣ D⁣ \dots〉$ — также кратчайшее представление (увеличение единицы на единицу равносильно её удвоению). При всех остальных значениях регистра удвоение даёт больший результат, чем прибавление единицы. Эту единственную оставшуюся неоднозначность устраняем, потребовав дополнительно, чтобы в представлении не было подряд двух «цифр» $I$ . Полученное представление назовём каноническим.

Оказывается, каноническое представление можно легко получить из двоичной записи числа $n$ : нужно каждый ноль заменить на «цифру» $D$ , а каждую единицу — на «цифры» $D⁣ I$ . После того, как это будет сделано, следует отбросить «цифру» $D$ из начала полученной программы, если она там окажется. Например, для $n = 13 = 1101_{2}$ получается программа $〈I⁣ D⁣ I⁣ D⁣ D⁣ I〉$ . И действительно, $13 = (((0 + 1) \cdot 2 + 1) \cdot 2) \cdot 2 + 1$ .

Но какое же всё это имеет отношение к быстрому возведению в степень? Пусть имеется некоторое представление показателя степени $n$ . Это значит, что $n$ получается из нуля в результате последовательных увеличений на единицу или удвоений. Но прибавление единицы к показателю степени равносильно домножению всей степени на $x$ , а удвоение показателя — возведению степени в квадрат. Если в нашем распоряжении имеется готовое представление показателя степени, получаем алгоритм $\begin{array}{l} p \leftarrow 1 \\ цикл для каждой цифры δ из представления n \\ если δ = I \\ p \leftarrow p x \\ иначе \\ p \leftarrow p^{2} \\ конец если \\ конец цикла \end{array}$ Беда в том, что для получения «цифр» представления прежде придётся устроить другой цикл. Совместить оба цикла будет проблематично, поскольку «цифры» нужны в порядке их записи, то есть слева направо. При этом их гораздо проще получать справа налево (точно так же, как и цифры двоичной записи числа). Наше решение, ради которого мы занялись методом инвариантов, обходит эту трудность. Тот цикл неявно получает «цифры» представления показателя степени справа налево и в зависимости от очередной цифры выполняет нужные действия: $\begin{array}{l} цикл пока n \neq 0 \\ если n mod 2 = 1 \\ I \\ n \leftarrow n - 1 \\ иначе \\ D \\ n \leftarrow \frac{n}{2} \\ конец если \\ конец цикла \end{array}$ Здесь в случае $I$ следует выполнить команду $p \leftarrow p x$ , а в случае $D$ — команду $x \leftarrow x^{2}$ . Разумеется, перед циклом нужно присваивание $p \leftarrow 1$ . Получившийся алгоритм, как легко видеть, равносилен созданному ранее.

Основная трудность нашей задачи заключалась в создании алгоритма. Теперь, когда алгоритмы готовы, не составит никакого труда переложить их на Perl. В связи с этим мы опускаем раздел «Разработка» и сразу переходим к готовым программам.


Глава 8. Быстрое возведение в степень		Готовая программа

Информатика-54© А. Н. Швец