Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 28
Текст из файла (страница 28)
Дальнейшие упрощения произойдут, когда мы более подробно исследуем зту итеративную процедуру. Положим, что т1 = Ь, тз = Ь, с1 = с, и построим следующую таблицу. (32) ат = (т,/тт+1), тт+2 = т; тот(т,+1, б, = (ст/тт+1), Ст.1.1 = Ст' Шод 171141 ° Отсюда следует, что О < тпте1 < т, Для удобства предположим, что алгоритм Евкляда закончится в (32) после четырех итераций, Это предположение будет иметь структуру„подобную той, которая наблюдается в общем случае. Так как Ь и Ь вЂ” взаимно простые числа, для начала в (32) следует положить тз = 1 и сз = О. Допустим также, что сз ~ О, но с4 = 0 для того, чтобы получить эффект от применения рекуррентной процедуры.
равенства (ЗО) и (ЗЦ дают с(Ь,л,с) = с(тз,тт,ст) /(тз, тт, ст ) — с(тз, тз, сз) = У(тз,т1,с1) У(тз,тз,сз)+У(т4,тз,сз) т(тз~тт14 сз) Первая часть Ь/Ь+ Ь/Ь формулы для /(Ь, б, с) в (19) приводит к добавлению тз тз т4 тпз тз т4 + + т1 1112 т2 1116 тпз п14 т4 тпз к общей формуле, которая сводится к тт11 — птз т2 тз тз тз т4 -+ + — + ат — аз+ аз — а4. Ь тз тз т4 111$ Следующая часть (19), 1/ЬЬ, также приводит к простому добавлению; в соответ- ствии с 4.5,3-(9) и другими формулами раздела 4.5.3 получим 1 1 1 1 Ь' + (35) тттз тпзтз Птэт4 тзтаз где Ь' — единственное целое число, удовлетворяющее Ь'Ьвз1 (по модулю б), 0<Ь'<Ь. т1 а1т2 + тз птз = азтпз + т4 тпз — езт,1 + тз т4 = азтз С1 = бттз+ сз сз = бзтз+сз сз — бзт4 + с4 ст = 64тпз+ сз Добавляя все эти слагаемые, вспомним о предположении, что с4 = 0 (так что с(п44, сз) = О, см. (20)).
Находим, что Л+ Ь' сг(Ь, Л, с) — — + (й( — йз + йз — й4) — 6(Ь( — Ьз + ЬЗ Ь4) сз сз сз сз +6 1 2 + 3 4 ГП( ГЛЗ ГПЗГПЗ Гйзтйз Гй42йз / в терминах таблицы (32). Подобный результат имеет место в общем случае. Теорема О. Пусть Ь, Ь и с — цетые числа с 0 < Ь < Л, О < с < Ь и Ь, взаимно простым с л, Образуем "таблицу евклида", как определено в (32), л прелполо2кггм, что процесс остановятся после 2 шагов с пз(+2 -- 1.
Пусть 3 — наименьший индекс, для которого с, = О, и пусть число Ь' определено в (36). Тогда (а,(4= — ' 2, (-()г ( г — Ю;~.6 — ( — ) Л+ Ь' пг шу +3((-Ц" +6. ) — 2+ ( — Ц'. Алгоритм Евклида тщательно анализируется в разделе 4.5.3; величины йг, йз, ..., аз называются часшпчнмззи оглношенцлми Ь/Л, Теорема 4.5.32 указывает, что число итераций 2 никогда не превосходит 1ойе Ь; следовательно, суммы Дедекннда могут быть быстро вычислены. Члены с~3~из пг +г мшкно упростить еще больше; эффективный алгоритм для оценки (2(Л, Л, с) можно найти в упр. 17.
Изучив обобщенные суммы Дедекинда, применим полученные знания для вычисления серивльного коэффициента корреляции. Пример 1. Найти серзгазьный коэффициент, когда пз = 233, а = 234 + 1, с = 1. Решение. Из (17) следует, что справедливо соотношение (2ззй(234 + 1 2зз Ц 3+ 6(223 (234 Ц Ц) г(22о Ц Чтобы вычислить й(234 + 1, 233, ц, мсокно образовать следующую таблицу.
Так как Ь' = 234 + 1, это значение в соответствии с теоремой П становится равным 233 — 3+2 32 Таким образом С (233+ 6).((22е Ц г + (с) < 2-32 (37) Подобная корреляция намного превышает ту, которая должна быть у случайной последовательности. Конечно, этот генератор имеет очень низкий потенциал и его можно было бы отбросить и раньше, как неслучайный.
пз — 233 п22=234+1 тз =2 — 1 З4 п24 =2 шз = 1 й( =1 аз=1 аз = 233 — 1 й4=2 сг =1 сз =1 сз =1 с4=1 сз=о ь =о ь =о ЬЗ=О Ь4 = 1 Пример 2. Найти приближенное значение когда т = 10~с а = 10001, с = 2113248653. Решение. Справедливо равенство С следующим образоис т1 = 10000000000 тз = 10001 тз ж 100 тз = 1 коэф4пцпеита сериальлой корреляции, а(а,т,с)/т.
Вычисления производим с~ = 2113248663 сз = 7350 сз = 50 сз = О Ь = 2ПЗОЗ ба= 73 бз — 50 а| — — 999900 аз = 100 аз = 100 а(тытз,с1) = -31.6926633544; С ш -3 10 э. На самом деле это очень приемлемое значение С. Но потенциал генератора равен только 3, гак что реально это не очень хороший датчик случайных чисел, несмотря яа то что у него низкая серивльная корреляция. Таким образом, необходимо (но не достаточно) иметь низкий сериальный коэффициент корреляции. Пример 3. Оценить сериальиую коррелянта для пронзвольньш а, т н с.
Решение. Если применить только один раз соотношение (30), то получится небольшие лознаиия — оласиал вещь. — АЛЕКСАНДР ПОП (АЬЕХАИОЕй РОРЕ), Эссе о ипигиие, гзз (ттП) Если серьезно проанализировать ошибки, то можно лучше понять, как были допущены злоупотребления в (39), Во-первых, кое-кто некритична предполагал, что маленькая сериальная корреляция по целому периоду является хорошей гарантией т сз с а(а,т,с) щ — + 6 — — 6- — а(т,а,с), а ат а Поскольку нз упр. 12 следует, что (а(т, а, с)~ < а, справедливы соотношения а(а,т,с) 1 / с 7 с ~зЪ Са ' ' ш — ~1-6 — +6~ — ) ) .
(39) т а~, т ~т)) Ошибка этой аппроксимации по абсолютной величине меньше (а + 6)/т. Оценка в (39) — это первый известный теоретический результат, касающийся случайности конгруэнтных последовательностей (генераторов). Р. Р. Ковэю (Н. Н. Сотеуоп) (,)АСМ 7 (1960), 72-74) получил его методом усреднения по всем действпшельнзьм числам х, лежащим между О н т, вместо того, чтобы рассматривать только целые числа (см. упр. 21). Затем Мартин Гринбергер (Магйп ОгеепЬегйег) [Магй. Сошр. 16 (1961), 383-389) нашел точное отклонение, включая н оценку ошибки. Так началась одна нз самых грустных глав в истории компьютерной науки.' Хотя приведенная выше аппроксимация была вполне корректной, она была совершенно неприемлемой на практике.
Люди отбросили хорошие генераторы и заменилн их ужасными генераторами, казавшимися хорошими с точки зрения критерия (39). Более чем на десятилетие репутация наиболее используемых генераторов случайных чисел была серьезно подорвана только в связи с прогрессом теории. случайности. На самом же деле она не может обеспечить даже маленькую сериальную корреляцию для 1 000 последовательных элементов последовательности (см. упр.
14). Во-вторых, (39) и точность приближения обеспечивают относительно малое значение С только при а тп ~/ш. Поэтому предлагалось выбирать множитель, равный примерно л/ш. На самом деле почти все множители дают значения С, постоянно меньшие, чем 1/~/т, поэтому (39) не является очень хорошей аппроксямацией истинного поведения оценки. 51инимизацня грубой верхней границы С не минимизирует само значение С.
В-третьих, было замечено, что (39) дает свои самые лучшие оценки, когда с/ттс е 1 х 1е лтЗ, (40) Теорема К. Прн предположениях теоремы Р всегда выполняется < ~~с а, + — ~~с а, — —. (41) 1 1 с<с<с с<с<с 1 ат — ~~т а; < а(Л,Л,с) сбтйс с<с<с т еаа 12ееп т еееп Докаэапсеяьсспео. Обратитесь к работе Д. Э.
Кнута (Р. Е. КпцФ, Асса Агсййшебса 33 (1978), 297-325), в которой, кроме всего прочего, показано, что эти границы, по существу, — наилучшие возможные границы, когда частичные отношения большие. 1 Пример 4. Оцените сертииьную корреляцию для а = 3141592621, пл = 2зл и нечетного с. Решение. Частичные отношения а/т равны 10, 1, 14, 1, 7, 1, 1, 1, 3, 3, 3, 5, 2, 1, 8,'7, 1, 4, 1, 2, 4, 2. Таким образом, по теореме К -55 < а(а,пс,с) < 67.5 и сериальиая корреляция гарантированно будет крайне низкой для всех с. Заметим, что эта граница значительно лучше, чем можно было получить из (39), так как ошибка в (39) илтеет порядок а7т. Неш еслучайный" множитель не может быть настолько лучше специально выбранного множителя, чтобы хорошо выглядеть так как этн значения являются корнями уравнения 1 — бх+ бхз = О.
еПрн отсутствии любого другого критерия выбора с можно использовать и этот." Последнее утверждение имеет смысл, но оно вводит в лучшем случае в заблуждение, так как эксперимент показал, что значение с оказывает большое влияние на истинное значение сериального коэффициента корреляции, когда а — хороший множитель. Выбор (40) в значительной степени снижает значение С только в случаях, аналогичных примеру 2. И мы обманываем себя, так как плохой множитель продемонстрирует свои недостатки другим путем. Ясно, что необходима лучшая оценка, чем (39).
Такая оценка сейчас доступна благодаря теореме Р, в основных чертах доказанной в работе Ульриха Дитера ( сЛг1сЬ Р1есег) (Маей. Соспр. 25 (1971), 855-883). В соответствии с теоремой Р а(а, пл,с) будет малым, если частичные отношения а/та малы, Кроме того, детальнее анализируя обобщенные суммы Дедекншла, можно получить вполне точные оценки. при использовании (39). На самом деле можно показать, что среднее значение ~„,, и, взятое по всем множителям а, относительно простым с гп, равно — (1п гп)з + О((!ойт)(1ой !ок т)~) (см. упр. 4.5.3-36). Поэтому вероятность того, что случайный множитель имеет большую сумму 2 ',, а,, скажем, больше (!оя гл)~+' для некоторого фиксированного с > О, стремится к нулю при гл -э ж.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
