Потребовалось тут реализовать ГСЧ на AVR. Интересует каков алгоритм реализации, числа должны лежать в диапазоне 0 - 9. В детстве делал такую штуку на МК61 , но к сожалению как это делать в памяти совершенно не отложилось

При таком диапазоне - всего 10 значений - погрешность от дискретности может сравняться с погрешностью от периодичности уже при длине таблицы в 100-200 чисел. Тогда проще всего зашить табличку (50-100 байт всего). Если генерить - то либо ПСП, либо линейный конгруэнтный метод (правда, там множить надо).

А можно подробнее о этих методах, или хотя бы какие ключевые слова для поиска?

Таблица - тут, думаю, все очевидно.
ПСП - это регистр сдвига с обратной связью, формирующий псевдослучайную последовательность максимальной длины (для твоей задачи за глаза хватит длины 15 бит). Делается его программная модель, и выбираются 4 бита из него. Единственная проблема - он двоичный, а тебе нужен диапазон 0...9, придется отбрасывать числа 10-15. При получении следующего числа для уничтожения явной корреляции нужно "прокручивать" регистр не менее, чем на его длину, например, на 16 циклов.
Линейный конгруэнтный метод - берем начальное число, следующие генерим из него:
x[n+1] = (a*x[n]+ c) mod M, a, c, М - константы. для M = степень двойки , ПСЧ имеет максимальную длину M, когда C - нечётное, а A mod 4 = 1.

Вот простая подборка по теме
http://www.uni-vologda.ac.ru/students/pm02...eudorandom.html

ОК! Спасибо, буду думать.

А что такое в данном случае погрешность от дискретности?

То, что распределение не непрерывное, а всего 10 дискретных значений - 0...9, к примеру, 4,5 не будет никогда.

А дискретные случайные величины Вы считаете неправильными?

Ну да, это типа "Бросаем игральную кость. Погрешность выпавшего числа N составляет..."

Да "правильные" они , просто при числе состояний N для устаканивания статистики (первой пары моментов - среднего и СКО) достаточно длины выборки порядка N^2. Проще говоря, повторяющаяся таблица длиной порядка N^2 во многих (но, конечно, не всех) задачах будет сравнима с истинно случайными числами. N здесь маленькое, таблица получается короткой. А короткую таблицу шебуршить проще простого, особенно если счетчик модулярный, места займет меньше, чем программный генератор. Я потому и дал несколько вариантов и ссылку - пусть сами выбирают, что лучше подойдет.

Сообщение отредактировал SIA - Jul 23 2007, 15:26

Ну первую пару моментов, хотя СКО вовсе не момент а корень из него, с очень большой натяжкой можно считать критерием близости экспериментальной ф-ии распределения выборки к некой желаемой. С очень большой натяжкой. И даже их устаканивание. Иначе всех, жаждущих случайности, спас бы генератор синуса с подставкой.
Сравнимость таблицы размером порядка N^2 с истинно случайными числами тоже вызывает смутные сомнения . Т.е. критерий сравнимости хотелось бы.
И простой пример.
Возьмите всего 2 равновероятных состояния (N=2) , 1 и -1. Вероятность каждого 0.5. Легко посчитать, что вероятность 2-х подряд идуших 1, или -1, равна 0.25. 3-х подряд - 0.125, 4-х подряд - 0.0625. Не такие уж и малые вероятности. У меня вызывает большие сомнения, что таблица из 4 элементов способна обеспечить появление хотя бы всех вышеперечисленных комбинаций с нужными вероятностями.

1. Универсального критерия на ВСЕ случаи жизни нет и быть не может. Но простейший пример, где таких "случайных" чисел (конечно, при достаточно большом N) вполне хватает - приближенное вычисление площади фигуры методом Улама/Монте-Карло. И таблицы случайных чисел в том числе и для этого в свое время и печатали, кстати, объем их редко достигал N^2. Естественно, этот способ годится не для всех задач, о чем я и предупреждал. Решать-то не мне, а тому, кто спрашивал. Мое дело - предложить варианты, пусть выбирают.
2. Вы рассматриваете вырожденный (особый) случай - всего 2 состояния, типа бинарного потока. Однако жесткие требования к статистике в таких случаях встречаются в основном при формировании длиннобазовых сигналов, когда важны требования к корелляционным свойствам (о чем исходно речи не было). В случае длиннобазового сигнала таблица длиной менее длины базы некорректна, к тому же для бинарной последовательности часто проще сделать ПСП на регистре. В то же время при увеличении числа состояний вероятности конкретных цепочек событий резко падают, и то, что далеко не все из них будут в таблице, а у оставшихся вероятность повышена, во многих случаях перестает иметь практическое значение. Конкретный пример - таблица порядка N^2 даст большинство двойных сочетаний, но (по порядку величины) только 1/N от общего числа тройных, завышая вероятность представленных в таблице с ~N^-3 до ~N^-2. Однако во вполне типовой задаче типа рандомизации ошибки округления это не имеет никакого практического значения.
3. Генератор синуса с подставкой - слишком сложен в вычислительном отношении, и распределение у него дальше от равномерного, чем у тупого генератора пилы на счетчике. Собственно, линейный конгруэнтный метод - это и есть сильно модифицированный модулярной арифметикой генератор пилы .
4. Напоследок замечу, что для такой безусловно практической задачи, как "случайный" выбор этажа, на котором должен отдыхать лифт, вся вышеизложенная теория заведомо избыточна
5. Больше писать просто лень. Не вижу смысла. Кому охота цепляться к мелочам - тратьте время сами, мне работать надо.

1. Так у Вас никакого не было критерия вообще, кроме матожидания и дисперсии, которые критерием случайности не являются.
2. На вырожденном все виднее
3. Генератор синуса с подставкой прекрасно заменяет случ. величину, и даже случайный процесс, с любым распределением, если критерием близости распределений считать матожидание и дисперсию
К тому же он является сильномодифицированным генератром пилы. И этим особенно близок к линейному конгруэнтному методу.
4. Все может быть.
5. Да ради бога, работайте. Если бы Вы не притянули некую наукообразность, а просто предложили бы генератор ПСП, лин. конгруэнтныйд, Парка-Миллера, ктороый правда тоже можно считать конгруэнтным, только вырожденным, еще чего- нибудь, я бы и словап не сказал.

А может быть все проще?
я делаю так:

// функция rnd(x) вернет числа между 1 и заданым максимумом x.
// rnd(10) вернет числа между 1 и 10, rnd(50) вернет числа между 1 и 50
int rnd( int max )
{
return (rand() % max) + 1;
}