for (j=0; j<LL; j++) ran u[j+KK-LL]=u[j] ; for (;j<KK;j++) ran u[j-LL]=u[j] ;

mainO { register int m; double a[2009]; /* элементарный критерий */ ranf.start(310952);

for (m=0;m<2009;m++) ranf.array(a,1009);

printf ("/..20f\n", ran.uCO]); /* 0.27452626307394156768 */

ranf.start(310952);

for (m=0;m<1009;m++) ranf.array(a,2009);

printf ("•/..20f\n", ran.uCO]); } /* 0.27452626307394156768 */

12. Простой линейный конгруэнтный генератор, подобный (1), не подходит, так как т чересчур мало. Хороший результат возможен при комбинации трех (не двух) таких генераторов с множителями и модулями (157,32363), (146,31727) и (142,31657), как советует П. Лекуер (Р. LEcuyer, САСМ 31 (1988), 747-748). Тем не менее лучшим методом является использование программ на языке С ran.array и ran.start со следующей заменой, чтобы сохранить все числа в области: long становятся int; ММ определяется как (1U«15) и тип переменной ss должен быть unsigned int. Тогда генерируются целые числа, содержащие 15 двоичных разрядов, из которых можно использовать все двоичные разряды. Начальное значение сейчас ограничено областью [0.. 32765]. "Программа элементарной проверки" напечатает Хюсокгосэ = 9387 при заданном начальном значении 12509.

13. Программа вычитания с заимствованием очень похожа на программу гап.аггау, но работает медленнее, поскольку сохраняет содержимое. Как в упр. 11, арифметику с плавающей точкой можно использовать с совершенной точностью. Это позволяет гарантировать "непересечение" последовательностей, полученных от различных начальных значений s путем инициализации генератора с (-п)-м элементом последовательности, где п = 2°. Этого требует вычисление Ь" mod (б* - Ь ± 1). Возведение в квадрат числа с основанием b по mod Ь* - Ь db 1, тем не менее, значительно сложнее, чем аналогичная операция в программе ran.start, и для к оно практически вьшолняется за приблизительно к операций вместо 0{к).

Оба метода, вероятно, практически генерируют последовательности одинакового качества, когда у них приблизительно те же самые значения к. Единственным различием между ними является лучшее теоретическое обоснование и, возможно, огромный период метода вычитания с заимствованием, анализ генератора Фибоначчи с запаздыванием менее полный. Опыт показывает, что можно было бы не уменьшать значение к в методе вычитания с заимствованием только из-за его теоретических преимуществ. Когда все это сказано и сделано, генератор Фибоначчи с запаздыванием кажется предпочтительнее с практической точки зрения. Метод вычитания с заимствованием является ценным, главным образом, потому, что его понимание дается нам благодаря превосходному поведению более простого приближения.

14. Имеем Хп+2оо = {Хп + Хп+ив) (по модулю 2); см. упр. 3.2.2-32. Следовательно, Уп+юо = Уп + Уп+26, когда п mod 100 > 73. Аналогично А„+200 = А„ + Ап+2б + Xn+gg-Значит, Уп+юо = Уп + Уп+2в + Уп+sg, когда п mod 100 < И. Таким образом, Уп+юо является суммой только двух или трех элементов {У„,..., Уп+дд} в 26% +11% всех случаев и преобладание нулей приводит к тенденции делать так, чтобы выполнялось равенство Уп+юо = 0.

Точнее, рассмотрим последовательность (ui, ка, •. ) = (126, 89,152,115, 78,..., 100, 63, 126,...), где un+i = - 37 + 100[к„ < 100]. Тогда

Хп+200 = {Хп + Xn+vi Н----+ Xn+vk-2 + A„ j) mod 2,

где Vj = Uj + (-IjtlOOhOO, например X+SOO = Xn + Xn+26 + An+lgg + An+152 = Xn +

An+26 + Ап+189 + An+52 + An+115. Если Bce индексы <n + tn>n + 100 +1, TO получим к членов выражения Уп+ioo, когда п mod 100 = 100 -( для 1 < t < 100. Случай, когда t = 63, является исключением, так как А + An+i + +Хп+б2 +Ап+1бз + An+i64 + • • •+An+i99 = 0. Здесь Уп+100 не зависит от {Yn,..., Ут1+99}. Случай, когда t = 64, интересен потому, что он дает 99 членов соотношения Уп+юо = Уп+i + Уп+2 + • • +Уп+99, которые имеют тенденцию становиться нулями несмотря на большое количество членов. Это происходит потому, что большая часть строк размерности 100, которые имеют 40 или меньше единиц, имеют одинаковую четность.

Когда существует соотношение из к членов, вероятность, что Уп+юо = 1, равна

= ее(Т-?)(.)ь-:/е(Т)-

Величина t принимает значения 100, 99, 1, 100, 99, 1, ... во время печати двоичных разрядов. Итак, мы определили, что ожидаемое число напечатанных единиц

равно 10(26р2 + 11рз+26р4+11рб+11р9+4р12+4р20+Зр28+р47+р74+р99+1/2)/100 К 14043.

Ожидаемое число напечатанных знаков равно 10 Ef=o ~ 28444, ожидаемое

число нулей равно к 14401.

Замеченное смещение пропадает, если отбрасывается больше элементов. Например, если использовать только 100 элементов программы га7г-аггаг/(о,300), вероятность может быть (26р5 + 22рб + 19pio + • • )/100. С программой га7г-аггаг/(о,400) дела обстоят хуже: здесь вероятность (15рз + 37рб + 15р9 + )/1.00, так как Хп+лоо = Хп + Хп+252-С программой гап.аггаг/(а,1009), рекомендованной в разделе, получаем вероятность (17р7 + Юрп + 2pi2 + )/100, что может быть обнаружено в ходе таких экспериментов, если порог для печати поднимается от 60 до, скажем, 75, но тогда предполагаемое число выходов равно всего лишь около 0.28 из миллиона испытаний.

[Это упражнение основано на идеях Й. Курита (Y. Kurita), X. Лииба (Н. Leeb) и М. Мацумото (М. Matsumoto), сообщенных автору в 1997 году.]

15. Следующая программа позволяет получить новые случайные целые числа, которые выражаются ran-arr-next{), начав с программы ran.start.

#define QUALITY 1009 /* рекомендуется уровень качества для

высокорезультативного использования */

long ran arr buf [QUALITY]; long ran arr sentinel=-l;

long *ran arr ptr=&ran arr sentinel; /* следующее случгшное

число или -1 */

#define ran arr next() (*ran arr ptr>=0? *ran arr ptr++: ran arr cycle0)

long ran arr cycle()

ran.array(ran arr buf.QUALITY); ran arr buf[100]=-1; ran arr ptr=ran arr buf+1; return ran arr buf[0];

РАЗДЕЛ 4.1

1. (1010)-2, (1011)-2, (1000)-2, (11000)-2, (11001)-2, (11110) 2.

2. (а) -(110001)2, -(11.001001001001 ...)2,-(11.00100100001111110110101 ...)2.

(b) (11010011) 2, (1101.001011001011 ...)-2 (111.0110010001000000101 ...)-2.

(c) (11111)3, (10.011011011011... )з, (10.0111111100010111110111111110...)з.

(d) -(9.4)i/io, -(...7582417582413)i/io, (... 3462648323979853562951413)i/io.

3. (1010113.2)2i.

4. (a) Между тА и rX. (b) У остатка в регистре гХ разделяющая точка находится между байтами 3 и 4; у частного в регистре гА разделяющая точка расположена на один байт правее младшего разряда регистра.

5. Представление в обратном коде получается путем вычитания из 999.., 9 = W - 1, вместо вычитания из 1000 ... О = IC.

6. (а, с) 2"-! - 1, -{2"- - 1); (Ь) 2"- - 1, -2.

7. Представление в дополнительном коде для отрицательного числа х может быть получено, если взять число 10" + х (п достаточно велико, чтобы число было положительным) и продолжить его влево при помощи бесконечного количества девяток. Представление в обратном коде можно получить обычным способом. (Эти два представления совпадают для бесконечных десятичных дробей, в противном случае представление в обратном коде имеет вид ... (а)99999 ..., а представление в дополнительном коде -.. .(а + 1)0000 ....) Данные представления имеют смысл, если считать, что значергае бесконечной суммы TV = 9 + 90 + 900 + 9000 Н----равно -1, поскольку N - 10N = 9.

См. также упр. 31, в котором рассматриваются системы р-адических чисел. Для чисел, представление которых по основанию р конечно, р-адическое представление совпадает с рассмотренным здесь представлением в дополнительном коде, но .между полем р-адических чисел и полем вещественных чисел не существует никакой прямой связи.

9. А BAD ADOBE FACADE FADED. [примечание. Вот другие "числовые фразы": DO А DEED А DECADE; А CAD FED А BABE BEEF, COCOA, COFFEE; BOB FACED A DEAD DODO.]

..., Аз, A2, Al, Ao; A i, A 2,... ..., вз, bi, bl, bo; b-i, b-2,

,03,02,oi,ao; a-i, 0-2,. , Ьз, 62, bl, bo; 6-1, b-2,....

A, =

afc,4-i-iiO»:j+i-2, • • • ,akj

bkj+i-2,-- , bkj

bj =bk,+,-i...bkj,

где (кп)-произвольная бесконечная последовательность целых чисел, удовлетворяющих неравенствам kj+i > kj.

11. (Описываемый ниже алгоритм выполняет как сложение, так и вычитание в зависимости от выбора знака "плюс" или "минус".)

Сначала устанавливается к 4- o„+i 4- ап+2 4- bn+i 4- bn+2 4- 0; затем для m = 0,1,... ... ,п + 2 вьшолняется следующее: устанавливается Ст Ят i Ьт + к; далее, если Ст > 2,

устанавливается к <--1ист-<- Ст-2; еми Ст < О, устанавливается А;4-1ист 4- Ст-1-2;

а если О < Cm < 1, то устанавливается А: 4- 0.

12. (а) Вычесть ±(... аз0а10)-2 из ±(... а40о20оо)-2 в негадвоичной системе.

(В упр. 7.1-18 приводится оригинальное решение задачи, полученное с использованием битовых операций над полным словом.)

(Ь) Вычесть (... 6зОЬ10)2 из (... 64062060)2 в двоичной системе.