Замечания. Брент (Brent) также рассматривал более общий метод, в котором следующие одно за другим значения Y = Хщ удовлетворяют ni = О, m+i = 14- [pnij, где р - любое число, большее 1. Он показал, что наилучшее значение р, приближенно равное 2.4771, сокращает около 3% итераций по сравнению с ситуацией, когда р = 2. (См. упр. 4.5.4-4.)

Однако метод, описанный в (Ь), имеет серьезные недостатки, так как можно получить много неслучайных чисел, прежде чем прекратится генеририрование, например в особенно неудачном случае, когда Л = 1, /х = 2*. Метод основан на идее Флойда (Floyd) из упр. 6, (Ь):

присваивать значения У = Х2п я X = Хп при п = 0,1,2, Потребуется несколько больше

функциональных оценок, чем для метода Брента, но при использовании метода Флойда работа остановится прежде, чем любое число появится дважды.

С другой стороны, если / неизвестно (например, если получены значения Хц, Xi, ... из постороннего источника) или если сложно использовать /, то в этом случае предпочтительнее применять следующий обнаруживающий циклы алгоритм, который был предложен Р. В. Госпером (R. W. Gosper): для того чтобы получить X п, используют вспомогательную таблицу значений Го, Ti, Гт, где т = l\gn}. Сначала присвоим Го ч- Хц. Для п = 1, 2,... сравниваем Хп с каждым из Го, ..., rignj; если в этой таблице не найдется числа, равного Хп, то присваиваем Те(п) Хп, где е(п) = тах{е 2 делит на п 4-1}. Но если найдется такое Тк, что Хп = Г, то Л = п-тах{ I \ I < п и е{1) = к}. После присвоения Хп значения Tfn) последовательно сравниваем это значение с Xn+i, Хп+2,- -, Х2(")+- Поэтому процедура остановится сразу же после генерирования X+x-hj, где j > О является минимальным среди тех j, для которых выполняется неравенство е{р 4- j) > [IgA] - 1. При использовании этого метода ни одно из значений X не появляется более двух раз и не более чем тах(1, 21-) значений случайных чисел появится более одного раза. [MIT AI Laboratory Memo 239 (February 29, 1972), Hack 132.]

P. Седгевик (R. Sedgewick), T. Г. Шиманский (Т. G. Szymanski) и Э. Ч. Яо (A. С. Yao) проанализировали более сложный алгоритм, основанный на использовании параметров тп > 2 и д > h вспомогательные таблицы размерности тп включают Ао, Хь, Хдь на момент, когда Хп вычислено, где b = г""! и g = ["/1 - 1- Если п mod gb < b, Хп сравнивается с табличными данными; в конечном счете равенство выполняется и мы вычисляем /x и Л, произведя не более чем (р4-1)2""1"" вычислений /. Если вычисление / отнимает время г и если проверка равенства Хп с табличными данными отнимает время сг, то д может быть выбрано так, что общее время счета будет равно {р 4- Л)(г 4- OiY"); если а/т - 0{тп), то время счета оптимально. Более того, А„ не вычисляется, пока не выполнится неравенство /х 4- Л > тпп/{тп 4- 4р 4- 2). Итак, этот "диалоговый" (online) метод можно использовать для гарантированного получения различных случайных чисел, так что для получения одного числа требуется только 2 4- 0(тп~) вычислений функции. [SICOMP 11 (1982), 376-390.]

8. (a,b) 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. С того момента, когда X < Ь", получаем Х < Ь", и средины квадратов равны [X/b"i < ХУЬ"- Если А > О, то ХЬ" < Xb"/b" = X

10. Если X = аЬ", то следующее число последовательности имеет ту же форму; оно равно (о modb")6. Если а кратно всем простым множителям Ь, последовательность вскоре выродится в нуль; иначе она выродится в циклы чисел такой же формы, как число X.

Другие факты о методе средин квадратов найдены Б. Йенссеном (В. Jansson, Random Number Generators (Stockholm: Almqvist к Wiksell, 1966), Section ЗА). Тем, кто интересуется магическими свойствами чисел, небезынтересно будет узнать, что число 3792

является самовоспроизводящим числом в четырехзначном методе средин квадратов, так как 3792 = 14379264; более того, как заметил Йенссен, оно также "самовоспроизводимо" в другом смысле, поскольку его разложение на простые множители имеет вид 3 • 79 • 2*!

11. Вероятность того, что Л=1и/х = 0, - это вероятность того, что Xi = Хо, л именно - 1/т. Вероятность того, что Л = 1, /х = 1 или Л = 2, /х = О, - это вероятность того, что Xl ф Хо, и того, что Х2 принимает определенные значения, т. е. равна (1 - \jm){\jvn). Аналогично вероятность того, что последовательность имеет любые заданные /х и Л, является функцией только от /х 4- Л, а именно:

1<к<+\

Вероятность того, что Л = 1, задается в виде

m V m / m

>0 " k=l

где Q(m) определено в разделе 1.2.11.3, равенство (2). По равенству (25) из того же раздела данная вероятность приближенно равна /njlm и 1.25/л/тп. Шанс, что алгоритм К будет вести себя, как в рассмотренном примере, равен одному из 80000; автора постигла явная неудача. См. другие комментарии о "колоссальности" в упр. 15.

. Е л,. i (..з(: - i) «(, -1) (. -1) .. .) = М,

1<Л<т

0<ti<m

(См. предыдущий ответ. В общем случае, если f{ao,ai,...) = Yln>o an Т11=Л ~ к/тп), то /(ao,oi,...) = ао 4- /(oi,a2,...) - /(ai, 2а2,... )/m; применим это тождество с а„ = (п-1- 1)/2.) Поэтому среднее значение Л (и в силу симметрии Р(/х, Л), а также /х -I- 1) приближенно равно у7гт/8 + . Среднее значение р + \ равняется точно Q{m), что приближенно равно 7гт/2 - . [Альтернативные выводы и другие результаты, включая асимптотические значения моментов, приводятся в А. Rapoport, Bull. Math. Biophysics 10 (1948), 145-157, и В. Harris, Annais Math. Stat. 31 (1960), 1045-1062; см. также Соболь И. М., Теория вероятностей и ее приденения 9 (1964), 333-338. Соболь обсуждает асимптотику длины периода для более общей последовательности Xn+i = f{Xn), если п ф Опомодулют, Хп+1 = д{Хп), если п = Опомодулют, когда одновременно и /, и р случайны.]

13. [Пардом П. (Paul Purdom) и Вильяме Дж. (John Williams), Ti-ans. Amer. Math. Soc. 133 (1968), 547-551.] Пусть Tmn - число функций, имеющих n циклов единичной длины и не имеющих более длинных циклов. Тогда

-С--;)

(Это совпадает с ()г(т,7п - п) в упр. 2.3.4.4-25.) Любая такая функция получается из такой же функции в результате перестановки п циклов единичной длины. Отсюда

En>iTmn п\ = т.

Пусть Рпк - число перестановок п элементов, самый длинный цикл которых имеет длину к. Тогда число функций с максимальным циклом длиной к равно у-ТтпРпк. Чтобы получить среднее значение к, вычислим сумму Yk>i iCn>i тпРпк, которая, как следует из упр. 1.3.3-23, равна Yii Tmn п\{сп + с + 0(п")), где с и .62433. Суммируя, получим, что среднее значение равно cQ{m) + с + 0{т). (Это выражение, в сущности, не больше, чем среднее значение к, когда Ао выбирается наудачу. Среднее значение тах/х

асимптотически равно Q(m)ln4 и среднее значение тах(/х + А) асимптотически равно 1.9268Q(m); см. Flajolet and Odlyzko, Lecture JVotes in Сотр. Sci. 434 (1990), 329-354.)

14. Пусть Cr(m) - число функций, имеющих точно г различных финальных циклов. Из рекуррентного соотношения ci(m) = (m - 1)! - I3fc>o (Т)(~)*("* " fc)*ci(m - к), которое можно получить в результате подсчета числа функций, образ которых содержит не более чем тп - к элементов, следует, что ci(m) = m"~Q{Tn). (См. упр. 1.2.11.3-16.) Другой способ получения ci(m), который, возможно, более элегантен и показателен, приведен в упр. 2.3.4.4-17. Значение Сг(пг) может быть определено так же, как в упр. 13:

t YT Г"1 m-i/1 rn , 1 [21n-l , 1 [-3]m-lm-2 , \

LrJ \ 0! LrJ 1! Lrj m 2! LrJ mm I

n>l Ч /

Теперь можно вычислить требуемое среднее значение (см. упр. 12):

т mm

1 т - 1 1 т - \ т - 2

= 1 +--+---+ • .

2 т 6 т т

Последняя формула была получена несколько ины.м путем М. Д. Крускалом [см. Martin D. Kruskal, АММ 61 (1954),392-397]. Используя интегральное представление

он доказал асимптотическое соотношение limm-+oo(£m - 1п7п) = (7+ bi2). Другие результаты, а также ссылки на литературу, можно найти в работе John Riordan, AnnaJs Math. Stat. 33 (1962), 178-185.

15. Вероятность того, что /(ж) ф х для всех ж, равна (тп - 1)"/т", а это приблизительно равно 1/е. Существование самоповторяющегося значения в алгоритме, подобном алгоритму К, не является поэтому "колоссальным"; его вероятность равна 1 - 1/е « .63212. "Колоссальным" было только то, что автору удалось получить такое значение Хо при случайном выборе (см. упр. И).

16. Последовательность повторится, когда пара следующих один за другим элементов встретится второй раз. Максимальный период равен т. (См. следующее упражнение.)

17. После произвольного выбора Хо,..., X-i пусть Xn+i = /(Хп,..., Xn-k+i), где О < xi,...,Xk < т влечет то, что О < f{xi,... ,Хк) < т. Максимальный период равен ш*. Это очевидная верхняя граница, однако не очевидно, что она достижима, для конструктивного доказательства того, что она достижима для подходящей функции / (обратитесь к упр. 3.2.2-17 и 3.2.2-21; численный метод приводится в упр. 2.3.4.2-23).

18. Метод такой же, как в упр. 7, но используйте цепочку из к элементов (Хп,..., Xn ife+i) вместо элемента Хп.

20. Достаточно рассмотреть простое отображение д{Х), определяемое на шагах К2-К13. Следя в обратном порядке от числа 6065038420, получим в общей сложности 597 решений; наименьшим числом является 0009612809, а наибольшим - 9995371004.

21. Можно работать с д(Х), как и в предыдущем упражнении, но сейчас необходимо запустить функцию в прямом порядке. Существует интересная взаимосвязь между временем и пространством. Используя несколько мегабайтов памяти, автор в 1994 году проверил это предположение для всех начальных значений, меньших, чем 0000165181, но решил подождать несколько лет, прежде чем продолжить исследования, так как компьютеры становились все больше и мощнее. Заметим, что механизм шага К1 способствует уменьшению