Такая программа требует выполнения примерно 10+6Llog,(XJ команд на компьютере

с базовым RISC-набором (считая умножение одной командой). Для х из диапазона от 10 до 99 требуется выполнение 16 команд.

Можно применить бинарный поиск, что позволит избавиться от циклов и не использовать таблицу. Такой алгоритм может сравнивать х с 10"*, затем с 10 или с 10* и т.д., до тех пор пока не будет найден показатель степени и, такой, что 10" < д: < 10"*. В этом случае нам потребуется выполнение от 10 до 18 команд, четыре или пять из которых будут командами ветвления (с учетом последнего безусловного перехода).

Программа, показанная в листинге 11.9, представляет собой модификацию бинарного поиска, которая имеет максимум четьфе ветвления на каждом из путей и написана в расчете на работу в первую очередь с небольшими значениями х. Она требует вьшолнения шести базовых RISC-команд для 10 S д: S 99 и от 11 до 16 команд при д: > 100.

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

int iloglO(unsigned х) {

if (X > 99)

if (X < 1000000)

if (X < 10000)

return 3 + ((int)(X - 1000) >> 31);

else

return 5 + ((int)(x - 100000) » 31);

else

if (X < 100000000)

return 7 + ((int)(x - 10000000) >> 31);

else

return 9 + ( (int) ((x-1000000000)b~x) » 31);

else

if (X > 9) return 1;

else return ((int)(x - 1) >> 31);

Команда сдвига в данной программе - знаковая (именно поэтому в программе использовано приведение типа (int)). Если в вашем компьютере эта команда отсутствует, можно воспользоваться одним из описанных далее вариантов, в которых используется беззнаковый сдвиг. Далее приведены три варианта замены первого оператора return. К сожалению, первые два из них требуют наличия команды вычитания из непосредственно задаваемого числа, которая на большинстве машин отсутствует. Последний вариант использует сложение с большой константой (две команды), но это не так важно для остальных операторов return, которые в любом случае работают с большими константами. Величина этой константы - 2 -1000.

return 3 - ((X - 1000) » 31); return 2 + ((999 - х) >> 31); return 2 + ((х + 2147482648) >> 31);

Четвертый оператор return можно заменить следующим: return 8 + ((X + 1147483648) 1 х) >> 31;

Здесь большая константа равна 2" -10. Такая замена позволяет избежать использования команды и-не и знакового сдвига.

Последняя конструкция if-else может быть заменена одной из приведенных ниже.

return ((int)(x - 1) » 31) I ((unsigned)(9 - x) » 31); return (X > 9) + (X > 0) - 1;

Обе они позволяют сэкономить команду ветвления.

Если компьютер оснащен командой вычисления nlz(x) или ilog2(x), то для вычисления

iloglO(x) существуют более эффективные и интересные способы. Так, например, программа из листинга 11.10 позволяет сделать это с помощью двух поисков в таблице [7].

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

int ilogio(unsigned х) {

int у;

static unsigned char tablel[33] = { 9, 9, 9, 8, 8, 8,

7, 7, 7, 6, 6, 6, 6, 5, 5, 5, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0

static unsigned table2[10] = { 1, 10, 100, 1000, 10000,

100000, 1000000, 10000000, 100000000, 1000000000

у = tablel[nlz(x)];

if (X < table2[y]) у = у - 1;

return у;

Таблица tablel дает нам приближение iloglO(x). Это приближение в основном правильное, однако для некоторых значений х (равного О и лежащего в диапазонах от 8 до 9, от 64 до 99, от 512 до 9999, от 8192 до 9999 и т.д.) оно завышено на 1. Если требуется коррекция получаемого значения, то используется таблица table2.

В этой схеме используется 73 байта для хранения таблиц, а код состоит из шести команд на машине IBM System/370 [7] (чтобы достичь этого, значения в таблице tablel должны бьпъ в четыре раза больше показанных). На RISC-компьютере с наличием команды вычисления количества ведущш нулевых битов требуется выполнение около десяти команд. Другие рассматривающиеся далее методы, по сути, являются виантами данного.

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

Метод состоит в замене инструкции if вычитанием после сдвига вправо на 31 позицию, что эквивалентно вычитанию знакового бита. Сложности возникают только при больших значениях дг>2+10; для решения этих проблем в table2 внесен дополнительный элемент (см. листинг 11.11).

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

int iloglO(unsigned х) {

int У;

static unsigned char tablel[33] = { 10, 9, 9, 8, 8, 8,

7, 7, 7, 6, 6, 6, 6, 5, 5, 5, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0

static unsigned table2[11] = { 1, 10, 100, 1000, 10000,

100000, 1000000, 10000000, 100000000, 1000000000, 0

у = tablel[nlz(x)];

у = у - ((X - table2[y]) » 31);

return y;

Эта программа требует вьшолнения примерно 11 команд на RISC-компьютере, оснащенном командой вычисленш количества ведущих нулевых битов, но в остальном обладающей "базовьпл" набором команд. Эту программу легко преобразовать так, чтобы для jc=0 она возвращала не значение -1, а значение О (для этого достаточно изменить последний элемент таблицы tablel на 1, т.е. заменить "о, о, о, о" на "о, о, о, i").

Еще один вариант состоит в замене первой таблицы вычитанием, умножением и сдвигом. Это оказывается возможным, так как log,(,x и logx связаны соотношением

log,o д: = log,(, 2• logj д:, где log,o 2 = 0.30103. Таким образом, iloglO(x) можно вычислить путем вычисления I cilog2(x)J с некоторой константой с и последующей коррекции полученного результата с использованием таблицы (подобно тому, как в листинге 11.11 для этого использовалась таблица table2).

Рассмотрим вопрос выбора константы более подробно. Итак, пусть log,(,2 = c + E, где о О - рациональное приближение log,„ 2 , представляющее собой подходящий множитель, и е>0. Тогда для д:>0

iloglO(x) = [log,,, д:] = [(с + e)log, д: [с logj х\ <. iloglO(x) = [с logj д: + е log2 дг J с ilog2(x)J <. iloglO(x) < [c(ilog2(x) +1) + е log xJ S

< cilog2(x) + c + ElogjX <,

< [c ilog2(x) J + [c + E logj xj + \.

Таким образом, если выбрать с так, что с + е log д: < 1, то [с ilog2(x) J аппроксимирует функцию iloglO(x) с ошибкой, равной О или +1. Кроме того, если полагать, что ilog2(0) = iloglO(O) = -1, то [с ilog2(0)J = iloglO(O), так как О < с < 1, поэтому нет необходимости в каком-то отдельном рассмотрении этого случая (конечно, могут быть и другие определения, которые также не будут требовать каких-либо дополнительных действий, например ilog2(0) = ilogl0(0) = 0).