Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 75
Текст из файла (страница 75)
Оба метода, вероятно, практически генерируют последовательности одинакового качества, когда у них приблизительно те же самые значения Й, Единственным различием между ними является лучшее теоретическое обоснование и, возможно, огромный период метода вычитания с заимствованием, анализ генератора Фибоначчи с запаздыванием менее полный. Опыт показывает, что можно было бы не уменьшать значение й в методе вычитания с заимствованием только иэ-за его теоретических преимуществ.
Когда все это сказано и сделано„генератор Фибоначчи с запаздыванием кажется предпочтительнее с практической точки зрения. Метгщ вычитания с заимствованием является ценным, главным образом, потому, что его понимание дается нам благодаря превосходному поведению более простого приближения. 14 Имеем Хп+па щ (Х» + Хя+шв) (па модулю 2); см. упр. 3.2.2 — 32.
Следовательно, У +!ое = — Уэ + Ъ'и~ге, когда и шод100 > 73. Аналогично Х эзео щ Хя + Хе+ы + Хя+вэ Значит, ),д.!со в У„+ У«ыа+ У«+в«, когда пшос)100 ( 11. Таким образом, У„э!ог является сул!мой только двух нли трех элементов (У„,..., У„+«е) а 26ЯЬ+ 11% всех случаев и преобладание нулей приводит к тенденпнн делать так, чтобы выполнялось равенство У +!ео = О. Точнее, рассмотрим последовательность (ам из,... ) = (126,89, 152, 115, 78,..., 100,63, 126,...), где и„+з = н — 37 + 100(н„ < 100), Тогда Х«+зса = (Х«+ Л«+»з + ' ' ' + Хлт»з з + Х»з„>) щоб 2, где с; = н; + (-ц~зсшч100, например Х+зсс ш Х„+ Х +ы+ Л;+ыз+ Х»ззз ш Х» + Х«+за+ Х«»~зе+ Х«з щ+ Х«+зы.
Если все индексы < я+ ( и > и+ 100+(. то получим )з членов выражения У»ще, когда л шоб 100 = 100-1 для 1 < ( < 100. Случай, когда ( = 63, является исключением, так как Х„+Х +~+ +Х„+щ+Х«+ыз+Л +из+ . +Х«+~за щ О Здесь У«»ни не зависит от (У«,..., У,+щ), Случай, когда З = 64, интересен потому, что он дает 99 членов соотношения 1'„~аа ги У ~ + У„+з+ . +1'„+зз, которые имеют тенденцию стшювиться нулями несмотря на большое количество членов.
Это происхолит потому, что большая часть строк размерности 100, которые имеют 40 или меньше единиц, имеют одинаковую четность. Когда существует ссютношение из )з членов, вероятностгч что 1' +ша = 1, равна Величина З принимает значения 100, 99, ..., 1, 100, 99, ..., 1, ... во время печати двоичных разрядов. Итак, мы определили, что ожидаемое число напечатанных единиц равно 10 (26рз+11рз+26рз+11рз+11рз+4ры+4рзо+Зры+рзг+рм+рзз+1/2)/100 = 14043.
Ожидаемое число напечатанных знаков равно 10е2, ('~)/2'~~ 28444, ожидаемое число нулей равно 14401. Замеченное смещение пропадает, если отбрасывается больше элементов. Например, если использовать только 100 элементов программы ган азтау(а,300), вероятность может быть (26рз + 22рз + 19р~е + )/100. С программой ган аггел(а,400) дела обстоят хуже: здесь вероятность (15рз + 37ре + 15рз + - )/100, так как Х„+зоз ш Л' + Л' +ыз. С программой гап азтау(а,.1009), рекомендованной в разделе, получаем вероятность (17рз + 10рп + 2р~з + )/100, что может быть обнаружено в ходе таких экспериментов.
если порог для печати поднимается от 60 до, скажем, 75, но тогда предполагаемое число выходов раино всего лишь около 0.28 из миллиона испытаний. (Это уира;кнение основано на идеях Й. Курита (Ъ". Кигзза), Х. «Тииба (Н. ВееЬ) и М. Мацумото (М. Магэипзосо), сообщенных автору в 1997 году.] 16. Следующая программа позволяет получить новые случайные целые числа которые выражаются ган агг нег((), начав с программы нзп згагб Ва«21пе 004ЬХТТ 1009 /» рекомендуется уровень качества дюз високорезультатвввого испольэовавия «/ 1опб гап агг„ьиу(0041177); 1опб гвл агг еептйве1 -1; 1опб»гап агт рсг пгеп агг еепсзпе1; /» следузжее случайное число илн -1 «/ эиеззпе гав агт пехсО («гап егг рсг> 07 «гап агг рсг++: гап агг сус1еО) 1опб гап агг сус1еО ( гэл актау(гап азт Ьиз,ЯОАЬТТТ); гап„агг Ьиз(100) -1; гап азт рсг гап агг Ъиу»1; гегизп таи агг Ьиз(0)и РАЗДЕЛ 6.1 1.
(1010)-г, (10П)-г, (1000)..г, ..., (ПООО)-г, (ПООЦ.-г, (ППО)-г, 2. (а) — (ПОООЦг, -(П.001001001001... )г, -(П.0010010000ПП ПОП0101 .. )г. (ь) (по1ооп), (по1.оо1опоо1оп... )-, (П1.опоо10001000000101 ... ) (с) (1ПП)„(10.0ПОПОПОП...)., (1041ППП100010П1ПОППППО...)г, (д) -(9.4)пл„-(... 7э82417582413)очо (... 3462648323979853562951413)иго. 3. (1О1ОП3.2)„. 4. (а) Меэкду гА и гХ. (Ь) У остатка в регистрегХ разделяющая точка находится между байтами 3 и 4; у частного в регистре гА разделяющая точка расположена на один байт правее иладщего разряда регистра. 5.
Представление в обратном коде получается путем вычитания из 999, 9 = 10» — 1, вместо вычитания из 1000... 0 = 10". 6. (а, с) 2» ' — 1, -(2» ' — Ц; (Ь) 2" ' — 1, — 2" '. 7. Представление в дополнительном коде для отрицательного числа х может быть полу- чщю, если взять число 10" + х (и достаточно велико, чтобы число было положительным) и продолжить его влево прн помощи бесконечного количества девяток. Представление в обратном коде можно получить обычным способом. (Зги два представления совпадают для бесконечных десятичных дробей, и противном случае представление в обратном коде имеет вид ... (а)99999...„а представление в дополнительном коде --...
(а + ЦОООО....) Данные представления имеют смысл, если считать, что значение бесконечной суммы 1»' = 9+ 90+ 900+ 9000+ равно -1, поскольку ВА — 10Л' = 9. См. также упр. 31, в котором рассматриваются системы р-адических чисел. Дхя чисел, представление которых по основанию р конечно, р-едическое представление совпадает с рассмотренным здесь представлением в дополнительном коде, но между полем р-адлческих чисел н полем вещественных чисел не существует никакой прямой связи. 6.
2 аЬ'иу,(ащ,ь '+ .+ал)ьлг. 9. А ВАО АООВЕ ГАСАОЕ рАОЕО, (Вркиечаннс. Вот другие "числовые фразы": 00 А ВЕЕР А ОЕСАОЕ; А САО РЕО А ВАВЕ ВЕЕР, СОСОА„ СОРГЕЕ; ВОВ ГАСЕО А РЕАО 0000.) 10. ~ = ' ' ' ' ' если , Ьг, Ьг, Ьм Ье; Ь-и Ь-и (..., Вг, Вг, Вм Ва; В и В г,... "~зз л' лги г''''' лг1 В, =Ьл„,,,Ь,, где (Ьв) — произвольная бесконечная последовательность целых чисел, удовлетворяющих неравенствам й, +г > Й . 11.
(Описываемый ниже алгоритм выполняет как сложение, так и вычитание в зависимости от выбора знака "плюс" или "минус".) Сначала устанавливается А +- а4.м +- а;+г +- Ь ег з — Ь +г е- О; затеи для гл = О, 1,... ...,и+2 выполняется следующее: устанавливается с, +- а А. Ь + А; далее. если с > 2, устанавливается А +- — 1 н с з- г — 2; если с < О, устанавливается Ь +- 1 и ств +- с + 2; а если 0 < с, < 1, то устанавливается А +- О.
12. (а) Вычесть к( а»олго)-г нз х(... азоагоае) г в негадвончной системе. (В упр. 7.1-18 приводитсн оригинальное рещение задачи, полученное с использованием битовых операций над полным еловом,) (Ь) Вычесть (... Ь»ОЬго)г из (... ЬлобгОЬа)г в двоичной систелле. (0.090909 ° .. )- о == П. [Ь вЂ” 4(! [5 — 41[ 13, (1.909О90...) 14. 11321 11321 11З21 11202 1212З 11321 11З21 О!О З 112 О! [9-40!) ун = 2 ьйтань16 -э где каждое ань принадлежит ло. Построим дерево, вершинами которого будут наборы (а„т,...,а„„) для 1 ( г- < н, причем одна вершина является родителем, если она является по отношению к этой вершине начальным поднабором. Согласно теорема о бесконечных деревьях (теорема 2.3.4.ЗК) зго дерева имеет бесконечный путь (ам ат, аз,...
); соответственно 2 вы аь16 ь есть предельная точка множества [рт,уэ,...), приналлежатцая 5. В соответствии с ответом к упр. 16 все числа вида (а+ 6!)/16' представимы, если а н Ь целыс. Поэтому прн действительных х и р и Ь > 1 число зь — — ([16ьх) + [1649)1)/16 для некоторых целых ш и н принадлежит Я+ та+ н(. Можно показать, что всякая представимая точка вне Я должна принадлежать множеству о'+ та+ и! при (т, и);е (О, О). Соответственно, если [х[ и [у[ фиксированы и й достаточно велико, получаем, что ль Е 5 и !пль-,~ хэ = х+ у! принадлежит множеству 5. [В. Мандельброт (В, Маада!Ьгог) назвал множество Я двуглавмм драконом, подметив, что оно, по существу, формируется путем объединения двух "кривых дракона" (см, книгу Рис. А-6.
Фундаментальная область 15. [-П .. — „[ и прямоугольник справа (рис А-6), для миимочетверичных чисел. то т 16. Соблазнительно попробовать сделать это самым простым способом, предписав реализацию переносов по правилу 2 = (1100), т, но это приведет к непрекращающейся процедуре (зацикливанию) при попытке добавления единицы к числу (11101), т = -1. В приведенном ниже решении предлагаются четыре алгоритма (для сложения и вычитания 1 и 1). Если а — строка нэ нулей и единиц, то цгьтагается, что а — такая строка из нулей и единиц, что (а' ), т = (а), т + 1. Аналогичным образом определяются а, аа, а а путем замещения +1 соответственно на -1, +4 и -Ь Тогда (ао)" = а1; (ах1) ж аахо. (ао)а = а 1! (а1) =а ~О.
(ахо) = а Ох1; (а1) = ао. (аО) ~ = а~1; (а1) ~ = а" ~О. Здесь х означает 0 или 1 и цепочки при необходимости дополняются слева нулями. Все эти процедуры очевидным образом заканчиваются. Таким образом, любое число вида а + Ы с целыми а и Ь представимо в системе по основанию ( — 1.
12. Нет (вопреки упр. 28); число — 1 не представимо в этой системе. Это можно доказать, построив соответствующее множество Ят как на рис. 1. Имеем представления -1 (0.1111... )тсь 1 = (100.Ш1...)1+.. 16. Пусть 5е — множество точек (атаеаэатазаэтмао) -м в котором каждое аь есть 0 или 1. (Поэтому множество Яо состоит из 256 внутренних точек, отмеченнмх на рнс. 1, после 16-кратного увеличения.) Покажем сначала, что множество Я замкнутое.
Пусть Рц рм .., -- пРоизвольная последовательность точек множества 5. Имеется ргасса)з! Еогт, СЬалсе, алд Рлтепзлол (Яап Егапшзсо! Егееплап, 1977). 313-314, в которой Мандельброт установил, что разлсерность границы равна 2 18х 1,523627, где х т 1 + 2х ! 1.69562. Другие саойстаа кривой дракона описаны а статье С. Раз!а апд Р.
Е. Кпп«Ь Х Нвсг. Ма«Ь. 3 (1970), 66-81, 133-149. Мпожества Я систем счисления по осноааниям (О, 1) и другим комплексным основаниям построены и проанализированы Д. Гаффином (Р. Со%пес) в АЗЫ 98 (1991), 249-255.] В статье 1, Кйса! апд 3. ЯзаЬо, Асса Я«сел!. Ма«Ь. 37 (1975), 255-260, показано, что основание -д+! приводит к системам счисления с цифрами (О, 1,..., д ). Другие свойства ! таких систем исследовались У, Дж. Гнльбертом (%. 3. СОЬегС) в Сапасйал Х Май. 34 (1982), 1335-1348; Май, ЛХлбахше 57 (1984), 77-81.
В, Нортов (Ъ!. Хогеоп) предложил еще одну интересную систему счисления по основанию 2 + ! с цифрами (0,1,л, — 1,-!) [МасЬ. Ыайавпе 57 (1984), 250-25Ц. С снстемал«и счисления, осноаанньгми на более общих целых числах, можно ознакомиться в работах 1. Кйа! алд В. Кохйсв, Асса Май. Асад. Ясл Нплй. 37 (1981), 159 — 164, 405-407; Асса ай. Нипя. 58 (1991), 113 — 120; А. Ре«65, Я«ад!а Ешепс. МатИ. Нплб.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
