AOP_Tom2 (1021737), страница 164
Текст из файла (страница 164)
д. кругкююм [сл7. магг!77 э Кгпв)7а), АММ 61 (1954), 392 — 397). Исполгыуя интегральное представление Е, =/ ((1+ — ) — 1)е он доказал асимптотическое соотношение 1пп (Š— —.„' !и пз) = — 7'(7 +!и 2) Другие результаты, а также ссылки на литературу, можно найти в работе 177Ьп В!ог7!а77, АплМз Маей. Ясаг. 33 (1962), 178 — 185.
15. Вероят77ость того, что 7"(к) ф т для всех х, равна (ш — 1) /7п", а это приблизительно равно 1/е. Существование самоповторяющегося значения в алгоритме, подобном алгоритму К, не является поэтому "колоссальным"; его вероятность равна 1 — 17'7 — .63212. "Колоссальным" было только то, что автору удалось получить такое значение Хе при случайном выборе (см упр. 11). 16. Последовательность повторится, когда пара следующих один за другим элементов встретится второй раз. Максимальный период равен т .
(См. следующее упражнение.) г 17. После произвольного выбора Хо,..., Хь 7 пусть Л„,7 = 7(Х„,..., Х„ьэ7), где 0 < х7,...,хь < т влечет то, что 0 < )(х7,...,хь) < 7п. Максимальный период равен нгь. Это очевидная верхняя граница, однако не очевидно, что она достижима, для конструктивного доказательства того, что она достижима для подходящей функции 1 (обратитесь к упр. 3.2.2 — 17 и 3.2.2 — 21; численный метод приводится в упр.
2 3.4 2-23). 18. Метод такой же, как в упр. 7, во используйте цепочку из !с элементов (Х„,..., Х„7г7) вместо элемента Хю 20. Достаточна рассмотреть простое отображение д(Х), определяемое на шагах К2-К13. Следуя в обратном порядке от числа 6065038420, получим в общей сложности 597 решений; наименыпнм числом является 0009612809, а наиб<шьшим -- 9995371004 21.
Можно работать с д(Л ), как и в предыдущем упражнении, но сейчас необходимо запустить функцию в прямом порядке. Существует иптереснаи взаимосвязь между временем и пространством. Используя несколько мегабайтов памяти, автор в 1994 году проверил зто предположение для всех начальных значений, л7еиьших. чем 0000165181, по решил подождать несказько лет, прежде чем продолжить исследования, так как компьютеры становились все больше и мощнее, Заметим, что механизм шага К1 спос77бствует уменьшению периода. Существуют Х с бочьшим числом значений, переходящих в ннх, например 512 значений Х = *6*»****** на шаге К2 приведут к шагу К10 со значением Х +- 0500000000.
С. Флюхер (Б. Е1ойгег) обнаружил другие фиксированные точки алгоритма К, а именно — значение 5008502835(!). Ои также нашел третий цикл 0225923640 -+ 2811514413 -+ 0590051662 — г 0225923640, объединяющий семь циклов, Только 128 начальных чисел ведут к повторению значении 5008502835. Алгоритм К вЂ” это ужасный генератор случайных чисел! 22. Если 7" -- действительно случайная функция, то это было бы идеально; но как построить такую 7"о Функция, определенная алгоритмом К, работала бы намного лучше по этой схеме, хотя она действительно имеет неслучайные свойства (см.
предыдущий ответ). 23. Фуякцня 7 переставляет свои циклические элементы; пусть (хо; .,хс ~) является 'необычным» представлением, обратным к этой перестановке. Затем продолжим определять хь,...,х о, как в упр 2.3.4.4 — 18 (См. д. Сошйшагог!а1 ТЬеогу 8 (1970), 361-375.) Так, если гп = 1О и (ДО),, 7(9)) = (3, 1,4, 1,5,9, 2,6, 5,4), получим (хо,,хо) = (4 9 5, 1, 1, 3 4 2 6 5)- если (то,, хо) = (3, 1, 4, 1, 5, 9 2 6 5, 4), пачучнм (7(0), 7(9)) = (6,4,9,3, 1, 1,2,5,4,5).
РАЗДЕЛ 3.2.1 1. Выберите числа Хо и а четными, а с — нечетным. Тогда Х будет нечетным при и > О. 2. Пусть Л„является первым повторившимся значением последовательности. Если Л, равно Хь для некоторого А, где 0 < А < г, можно доказать, что Х, г = Хь н так как Л» единственным образом определяет Х„ц где а взаимно просто с т.. Отсюда А = О.
3. Если д — нанболыиий общий делитель а н т, величина аХ может принимать не боаее т/д значений. Возможна даже худшая ситуация; например, если т = 2' и а— четное число, формула (6)показывает,что последовательность в конечном счете является константой. 4. Индукция по )г. 5. Если числа а и т взаимно простые, то существует число а', для которого аа' св 1 (по модулю т).
Тогда Л„о = (а'Х вЂ” а'с) шос1 т и в общем случае Л» ь = ((а )~Մ— с(а + + (а ) )) гпод т = ((а ) Х„+ ((а ) — 1) с/Ь) шод т, где )г > О, и — А > О. Если а и т не являются взаимно простыми числамн, то определить Х о, когда задано Х», невозможно; числа, кратные т/бед(а,гп), могут быть добавлены к Х»-~ без изменения величины Х . (См. также упр. 3.2.1.3-7.) РАЗДЕЛ 3.2.1.1 1. Пусть с' — решение уравнения ас' кв с по модулю т.
(Так, с' = а'с шод т, если а'— число в ответе к упр. 3.2.1-5.) Тогда ЬОА Х; АОО СР81МЕ; 81П. А. Переполнение возможно на операции суммирования. (Из результатов, полученных ниже в этой главе, следует, что, возможно, лучше сберечь единицу времени, положив с = а н заменив операцию АОО операцией»1МСА 1". Затем, если Ло = О, переполнение не произойдет до конца периода, так что практически его не будет.) 2. МАМРМ ЯТЛ ЬВА МОЬ 51АХ АОВ ЯТА 1Н 1МОУ Л1Р ХМИ!В СОМ 2Н СОМ зо СОМ 1Р ХХАМР 2Р 5 ЗР (Или 1МСА с, если с «гало) ХНАМВ «-1 Хо а с 3 3.
Пусть а' = ашшойт и пусть т' таково, что тгл' = ! (по модулю ш). Положим у «- !огиз«!с(а',х), г е- Ьпопй(а,х), ! +- !ошо!з(т',у), и +- Ь!гоо!1(т,!). Тогда получилг тс щ а'х (по модулю ш). Значит, а'х — т! = (х — и)ш и а:г .= з — а (по модулю т); отсюда следует, что ах той«в = х — о+ [х < и[т.
4. Определим операцию х гной 2" = у тогда и только огда, когда х— : у (по модулю 2') и -2' ' < у ( 2' '. Конгруэнтная последовательность (1'„), определенная следующим образом Уо = Хо. шой 2, Уты = (аУ„л с) глод 2 зг зг легко вычисляется на машинах серии Зуэзеш/37О, так как младшие разряды произведе- ния у и г равны (уг) пюй 2 для всех двоичных дополнений чисел у и х; и поскольку зг при суммировании не принимается во внимание переполнение, она также представляет результат сравнимым по злой 2 . Эта последовательность обладает всеми свойствазг ми случайности стандартной линейной конгруэнтной последовательности (Х„), так как У„ = Х„ по модулю 2 .
В саном деле, представление в виде двоичного дополнения У„ зг ойентично двоичному представлению Х«для всех и. [Дж. Марсалья (С. Ышэаб!!а) и Т. А. Брей (Т. А. Вгау) впервые подчеркнули это в САСМ 11 (1968), 757-759.) 5. (а) Вычитание ЬВА Х; 5ОВ Т; 1АММ «+2; АВВ М. (Ь) Суммирование: ЬВА Х; 5ОВ М; АВО Т; ЯАМИ «+2; АРО М. (Заметим, что если гл больше половины длины слова, то операция "5ОО М" должна предшествовать операции "АРО Т".) 6. Эти последовательности мало различаются, так как добавление константы (гл — с) дает тот же эффект, что и вычитание константы с. Данная операция должна сочетаться с операцией умножения, так что процесс вычитания имеет небольшие преимущества перед процессом сложения (по крайней мере, для машины М1Х). Исключение составляет случай, когда необходимо избежать переполнения. 7.
Простые делители х — 1 появляются в факторизации г — 1. Если т нечетное, то з ы простые делители г +1 появляются в факторизации х '+1 и х — 1 равно (г — 1)(х +1). з ь гз з з 8„1ОЧ «+1 (Убедитесь, что переполнение выключено.) ьВА Л М~Л. А 5ТХ ТЕМР АВВ ТЕМР Добавить млалзпие разряды к старшим. 1уот «+2 Если > гс, вычесть ш — 1, 1МСА 1 (Переполнение невозможно на этом шаге.) 1 Замечание. Так как сумиирование на е-разрядном компьютере с единичным дополнениеи производится по шой (2' — 1), то можно комбинировать технику из упр. 4 и 8, выполняя операцию (уг) шой (2' — 1) путем суммирования двух е-разрядных половин произведения уг для всех единично дополненных чисел у и г, не обращая внимания на знак.
9. (а) Обе части равенства совпадают с выражением ад[х/д]. (Ьг Положим 1 +- а(х той д) — г[х/д], где г ж т той а; константы д и г могут быть вычислены заранее. Тогда ах шой гл = Г + [1 < 0]т, так как можно доказать, что Ф > -т. Ясно, что а(х шейд) < а(д — 1) < т. Также г[х/д] < г[(т — 1)/д] = в[а + (г — 1)/д] = га < да < гп, если О < г < д; и а < т влечет г < а < д. [Эта методика в неявном виде использована в программе, опубликованной Б, А. Нихманом (Н.
А, Ъв'1сЬшапп) и Я. Д. Хиллом (1, Р. Нв!1): Лррбей Бваь 31 (1982), 190.] 10. Если г > д и х = т — 1, то г[х/д] > (д+ 1)(а ч-1) > т. Итак, условие г < д необходима и достаточно для применения метода из упр. 9, (Ь). Подразумевается, что — — 1 < а < —. ч — — в' Пусть Г = [э/т]. Интервалы [ — — 1 .. — ] не пересекаются при 1 < д < 1 и обязательно включают 1 или 2 целых чисча в зависимости от того, будет ли д делителем т.. Эти интервалы дают все решения с а > э/т; они также включают случаи для а = 1, если (э/тшой1) < —,', и а = à — 1, если т = 1~. Таким образом, общее число "удачных" множителей точно равно 2[э/т] + [й(т)/2] — [(т/т шой 1) < -'] — 1, где й(т) — число делителей т.
11. Можно предположить. что а < -'т; иначе можно получить ах той т. из (т — а)х той т. Тогда можно представить а = а'ав — ав', где асе числа а', ав и ав' меньше э/т; ншвример, можно взять а' ш;/т — 1 и ав = [а/а']. Следовательно, ахгаойт равно (а'(а"х шой т) пюй т — (а'вх гной т)) шой га и все три внутренние операции вюгут быть заимствованы из упр. 9. Когда т = 2 ' — 1, можно воспользоваться тем, что т — 1 имеет 192 делителя, для зв определения случаев, в которых т = д'а' + 1. При этом упрощается общий метод, так как г' = 1. Кроме того, 86 из этих делителей ведут к удачным ав и ав', когда а = 62089911.
Наилучшим из этих случаев будет, вероятна, случай, когда а' = 3641, а" = 17053, ав' = 62, потому что т — 1 делится как на 3641, так и на 62. Это разложение осуществляется по схеме 1 +- 170оЗ(х шой 125929) — 16410 [х/125929], 1 +- 3641(1 шой 589806) — [1/589806], 1 + — д — (62(х впой 34636833) — [х/34636833]), где "-" обозначает вычитание по модулю вь Операция сравнения по модулю рассматри- вается как две операции — - умножения н вычитания. Поскольку х шейд = х — д[х/д] и операция [х/д] уже выполнена, то совершено семь умножений, три деления и семь вычитаний. Заметим, что число 62089911 имеет 24 делителя; они поэволявэт получить пять подходящих факторизаций с а"' = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
