AOP_Tom2 (1021737), страница 29
Текст из файла (страница 29)
3.2.1-3 сделан вывод о том, что наилучший конгруэнтный генератор будет иметь множитель о, взаимно простой с пэ. Покажите, что, когда пэ = ш, возможно лучшее вычисление (аХ + с) шоо ш точно в трех операциях И11> чем в четырех операциях (1), с результатом, появляющимся в регистре Х. 2. (1б) Напишите подпрограмму на И11, имеющую следующие характеристики. ВЫЗЫваЮщая ПОСЛЕдОВатЕЛЬНОСтЬ: Л1р ВАИВИ Условия на входе: Адрес ячейки Хйайэ содержит целое Х Условия на выходе: Х ь- гА э- (аХ+ с) шой ш, гХ < — О, переполнение выключено (В результате обращения к этой подпрограмме можно получить следующее случайное число линейной ковгруэнтной последовательности.) 3.
[М80] Многие компьютеры не имеют возможности делить числа из двух глав на числа нз одного слова; они позволяют выполнять только операции над числами, из отдельных слон, такие как операция Ьнпн!с — Ыпш!с (х, у) = [ху/сл] и операция !опш!с — !опш!с (х, у) = ху шос! ю, когда х и у — неотрицательные целые числа, меньшие, чем компьютерное слово со. Объясните, как вычислить ах шос! гн в терминах Ьнпн1с и !опш!С, предполагая, что 0 < а, х < т < го и пс 1 ю.
Вы можете использовать заранее вычисленные константы, которые зависят от о, гп и со. 4. [И] Исследуйте вычисление линейной конгруэнтной последовательности с т = 2 на 32 машинах с двоичным дополнением, таких, как компьютеры серии Зуэсеш/370. б. [80] Дано, что т меньше, чем длина слова, н что х и у — неотрицательные целые числа, меньшие, чем т, Покажите, что разность (х — у) тасс гн может быть вычислена точно четырьмя операциями без операции деления на машине 811.
Какая программа будет наилучшей для вычисления суммы (х + у) шос! сп? 6. [80] Предыдущее упражнение наводит на мысль, что вычитание па модулю гав более простая операция, чем суммирование по модулю т. Обсудите последовательность, генерируемую по правилу Х ес = (аХ вЂ” с) шос! т.
Будет ли эта последовательность существенно отличаться от линейной конгруэнтной последовательности, определенной ранее? Будет ли ана более эффективной при вычислениях? 7. [М84] Какие особенности можно заметить в табл. 1? 8. [90) Напишите программу для вычисления (аХ) шаг! (и — 1) на компьютере 811, аналогичную программе (2). Значения 0 и си-1 на входе и выходе вашей программы считаются эквивалентными. 9. [М20] В большинстве языков программировании высокого уровня не предусмотрен хороший способ деления целого числа из двух слав на целое число из одного слова.
Не предусматривается это н операцией Ьшш!с из упр. 3. Пель данного упражнения — найти приемлемый способ преодоления таких ограничений, когда необходимо вычислить ох шас! т для переменной х и константы 0 < а < т, а) Докажите, что если д = [гп/и], то а(х — (х псас! 0)) = [х/Ч](т — (т гпос1 а)), Ь) С помощью равенства (а) вычислите ах шос) т, не оперируя числами, которые превосходят т по абсолютной величине, н предполагая, что а < гн. 2 10.
[МЯ0] Решение. упр, 9, (Ь) иногда применимо, когда а ) т. Определите точное число множителей а, для которых промежуточные результаты этого метода никогда не превосходят т для всех х между 0 и т. 11. [М00] Продолжая упр. 9, покажите, что можно оценить ох шад т, используя только следующие основные операции; !) ихо,гдеи>О,о)Оисго<т; и) [и/в],где0<а<и<т; !!!) (й — о) шод т, где 0 < и,ь < т.
Действительно, это всегда возможна, если использовать максимум 12 операций типа (!) и (й) и ограниченное число операций типа (ш), не считая предварительного вычисления констант, которые зависят от а и т. Например, объясните, как можно выполнить вычис- ления, когда о равно 62089911 и гн равно 2з' — 1 (Этн константы взяты из табл. 3.3.4 — 1.) ь 12. [Мйу] Рассмотрите вычисления карандашом на бумаге или на счетах. а) Найдите хороший метод умно;кения заданного десятнзвачного числа на 10 по модулю 9999998999.
Ь) Сделайте то же самое, но умножив непа 10, а на 999999900 (па модулю 9999998999). с) Объясните, как вычислить степень 999999900" шо4 9999998999 для и = 13Ь 3, .... 4) Выполните такие же вычисления с десятичным разложением числа 1/9999998999. е) Покажите, что эти идеи предоставляют воэможность реализовать определенные виды линейных хонгруэнтных генераторов, ил1еющнх очень большие модули, с помощью лишь нескольких операций с генерируемым числом. 13. [М84] Повторите предыдущее упражнение, но с модулем 9999999001 н множителями 10 и 8999999101.
14. [МЯ5) Обобщите идеи предыдущих двух упражнений для того, чтобы получить боль- шое семейство линейных конгруэнтных генераторов с особенно большими модулями, 3.2.1.2. Выбор множителя. В этом разделе будут рассмотрены методы выбора мнонЕнтеля а для создания периода максимальной длины. Длинный период необходим для любой последовательности, используемой в качестве источника случайных чисел. Безусловно, мы ожидаем, что в периоде содержится значительно болыпе чисел, чем требуется для одноразоного использования. Поэтому здесь внимание будет сосредоточено на длине периода. Читателю следовало бы помнить, однако, что длина периода — это только одно из требований к линейным конгруэнтным последовательностям, которые мы хотим использовать, как случайные последовательности.
Например, когда а = с = 1, последовательность примет простой вид: Хпы = (Х„+ 1) шобт. Она, очевидно, имеет период длиной т, но несмотря на это в ней нет ничего случайного. Другие соображения, влияющие на выбор множителя, будут приведены ниже в этой главе, Так как возможны только т различных значений, длина периода, несомненно, не может быть больше т. Можно ли достичь максимальной длины периода — гпу Пример, приведенный выше, показывает, что это всегда возможно, хотя выбор а = с = 1 не обеспечивает желаемые свойства последовательности. Исследуем есе возможные значения а, с и Хю которые дают период длиной пг.
Оказывается, что такие значения параметров могут быть охарактеризонаны очень просто; когда т является произведением различных простых чисел, только значение а = 1 обеспечивает полный период, но когда гп делится на простое число в большой степени, то существует значительная свобода в выборе а. Следующая теорема позволяет легко определить, возможно ли достижение периода максимальной длины. Теорема А.
Линейная конгруэнгная погледовательность, определенная числамп тьа, с п Хе, имеет период дллной гп то~да и только тогда, когда: !) числа с и т взаимно простые; й) Ь = а — 1 кратно р для каждого простого р, являющегося делителем т; !!!) Ь'кратно 4, если т кратно 4. Идеи, используемые при доказательстве этой теоремы, впервые возникли, по крайней мере, сто лет тому назад. Но первое ее доказательство в этой особой форме было предложено М. Гринбергером (М. ОгеепЬегкег) для частного случая при т = 2' [см,,7АСМ 8 (1961), 383-389).
Достаточность условий (!) — (!!!) в общем случае быда доказана Халлом (Нц1!) и Добеллом (ПоЬе)!) [см. 51АМ йе1пеж 4 (1962), 230-254). Чтобы доказать теорему, мы сначала рассмотрим некоторые вспомогательные теоретико-числовые результаты, представляющие и самостоятельный интерес. Лемма Р. Пусть Р— простое число, а е — положительное целое число, такое, что Р' > 2. Если х = 1 (по модулю Р'), х э( 1 (по модулю р'+'), (т) то "— = 1( ду.,'+'), '~1( ду Р'").
(2) Доказательс|пео. Если х не кратно р, то оно может быть представлено в виде х = 1+ др' для некоторого целого д. По биномиальной формуле получаем хг = 1+ р'+ + ~" '~(" 0'+~я~"' Ы 1Р-1! "(+-(,) г -()а'." +-(„)г'"") Величины в скобках являются целыми числами, и к тому же каждый член внутри скобок, за исключением первого, кратен р.
Для таких й, что 1 < й < р, биномиальные коэффициенты ('„') делятся на р (см. упр. 1.2,6 — 10); следовательно, 1 р й/ )4 Р -() Р~ ь — 1 (ь — 11е делится на Р~~ 'и. Последний член д' 'р~г гм ' также делится на р, поскольку (р — 1)е > 1, когда р' > 2. Итак, хг: — 1+ др'+' (по модулю р'+з), что и завершает доказательство, (Замечание. Обобщение этого результата приведено в упр, 3.2.2-11, (а).) $ Лемма с4.
Пусть чвсло т допускает разложение на простые множители в виде (3) т=р| Р~. Длина периода Л линейной конгруэнтной последовательности, определенной параметрамн (Хе,а,с т), является наименьшим общим кратным длин Л пернодов линейных конгруэнтных последовательностей (Хе топ р ', а топ р ', с шоа р ', р ' ), 1<1<1. Доказательсгпео. Если использовать индукцию по 1, то достаточно доказать, что если т1 и тз — взаимно простые числа, то длина Л линейной конгрузнтной последовательности, определенной параметрами (Хе, а, с, т~ тт), является наименьшим общим кратным длин Л, и Ла периодов последовательностей, определенных параметрами (Хе щод ты а щоб ты с щод ты т1) и (Хе шод тз, а шос) тт, стоб тм тз). В предыдущем разделе мы заметили (см.
(4)), что если элементы этих трех последовательностей соответственно обозначены через Х„, У„и Я„, то справедливо равенство У„= Х„шоцт~ и Я„= Х„шоотз длн всех и > О. Поэтому по закону П из раздела 1.2.4 находим, что тогда и только тогда, когда У„= 1ь и л„= Еь. (4) Х„= Хь Пусть Л' — наименыпее общее кратное Л~ и Ла. Необходимо доказать, что Л' = Л.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
