Генератор случайных чисел на основе ряда натуральных чисел

Новый комментарий
 
Подскажите плиз, можно ли из ряда натуральных чисел образовать псевдослучайные числа по следующему алгоритму:
1. записываем ряд натуральных чисел подряд без пропусков.
2. выбираем число знаков будущего псевдослучайного числа.
3. режем ряд натуральных чисел этим числом знаков.
4. получаем псевдослучайные числа.

Например:
Ряд: 123456789101112131415...
Число знаков: 3
Полученные числа: 123 456 789 101 112 131 415
т.о. мы получил последовательность псевдослучайных чисел.

Собственно вопросы:
1) Являются ли полученные числа равномерно распределёнными на интервале 000-999?
2) Если да, как это доказать?
 
capporicci >>:
1) Являются ли полученные числа равномерно распределёнными на интервале 000-999?
2) Если да, как это доказать?

Легче проверить, набросав код, чем пытаться доказать. Самопальный алгоритм вряд ли будет лучше сишного.

 
capporicci писал(а) >>
Собственно вопросы:
1) Являются ли полученные числа равномерно распределёнными на интервале 000-999?
2) Если да, как это доказать?

Не придумывайте алгоритмы, если не уверены в своих математических способностях. С большой вероятностью ваши алгоритмы окажутся ошибочными.
Рекомендую найти трехтомник Дональда Эрвина Кнута "Искусство программирования для ЭВМ" ("The Art of Computer Programming") и внимательно прочитать третью главу из второго тома.
Можно упростить себе жизнь и воспользоваться готовым генератором из cryptoapi (CryptGenRandom - http://msdn.microsoft.com/en-us/library/aa379942(VS.85).aspx).

 
lea >>:

Не придумывайте алгоритмы, если не уверены в своих математических способностях.

Я предложенный алгоритм не придумывал, а вспомнил из студенческого прошлого. Поиск по инету ничего не дал. Соответственно вопрос: качественно данный алгоритм является ли ГПСЧ и полученные ПСЧ являются ли равномерно распределёнными? Если не знаете - не пишите, плиз..

 
Нет, некачественно. Есть зависимость между соседними числами. Какая - не знаю. Но ее можно вычислить.
Гораздо надежнее, если уж на то пошло, взять последовательность знаков числа Pi после запятой. Миллион в сетке есть точно.
 
capporicci писал(а) >>

Соответственно вопрос: качественно данный алгоритм является ли ГПСЧ и полученные ПСЧ являются ли равномерно распределёнными?


Проверить равномерность не трудно - генерируете случайные числа (несколько миллионов для точности), считаете количество появлений каждого числа. Далее анализируете отклонения от среднего. Однако равномерное распределение не является залогом качества. Как проверить качество - это можно прочитать у Кнута.
Ещё могу порекомендовать книгу Джулиана Бакнелла "Фундаментальные алгоритмы и структуры данных в Delphi". ГПСЧ там посвящена отдельная глава (куча реализаций и прога для проверки качества при помощи различных критериев). К книге прилагается архив с исходниками, так что вам нужно будет лишь реализовать класс вашего генератора и запустить прогу.

 
Вообщем, и на том спасибо.
 
lea >>:

Не придумывайте алгоритмы, если не уверены в своих математических способностях. С большой вероятностью ваши алгоритмы окажутся ошибочными.
Рекомендую найти трехтомник Дональда Эрвина Кнута "Искусство программирования для ЭВМ" ("The Art of Computer Programming") и внимательно прочитать третью главу из второго тома.
  

Все три тома можно скачать здесь http://depositfiles.com/files/msfrmgg71

 
drknn >>:

Все три тома можно скачать здесь http://depositfiles.com/files/msfrmgg71



Пасиб!
На другой ветке задавал тот же вопрос, один чел бездоказательно утверждал, что при n=1 распределение равномерно (на интервале 0...9 разумеется).
 
capporicci >>:


Пасиб!
На другой ветке задавал тот же вопрос, один чел бездоказательно утверждал, что при n=1 распределение равномерно (на интервале 0...9 разумеется).


Ну теперь пусть скачает эту книгу и скажет, на какой страничке какого тома лежит доказательство его суждения :)
Новый комментарий