Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 7
Текст из файла (страница 7)
В качестве примера рассмотрим компьютер 31Х. Можно вычислить у той т, помещая у в регистры А и Х и выполняя деление на т. Если у и т положительны, то у шоб гп появится в регистре Х. Но деление — сравнительно медленно протекающая операция, и этот недостаток можно компенсировать, если выбрать значение т таким, что особенно удобно. как длина с юеа нашего компьютера. Пусть ю будет длиной компьютерного слова, а именно — 2» на е-разрядном двоичном компьютере или 10' на е-цифровой десятичной еычнсрительной машине. (В настоящей книге мы часто будем употреблять букву е длк обозначения произвольной целой степени.
Несмотря на то что эта буква часто используется для обозначения основания натурального логарифма, мы надеемся„что читателю из контекста будет понятно, что она обозначает. Физики сталкиваются с подобными проблемамн, когда используют е для обозначения заряда электрона.) Результат операции суммирования обычна дается по модулю ю (но не на машинах, использующих процедуру единичного дополнения): умножение по модулю ю также очень простое, поскольку затрагиваются только младшие разряды произведения. Таким образом, следующая программа эффективно вычисляет величину (аХ + с) пюд ш. ЬОА А гА <- а.
И01 Х Ах -(гА) Х, И.АХ Б гА+-гАХшодм. А00 С гА ь-(гА+с)пюдм. А Результат появляется в регистре А. В конце программы возможно переполнение; если это нежелательно, то следует, допустим, команда»307»+1» — "выключить . »Умная" техника, обычно менее известная, может использовать представление вычисления по модулю ю+ 1. По причинам, поясняемым ниже, как правило, требуется, чтобы с = О, когда т = ю + 1; тогда мы просто должны вычислить (аХ) шой (в + 1). Делает зто следующая программа. 01 1.МАМ Х 00 ИШ.
А 00 бтХ тЕИР 04 МОВ тВИР 05 ЛАМИ в+3 06 1МСА 2 07 АОО в — 1 гА <- -Х. гАХ +- (гА) а. гА +- гА — гХ. Выход, если гА > О. .А <- гА+ г. гА+- гА+ в — 1 $ аХ = а(в + 1) + (г — у) и мы имеем -в < г — д < в, так квк а < в; следовательно, (аХ) пюд (в + 1) равно одному из двух значений (г — д или т — а+ (в + 1)) в зависимости от того, г — д > 0 илиг †а. Подобная техника может быть использована для получения произведения двух чисел по модулю (в — 1); см. упр, 8. Для освоения следующих разделов требуется знать простые множители т, чтобы правильно выбрать а. В табл.
1 впервые дается полный список разложений на простые множители в в 1 почти для каждой известной длины компьютерного слова; при желании методы из раздела 4,5.4 можно использовать для расширения таблицы. Читатель может поинтересоваться, почему здесь обсуждается использование т = в х 1, когда выбор т = в так явно удобен. Причина в том, что, когда т = в, цифры правой частя Х„гораздо менее случайны, чем цифры левой части. Если 0 является делителем т и если 1'„= Х„шод М, можно легко показать, что 1'„+~ —— (а1'„+ с) шос( М.
(Пусть Х„.~~ — — аХ„+ с — ага, где а — некоторое целое число, Если обе части равенства взять по модулю а', можно потерять уа, когда М вЂ” множитель т.) Для иллюстрации важности выражения (4) предположим. например, что имеется двоичный компьютер. Если т = в = 2", младшие четыре разряда Х„являются В регистре А сейчас содержится значение (аХ) шод (в + 1), Конечно, оно может лежать где-нибудь между 0 н в включительно, так что читатель может законно удивиться, как можно представить так много значений в регистре А! (Обычно регистр не может хранить число, болыпее, чем в — 1.) Ответом является то, что переполнение в программе (2) происходит тогда и только тогда, когда результат равен в (если предположить, что переполнение убрано в исходном положении) .
Можно отобразить в в виде нуля, так как программу (2) обычно нельзя использовать, когда Х = О; но более удобно просто отбросить значение в, если оно появляется в конгрузнтной последовательности по модулю в+ 1. Затем также можно избежать переполнения, просто заменив строки 05 и Об в (2) строками "ЛАИМ ь+4; 1МСА 2; ЛАР ь-б". Для доказательства того, что программа (2) действительно вычисляет (аЛ') шод (в+ 1), заметим, что в строке 04 младшие разряды произведения вычитаются из старших разрядов. Переполнение не может произойти на атом шаге, и, если аХ = йв + г при 0 < г < в, получим значение г — а в регистре А после строки 04.
Сейчас чнсламн 1'„= Х„щи 2э. Суть выражения (4) состоит в том, что младшие четыре разряда (Х„) формируют конгрузнтную последовательность с периодом 16 или меньше. Аналогично пять младших разрядов являются перноднчными с периодом не более 32 и наименьший значащий разряд Х„является либо постоянным, либо строго периодичным. Подобная ситуация не возникает, когда гп = ш ш 1; в таком случае младшие РазРЯды Хэ ведУт себЯ так же слУчайно. как и стаРшие. НапРимеР, пРи ш = 2ээ и гл = 2ээ — 1 числа последовательности будут не очень случайны, если рассмотреть только их остатки по модулю 31, 71, 127 или 122921 (см.
табл. 1); но младшие разряды, которые представляют числа последовательности, взятые по шод 2, будут достаточно случайны. Альтернатива состоит в том, чтобы в качестве т взять наибольшее простое число, меньше, чем ш. Это простое число можно найти, используя методы из раздела 4.3,4 и таблицы из того же раздела, в которых содержатся подходящие большие простые числа.
В большинстве случаев применения младшие разряды несущественны и выбор гл = ш является совершенно удовлетворительным при условии, что программист, работающкй со случайными числами, делает зто сознательно. Обсуждение до сих пор базировалось на использующих "величины со знаками" компъютерах типа И12. Подобные идеи применяются в вычислительных машинах с дополнительной системой обозначений, хотя есть несколько полезных разновидностей. Например, компьютер ПЕСэуэгегп 20 имеет Зб бит с двоичным арифметическим дополнением; когда он вычисляет произведение двух неотрицательных чисел, младшие разряды содержат 33 бит со знаком "плюс". На этой вычислительной машине следовало бы полагать, что ш = 2ээ, но не 2ээ.
32-битовое двоичное арифметическое дополнение на компьютерах?ВЫ Буэ?еш~370 другое: младшие разряды операции умножения содержат 32 полных бита. Некгэгорые программисты считают, что это недостаток, так кэк младшие разряды могут быть отрицательными, когда исходное число положительно, и досадно корректировать это. На самом деле есть определенные преимущества с точки зрения генерирования случайных чисел, так как можно брать т ш 2ээ вместо 2э1 (см.
упр. 4). УПРАЖНЕНИЯ 1. [М?э) В упр. 3.2.1-3 сделан вывод о том, что наилучший коигруэнтный генератор будет иметь множитель о, взаимно простой с т. Покажите, что, когда гп = ш, возможно лучшее вычисление (аХ + с) шоб м точно в шрэя операциях И11, чем в четырем операциях (1), с результатом, появляющимся в регистре Х. 2.
(16) напишите подпрограмму на и11, имеющую следующие характеристики. Вызывшощая последовательность: зПР каКПН Условия па входе: Адрес ячейки Хвапв содержит полое Х Условия нэ выходе: Х э- гА <- (оХ + с) щи ш, гХ <- О, переполнение выключено (В результате обращения к этой подпрограмме можно получить следующее случайное число линейной конгруэнтной последовательности.) 3. [Мйб) Многие компьютеры нс имеют возможности делить числа из двух слов на числа из одного слова:, они позволяют выполнять только операции над числами, из отдельных слов, такие как операция Ьлпшй — Ыпш11 (х,у) = [ху/ю) и операция 1ошэ11 — 1ошэ11 (х, у) = ху шой ш, когда э и у — неотрицательные целые числа, меньшие, чем компьютерное слово ш. Объясните, как вычислить ах шол( т в терминах Ьшш11 н 1опш!ц предполагая, что 0 < а, х с т < ю и гл.1 ю.
Вы можете использовать заранее вычисленные константы, которые зависят от а, гл и ил ° 4. [31) Исследуйте вычисление.шнейной конгруэнтной последовательности с т = 2з' на машинах с двоичным дополнением, таких, как компьютеры серии Яуэсеш/370. б. [00) Дано, что гп меньше, чем ллииа слова, и что х и у — неотрицательные целые числа, меньшке, чем т. Покажите, что разность (я — у) шол) пл может быть вычислена точно четырьмя операциями без операции деления на машине НП. Какая программа будет наилучшей для вычисления суммы (х + у) шо4 т? В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
