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