AOP_Tom2 (1021737), страница 28
Текст из файла (страница 28)
В качестве примера рассмотрим компьютер й11. Можно вычислить у пюб т, помещая у в регистры А и Х и выполняя деление на т. Если у и т положительны, то у шог( т появится в регистре Х. Но деление — сравнительно медленно протекающая операция, и этот недостаток можно компенсировать, если выбрать значение пт таким, что особенно удобно, как длина слова нашего компьютера. Пусть ю будет длиной компьютерного слова, а именно — 2' на е-разрядном двоичном компьютере или 10' на е-цифровой десятичной вычислительной машине. (В настоящей книге мы часто будем употреблять букву е для обозначения проиэвОЛьпой цЕЛОй ствпвии.
Несмотря на то что эта буква часто используется для обозначенин основания натурального логарифма, мы надеемся, что читателю из контекста будет понятно, что она обозначает. Физики сталкиваются с подобными проблемами, когда используют е для обозначения заряда электрона.) Результат операции суммирования обычно дается по модулю ю (но не на машинах, использующих процедуру единичного дополнения); умножение по модулю и> также очень простое, поскольку затрагиваются только младшие разряды произведения.
Таким образом, следуюгдая программа эффективно вычисляет величину (аХ + с) шоб ю. ЫА а гА+ а. И0 ~ Х гАХ<-(гА) Х. 01,АХ Б гА ~- гАХюодю. 100 С гА <-(гА+с) шодм. ° Результат появляется в регистре А. В конце программы возможно переполнение; если это нежелательно, то следует, допустим, команда '30Ч ь+1" — "выключить". "Умная" техника, обычно менее известная, может использовать представление вычисления по модулю ю + 1.
По причинам, поясняемым ниже, как правило, требуется, чтобы с = О, когда т = ю + 1; тогда мы просто должны вычислить (аХ) шой (ю + 1). Делает это следующая программа. гА «- — Х. тАХ «- (гА) а. 01 ЮАИ Х 00 МО1. А 00 БТХ ТЕИР 04 ЯОВ ТЕИР 00 ЗАИИ ««3 00 1ИСА 2 07 АОО =ю — 1= (2) гА «- гА — гХ Выход, если гА > О. гА з — гА+ 2. гА «- гАч-ю — 1. 1 аЛ' = д(ю+1) + (т — 0) и мы имеем — ю < т — о < ю, так как д < ю; следовательно, (аЛ ) тпой (ю + 1) равно одному из двух значений (т — д или т — д+ (ю+ 1)) в зависимости от того, т — д > 0 илит †0.
Подобная тсхника может быть использована для получения произведения двух чисел по модулю (ю — 1); см. упр. 6. Для освоения следующих разделов требуется знать простые множители т, чтобы правильно выбрать а. В табл. 1 впервые дается полный список разложений на простые множители ю х1 почти для каждой известной длины компьютерного слова; при желании методы из раздела 4.5.4 можно использовать для расширения таблицы. Читатель может поинтересоваться, почему здесь обсуждается использование тп = ю х 1, когда выбор тп = ю так явно удобен. Причина в том, что, когда т = ю, ипфры правой часто Х„гораздо менее глучайны, чем цифры левой части. Если й является делителем т и если У„= Х„шопа, можно легко показать, что (4) У„«~ — — (а1'„+ с) шог( Н.
(Пусть Хью = аХ«+ с — от, где д — некоторое целое число. Если обе части равенства взять по модулю 0, можно потерять дт, когда а' — множитель т.) Для иллюстрации важности выражения (4) предположим, например. что имеется двоичный компьютер.
Если тп = ю = 2", младшие четыре разряда Х„являются В регистре А сейчас содержится значение (аХ) шой (ю + 1). Конечно, оно может лежать где-нибудь между О и ю включительно, так что читатель может законно удивиться, как можно представить так много значений в регистре А! (Обычно регистр не может хранить число, большее, чем ю — 1.) Ответом является то, что переполнение в программе (2) происходит тогда и только тогда, когда результат равен ю (если предположить, что переполнение убрано в исходном положении). Можно отобразить ю в виде нуля, так как программу (2) обычно нельзя использовать, когда Х = 0; но более удобно просто отбросить значение ю, егли оно появляется в коигруэнтной последовательности по модулю и~ + 1. Затем также можно избежать переполнения, просто заменив строки 05 и 06 в (2) строками "ЛАЛИ «+4; 1ИСА 2; 3АР ° -6".
Для доказательства того, что программа (2) действительно вычиглиет (аЛ') шой (ю + 1), заметим, что в строке 04 младшие разряды произведения вычитаются из старших разрядов. Переполнение не может произойти на этом шаге, и, если аЛ = дю + т при 0 < т < ю, получим значение т — д в регистре А после строки 04. Сейчас Таблица 1 РАЗЛОЖЕНИЕ НА ПРОСТЫЕ МНОЖИТЕЛИ и ~ 1 10' —, 1 10' — 1 б 7 8 9 10 11 12 16 7 31 151 3 5 17 257 131071 Зз, 7 19 73 524287 3 5з . 11 ° 31 ° 41 7з 127 337 3.23 89 683 47 178481 Зз 5 7 13 17 241 31 601 . 1801 3 2731 8191 7.73 262657 3.5 29.43 1)3 127 233 1103 . 2089 ЗЗ . 7 11 31 15! 33) 2147483647 3 5 17 257 65537 7 23 89 599479 3 43691 131071 31 7! 127 122921 ЗЗ 5 7 13 19 37 73 .109 223 616318177 3 174763 524287 7 .
79 8191 . 12)369 3 5) )1 17 31 .41 61681 13367 164511353 Зз 7з 43 127 337 5419 431 9719 2099863 3 5 23 -89 397 583 2!!3 7 31 73 151 631 2331! 3 47 178481 2796203 2351 4513 13264529 Зз 5 7 13 17 97 241 257 673 179951 3203431780337 5) 7 11 13 3! 41 61 151 33! 1321 7з, 73 )27 337, 92737, 649657 3 5 17 257 641 65537 . 6700417 . Зз 7 11 13 37 Зз 239.
4649 Зз 11 73 101 137 Зз . 37 333667 Зз 11 41 .271 9091 Зз 21649,513239 Зз 7 11 13, 37 )01, 9901 Зз 11 17 73 101 137 5882353 15 16 !7 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 ЗЗ 34 35 Зб 37 38 39 40 41 42 43 44 45 46 47 48 59 60 63 64 Зз . 11, 331 65537 3 43691 5 !3 37.109 3 174763 17 61681 Зз 43 5419 5 397 2113 3 2796203 97 257 673 3 11 251 4051 5 53 157 1613 34 19 87211 17 15790321 3 59 . 3033169 5) 13, 41 61, 1321 3 . 715827883 641 6700417 Зз 67 683 20857 5 137 953 26317 3 11 43 281 86171 17 241 433 38737 3 1777 25781083 5 229.457 525313 Зз .
2731 . 22366891 257 4278255361 3 83 8831418697 5 13 29 113 1429 14449 3 2932031007403 17 353 29ЗР342417 Зз,11 19 331 16637001 5 277 1013 1657 . 30269 3 283 165768537521 193 65537 22253377 3 2833 . 37171 1824726041 17 241 61681 45622845б1 Зз !9, 43 5419, 77Р38673929 274177 67280421310721 101.9901 11 909091 17 5882353 7 11-13 19 52579 101 3541 27961 11! . 23 4093 8779 73 137 99990001 353 449 . 641 1409 . 69857 числами У„= Х„шоб 24. Суть выражения (4) состоит в том, что младшие четыРе Разряда (Хэ) формируют конгруэнтную последовательность с периодом 16 или меньше. Аналогично пять младших разрядов являются периодичными с периодом не более 32 и наименьший значащий разряд Л„является либо постоянным, либо строго периодичным.
Подобная ситуация не возникает, когда т = ш ш 1; в таком случае младшие разряды Х„ведут себя так же случайно, как и старшие. Например, при ш = 2зь и пэ = 2зэ — 1 числа последовательности будут не очень случайны, если рассмотреть только их остатки по модулю 31, 71, 127 или 122921 (см. табл.
1); но младшие разряды, которые представляют числа последовательности, взятые по шоб 2, будут достаточно случайны. Альтернатива состоит в том, чтобы в качестве т взять наибольшее простое число, меньше, чем ш. Это простое число можно найти, используя методы из раздела 4.5.4 и таблицы иэ того же раздела, в которых содержатся подходящие большие простые числа. В большинстве случаев применения младшие разряды несущественны и выбор пз = ш является совершенно удовлетворительным при условии, что програлэмист, работающий со случайными числами, делает это сознательно, Обсуждение до сих пор базировалось на использующих "величины со знаками" компьютерах типа И11. Подобные идеи применяются в вычислительных машинах с дополнительной системой обозначений, хотя есть несколько полезных разновидностей.
Например, компьютер ВЕСзуэСеш 20 имеет 36 бит с двоичным арифметическим дополнением; когда он вычисляет произведение двух неотрицательных чисел, младшие разряды содержат 35 бит со знаком "плюс". На этой вычислительной машине следовало бы полагать, что ш = 2зэ, но не 2зе.
32-битовое двоичное арифметическое дополнение на компьютерах 1ВМ Буэсеш/370 другое: младшие разряды операции умножения содержат 32 полных бита. Некоторые программисты считают, что это недостаток, так квк младшие разряды могут быть отрицательными, когда исходное число положительно, и досадно корректировать это. На самом деле есть определенные преимущеспэва с точки зрения генерирования случайных чисел, так как можно брать т = 2зз вместо 2зз (см. упр. 4). УПРАЖНЕНИЯ 1. (М12) В упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
