венно вычислить начало второго цикла. Однако имеются и более эффективные алгоритмы - как в смысле времени выполнения, так и в смысле необходимой памяти.

Возможно, самый простой метод предложен Флойдом (R.W. Floyd) [39, раздел. 3.1, задача 6]. В этом алгоритме итеративно выполняется следующий процесс:

у=/Ш)

(где начальные значения хиу равны Хо). После и-го шага х=Х„ и у=Х2„. Затем эти значения сравниваются. Если они равны, значит, элементы последовательности Х„ и Х2п отделены друг от друга количеством элементов, кратным периоду Л т.е. 2п-п = п кратно Л. Чтобы найти индекс последовательность генерируется заново и Хо сравнивается с Х„, Xl - с Х„+1 и так до тех пор, пока не будет найден элемент Xf„ равный Х„+. И наконец, Л определяется путем дальнейшей генерации элементов и сравнением с элементами Х+и Xfi2--- Этот алгоритм требует небольшого количества памяти, но функция /при этом вычисляется многократно.

В алгоритме Госпера [25, item 132; 39, Ответы на упражнения к разделу 3.1, задача 7] определяется только период Я,, но не начальная точка fi первого цикла. Главное достоинство данного алгоритма в том, что в нем не требуется повторное вычисление функции/, а также скорость работы и экономное использование памяти. Алгоритм не ограничен какими-либо значениями; для работы ему требуется таблица размера logj (А) +1, где Л -

максимально возможный период. Это не так много: например, если заранее известно, что Л < 2, то достаточно массива из 33 слов.

В листинге 5.16 приведен код на языке С, реализующий алгоритм Госпера. В качестве параметров функции передается указатель на рассматривавшуюся функцию / и начальное значение Xq. Функция возвращает верхнюю и нижнюю границы ju и период Л. (Хотя алгоритм Госпера и не позволяет определить точное значение он позволяет вычислить его нижнюю и верхнюю границы / и /4, такие, что ц,-ц,+\< max (Я -1,1).) Алгоритм работает путем сравнения Хп (для и = 1, 2,...) с подмножеством (размером [logjnj + l)

предшествующих значений. Элементами данного подмножества являются ближайшие предшествующие Х„ такие, что i +1 заканчивается единичным битом (т.е. / - четное число, предшествующее и), i+l заканчивается ровно одним нулевым битом, i+l заканчивается ровно двумя нулевыми битами и т.д.

Листинг 5.16. Алгоритм Госпера

void ld Gosper(int (*f) (int), int XO, int *mu l, int *mu u, int *lambda)

int Xn, k, m, kmax, n, Igl; int T[33];

T[0] = XO; Xn = XO;

for (n = 1; ; п++) {

Xn = f(Xn);

kmax = 31 - nlz(n); Floor(log2 n)

for (k = 0; к <= kmax; k++)

if (Xn == T[k]) goto L;

% ГЛАВА 5. ПОДСЧЕТ БИТОВ

Вычисляем m = max{i i < n и ntz(i+l) = k}

m = ((((n » k) - 1) I 1) « k) - 1; *lambda = n - m;

Igl = 31 - nlz(*lambda -1); Ceil(log2 lambda)-!

*mu u = m; Верхняя граница mu

*mu l = m - max(l, 1 << Igl) + 1; Нижняя граница mu

Таким образом, сравнения выполняются так:

X,: Х.Х Х: X.Xi.Xj

Xi Xf,X,,Xj

Х-.Х.ХуХ А",:

8 • б» 3» 3» 7 Хц

Х XtXfXyX.j Xi

X:X,X,,X,X Ху(

14-13-11-7

14 -13 -11 X,X Xf,,X.J,X,X,Xf Xlв,X.,,X,X.,,X

Хц Ху,Х,,Х,Х.,

А,2: А,0, А",, А,,,Х,

Можно показать, что вычисления всегда завершаются во втором щткле, т.е. при п<ц + 1Х, Более подробно этот алгоритм описан в [39].

Функция линейки используется в задаче о Ханойских башнях. Перенумеруем и дисков от О до и-1. При каждом перемещении к, где к принимает значения от 1 до 2"-!, циклически перемещаем диск ntz() на минимальную разрешенную дистанцию вправо.

Функция линейки используется также при генерации отраженного бинного кода Грея (см. раздел 13.1). Начиная с произвольного и-битового слова на каждом шаге к (где к принимает значения от 1 до 2"-1), изменяем бит ntz(*).

ГЛАВА 6 ПОИСК в СЛОВЕ

6.1. Поиск первого нулевого байта

Необходимость в отдельной функции поиска нулевого банта возникает главнь»! образом из-за способа представления символьных строк в языке С. Строки не содержат явно указанной длины; вместо этого в конце строки помещается нулевой байт. В С для вычисления длины строки используется функция strien. Эта функция сканирует строку слева направо до тех пор, пока не находит нулевой байт, и возвращает количество просканиро-ванных байтов без учета нулевого.

Быстрая реализация функции strien может загружать в регистр целое слово за раз и искать в нем нулевой байт. На компьютерах, где первым хранится стЕфший байт слова, функция должна возвращать смещение первого нулевого байта слева. Удобно использовать значения от О до 3, которые соответствуют номеру нулевого байта в слове; если нулевого байта в слове нет, возвращается значение 4. Это значение по ходу поиска добавляется к длине строки. На компьютерах, где первым хранится младший байт, соответствующая проверка должна возвращать номер первого нулевого байта справа, поскольку порядок байтов при загрузке слова в регистр на таких компьютерах изменяется на обратный. Определим функции zbytel(jt) и zbyter(jt) ("00" обозначает нулевой байт, "пп" -

ненулевой байт, байт "хх" может быть как нулевым, так и ненулевым).

jc = OOxxxxxx, jt = nnOOxxxx, jt = nnnnOOxx,

zbytel(jt) =

jt = nnnnnnOO, x = nnnnnnnn.

zbyter(jt) =

jt = xxxxxxOO, jt = xxxxOOnn, jt = xxOOnnnn, X = OOnnnnnn, jt = nnimimnn.

В листинге 6.1 приведен код функвди zbytel(jt), которая ищет первый нулевой байта

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

Листинг 6.1. Поиск первого слева нулевого байта с использованием ветвления

int zbytel (unsigned х)

else else else

if if if

((X ((X ((X

else return

( (X » 24) OXOOFFOOOO) OxOOOOFFOO) OxOOOOOOFF)

0) 0) 0) 0)

return return return return

Для вычисления функции zbytel(jt) требуется выполнить от 2 до И базовых RISC-команд (И команд в случае, если в слове нет нулевых байтов, что является наиболее распространенной ситуацией для функции strien). Код для функции zbyter(jt) практически аналогичен коду zbytel (jt).