то будет достаточно шеста умножений. Наименьшее значение показателя степени, при котором метод бинарного разложения оказьшается неоптимальным, -15 (подсказка: х" =[xf).

Вероятно, это покажется неожиданным, но простой метод поиска оптимальной последовательности умножений для вычисления jc" для произвольного и неизвестен. Единственный известный сегодня метод включает обширный поиск. Данная проблема подробно рассматривается в [39, раздел 4.6.3].

Метод бинарного разложения имеет версию, в которой бинарное представление степени сканируется слева направо [53, 32], что аналогично методу преобразования двоичного представления в десятичное слева направо. Инициализируем результат у значением 1 и сканируем двоичное представление показателя степени слева направо. Когда нам встречается нулевой бит, возводим у в квадрат; единичный бит приводит к возведению у в квадрат и умножению на х. Таким образом, х = д:"° вычисляется так:

•X .

Этот метод требует того же количества умножений, что и метод сканирования справа налево из листинга 11.6.

2" в Fortran

Компилятор ШМ XL Fortran использует следующее определение функции:

pow2(n) =

2", 0<л<30, -2\ « = 31, О, п < О или п й 32.

Здесь предполагается, что и и, и результат возведения в степень рассматриваются как знаковые целые числа. Стандарт ANSIASO Fortran требует, чтобы результат был нулевым при и<0. Данное выше определение при п > 31 представляется разумным в том плане, что это корректный результат вычислений по модулю 2, и согласуется с тем, что дают многократные умножения.

Стандартный способ вычисления 2" состоит в размещении числа 1 в регистре и сдвиге влево на и позиций. Этот способ не удовлетворяет определению Fortran, поскольку обычно величина сдвига рассматривается по модулю 64 или модулю 32 (на 32-битовом компьютере), что привадит к неверному результату для больших или отрицательных значений смещения.

Если ваш компьютер оснащен командой подсчета количества ведущих нулевых битов, то вычисление pow2(n) может быть выполнено следующим образом:

nlz

п»5

; II х<г-Ъ2 при п из диапазона от О до 31; в противном случае д: < 32

д. x»5 ; II х*г- \ при и из диапазона от О до 31; в противном случае д: = О pow2 <- д:« л ;

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

Если компьютер не имеет команды nlz, вместо нее можно использовать предикат *=0 (см. раздел 2.11), заменив вьфажение x»5 выражением x»31. Возможно, луч-

шим методом реализации предиката О < х S 31 является использование его эквивалент-

ности предикату дг<32 с упрощением выражения для него из раздела 2. И до -ix&{x-32). Такой метод дает нам рещение из пяти команд (четырех, если машина оснащена командой и-не).

X*-л &(я - 32); II х<0 тогда и только тогда, когда О < л < 31

X ir-х>>Ъ\; д:= 1 при 0<л<31,иначеО pow2 •«- дс « л ;

11.4. Целочисленный логарифм

Под "целочисленным логарифмом" подразумевается функция [log,, х\, где д: - положительное целое число, а - целое число, не меньшее 2. Обычно Ь=2 или 10; дадим таким функциям имена ilog2 и iloglO соответственно.

Вполне уместно расширить определение функции для д:=0, полагая ilog(0) = -l [7].

Для такого определения имеется ряд причин.

• Функция ilog2(x) оказывается при этом тесно связанной с функцией количества

ведущих нулевых битов nlz(x), так, что если одна нз этих функций реализована

аппаратно, то вычисление другой- задача совсем несложная: ilog2(jt:)-(-nlz(x) = 31.

• При этом легко вычисляется значение [log(x)], если воспользоваться формулой [log(x)] = ilog(x-l) +1, из которой вытекает, что ilog(O) = -1.

• Такое определение делает справедливым для х=1 (но не для д:=0) тождество ilog2(x + 2) = ilog2(x)-l.

• Это определение сохраняет справедливость тождества [log х\ = [(log,o 2) log2 xJ.

• При таком определении возможные значения функции ilog(x) представляют собой небольшое компактное множество (от -1 до 31 для функции ilog2(x) на 32-разрядном компьютере при беззнаковом дг), что позволяет использовать их для индексации таблиц.

• Это определение естественным путем вытекает из ряда алгоритмов вычисления ilog2(x) и iloglO(x).

К сожалению, данное определение некорректно для определения "количества цифр числа дг", которое равно ilog(x) + 1 для всех дг, кроме 0. Однако в силу большого количества преимуществ данное определение для д:=0 можно считать исключением из правила.

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

Целочисленный логарифм по основанию 2

Вычисление ilog2(д;), по сути, то же, что и вычисление количества ведущих нулевых

битов, которое рассматривалось в разделе 5.3. Все алгоритмы из этого раздела могут быть легко преобразованы для вычисления ilog2(jir) путем вычисления аЩх) с последующим вычитанием этого значения из 31 (в случае алгоритма из листинга 5.10 достаточно заменить строку return рор(-х) строкой return рор(х)-1.

Целочисленный логарифм по основанию 10

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

Для вычисления iloglO(x) вполне применим метод поиска в таблице. Вполне возможно использование бинарного поиска, но таблица так мала, что, пожалуй, лучше воспользоваться последовательным поиском. Такой метод использован в приведенном в листинге 11.7 алгоритме.

Листинг 11.7. Целочисленный логарифм по основанию 10, метод поиска в таблице

int iloglO(unsigned х) {

int i;

static unsigned table[11] = {O, 9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999, OxFFFFFFFF

for (i = -1; ; i++) {

if (x <= table[i+1]) return i;

Ha компьютере с базовым набором RISC-команд эта программа требует выполнения 9+4Llog,( xj команд, так что максимальное количество выполняемых команд - 45.

Программа из листинга 11.7 может быть легко преобразована в версию без использования таблицы. Выполнимая часть такой программы представлена в листинге 11.8. Этот метод хорошо работает на компьютере с быстрым умножением на 10.

Листинг 11.8. Целочисленный логарифм по основанию 10, метод умножений на 10

Р = 1;

for (i = -1; i <= 8; i++) { if (x < p) return i; p = 10*p;

return i;