AOP_Tom2 (1021737), страница 163
Текст из файла (страница 163)
[Замечание. Это, в сущности, доказательство известного математического утверждения; "Степени элемента конечной полугруппы включают единственный идемпотеитный элемент: возьмите Хс — — а, 7(х) = ах".] (с) Как только и найдено, генерируем Х, и Х„+; для с > О до тех пор, пока найдется первое Л, = Л" +,, тогда д = с. Если ни одно из значений Х +, при 0 < с < р не равно Хса значит, Л = и, иначе Л вЂ” наименьшее из таких с. 7. (а) Наименьшее значение и > О, такое, что и — (б(и) — 1) кратно Л и б(и) — 1 > д, равно и = 2 ~л"*'"с" +с Ю' — 1+ Л. [Это можно сравнить с наименьшим и > О, при котором Хс = Л„т.
е. Л([д/Л) + б~ а) ) (Ь) Начните со значения Х = У = Хе, )с ш т ж 1. (На ключевом месте в этом алгоритме получим Х = Лс с и 1 = Х с и ис ж б(2т — 7с).) Для генерирования следующего случайнога числа выполним такие шаги. Установим Х с — 7'(Х) и /с с — 7с — 1. Если Х = У, останонка (длина периода Л равна т — )с). Если х = О, установим У с- Х, т с- 2т, й с- т. Получим Л'. Замечания. Брент (Втсп!) также рассматривал более общий метод, в котором следующие одно за другим значения У = Х»ч удовлетворяют п~ = О, пгю = 1 + (рп;), где р -- любое число, большее 1, Он показал, что наилучшее значение р, приближенно равное 2.4771, сокращает около 3% итераций по сравнению с ситуацией, когда р = 2.
(См. упр. 4 5.4-4.) Однако метод, описанный в (Ъ), имеет серьезные недостатки, так как можно получить много неслучайных чисел, прежде чем прекратится генеририрование, например в особенно неудачном случае, когда Л = 1, д = 2'. Метод основан на идее Флойда (Р!оус!) из упр. 6, (Ъ) присваивать значения У = Хэ и Х = Х при и = О, 1, 2,.... Потребуется несколько больше функциональных оценок, чем для метода Брента, но при использовании метода Флоцда работа остановитсв прежде, чем любое число появится дважды.
С другой стороны, если / неизвестно (например, если получены значения Хо, Хы, .. из постороннего источника) или если сложно использовать /, то в этап случае предпочтительнее применять следующий обнаруживающий циклы алгоритм, который был предложен Р. В. Госпером (В. Ч!. Соэрег) для того чтобы получить Х», используют вспомогательную таблицу значений Те, Тм ..., Т»н где ш = (!8п).
Сначала присвоим Те е — Хо. Для и = 1, 2,... сравниваем Х„с каждым из То., Тра„! , 'если в этой таблице не найдетсв числа, равного Х„, то присваиваем ТМ»! +- Л, где е(п) = гаах(е ! 2' делит на п + 1). Но если найдется такое тю что х» = тю то л = и-шах( ! / ! < и и е(!) = )г). после присвоения Х значения Т»!»! последовательно сравниваем это значение с Х„ем Х„~.э,..., Х„+ги ым Поэтому процедура остановится сразу же после генерирования Х».»ьчч. где / > 0 является минимальным среди тех /, для которых выполняется неравенство е(д + /) > (!8 Л) — 1. При использовании этого метода ни одно из значений Х не появляется более двух раз и не более чем шах(1, 20э~! ') значений случайных чисел появится более одного раза.
(М1Т А1 ЬаЪогагогу Мепзо 239 (РеЪгпагу 29, 1972), Насй 132.) Р. Седгевик (В. Бег)бевч!сй), Т. Г. Шиманский (Т. С. 8хупгапэрй) и Э. Ч. Яо (А. С. Уво) проанализировали более сложный алгоритм, основанный на использовании параметров гп > 2 и д > 1: вспомогательные таблицы размерности ш включают Хо, Хы ..., Хгэ на момент, когда Х вычислено, где Ь = 2!'е "7~! и д = (и/Ь! — 1.
Если и шос) дЬ < Ь, Х„ сравнивается с табличными данными, в конечном счете равенство выполняется и лгы вычисляем и и Л, произведя не более чем (д+1)2 э~»~ !!э' вычислений /. Если вычисление / отнимает время г и если проверка равенства Х с табличными данными отнимает время и, то д может быть выбрано так, что общее время счета будет равно (и + Л)(т + 0( — ') ч~); если а/г = 0(т), то время счета оптимально. Более того, Х не вычисляется, пока не выполнится неравенство д+ Л > тп/(т + 49+ 2). Итак, этот "диалоговый" (оп!ше) метод можно использовать для гарантированного получения различных случайных чисел, так что для получения одного числа требуется только 2 + О(т ч ) вычислений функции. (ЯСОМР 11 (1982), 376-390.) 8. (а,Ъ) 00,00,...
(62 начальных значения); 10, 10,... (19); 60,60,... [15); 50,50,... (1]; 24, 57, 24, 57, (3). (с) 42 или 69; оба эти числа дают множества, содержащие 15 различных значений, а именно: 42 или 69, 76, 77, 92, 46, 11, 12, 14, 19, 36, 29, 84, 05, 02, 00. 9. С того момента, когда Х < Ь", получаем Х < Ь™, и средины квадратов равны (Х~/Ь") < Хе/Ь".
Если Х > О, то Х /Ь" < ХЬ»/Ь" = Х. 10. Если Х = аЬ", то следующее число последовательности имеет ту же форму; оно равно (а шог1Ь )Ь". Если а кратно всем простым множителям Ь, последовательность вскоре выродится в нуль; иначе она выродится в циклы чисел такой же формы, как число Х Другие факты о методе средин квадратов найдены Б. Йенссеном (В. Лапшов, Вапг(ош Аитбег Селегагогз (Бгос1~Ъо!ш: А!пщч!в! 5г Лайзе!1, 1966), Бесйап ЗА).
Тем, кто интересуется магическими свойствами чисел, небезынтересно будет узнать, что число 3792 является самовоспроизводящим числом в четырехэначном методе средин квадратов, так как 3792 = 14379264; более того, как заметил Йенссен, оно также "самовоспроизводимо" в другом смыш»е, поскольку его разложение на простые множители имеет вид 3 79 2~! 11. Вероятность того, что Л = 1 и д = О, — это вероятность того, что Х» = Хо, а именно— 1/гп. Вероятность того, что Л = 1, д = 1 или Л = 2, д = О, — это вероятность того,что Х» Э» Ха, и того, что Хэ принимает определенные значения, т.
е. равна (1 — 1/т)(1/т). Аналогично вероятность того, что последовательность имеет любые заданные д и Л, является функцией только от д+ Л, а именно: п( ) »<»<»а» Вероятность того,что Л = 1, задается в виде К-„'й( --.") =-.' (гл »>о где 1г(гп) определено в разделе 1.2.11.3, равенство (2). По равенству (25) из того же раздела данная вероятность приближенно равна ь/я/2т 1.25/»/т. Шанс, что алгоритм К будет вести себя, как в рассмотренном примере, равен одному из 80000; автора постигла явная неудача. См другие комментарии о "колоссальности" в упр. 15.
12. ~ ЛР(В,Л) = — [1+3(1 — — )+ф — — ) [1 — — )+ )— »<»< о«„ (См. предыдущий ответ. В общем случае, если /(ао,а», . ) = 2 1>о а П»=»(1 "/гп) то /(яо,а»:. ) = ае + /(а»,аэ,...) — /(ам 2аэ, )/т; применим это тождество с а (и+ 1)/2.) Поэтому среднее значение Л (и в силу симметрии Р(дЛ), а также д + 1) приближенно равно»/игл/8 + -'. Среднее значение д + Л равняется точно Я(гл), что приближенно равно ь/л»п/2 — -'. [Альтернативные вывод»а и другие результаты, включая асимптотические значения моментов, приводятся в А. ВаророгС, Вп!!.
Ма»Ь. В!ор!»уэ!сэ 10 (1948), 145-157, и В. Нагпэ, Аппа!э Ма»Ь. агап 31 (1960), 1045-1062; см. также Соболь И. М., Теория вероятностей я ее применения 9 (1964), 333-338. Соболь обсуждает асимптотику длины периода для более общей последовательности Х„а~ —— /(Х ), если и ~ Опомодулюга, Х „.» = д(Х„), если и = Опомодулюпэ, когда одновременно и /, и д случайны.) 13. [Пардом П. (Рап1 Рвгбош) и Вильямс Дж. (ЗаЬп 1Ч»!5»ашэ), 2?апэ. Ашег. Л!а»Ь. Зос. 133 (1968), 547 551 ] Пусть тмя — число функций, имеющих и циклов единичной длины и не имеющих более длинных циклов.
Тогда та=( ) (Это совпадает с (",)г(ш,т — и) в упр. 2.3.4.4-25.) Любая такая функция получается нз такой же функции в результате перестановки п циклов единичной длины. Отсюда ~..„т„„п! = Пусть Р„» — число перестановок и элементов, самый длинный цикл которых имеет длину Ь. Тогда число функций с максимальным циклом длиной Ь равно 2 „>, Т Р„».
Чтобы получить среднее значение Ь, вычислим сумму 2„»>» 2 „>, ЬТ „Р„», которая, как следует из упр 133 -23, равна 2 „>, Т ь п)(си + »с+ О(п ')), где с ж .62433. Суммируя, пахучим, что среднее значение равно с»,1(гп) + -'с+0(гл ! ). (Это выражение, в сущности, не больше, чем среднее значение Ь, когда Хе выбирается наудачу. Среднее значение шах д асимптотически равно Я(гп) !п4 и среднее значение шах(р + Л) асимптотически равно 1.9268Я(т); см. На)о!ее вп7! 07(!Узко, Ьес1вге Негев ш СошР. 8<7'. 434 (1990), 329-354 ) 14. пусть с,(гп) — число функций, имеющих точно 7 различных финальных циклов. из рекуррентного соотношения с7(гп) = (ги — 1)! — 3 >е („)(-1)ь(гп — 77) с7(гл — к), которое можно получить в результате подсчета числа функций, образ которых содержит не более чем гп — й элементов, следует, что с7(гп) = гп 'Я(гп).
(См. упр, 1.2.11.3 — 16.) Другой способ получения с7(ш), который, возможно, более элегантен н показателен, приведен в упр. 2.3.4.4 — 17. Значение с,(гп) может быль определено так же, как в упр. 13: ,,Р 7=те.(")= -'( — ',(') — „Ц'" ' — ',Ц '" 7 ) Теперь можно вычислить требуемое среднее значение (см. упр. 12): 1 7' гп 1 7п — 1 7п — 2 Е„, = — 7( Н7 + 2Н7 + ЗНз + ) т ~ 7П 7П 7П 17п — 1 1т — 1т — 2 + — 1+ + 2 гп 3 гп 7п последняя формула была получена несколько иным путем м.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
