Генератор случайных чисел. Опции

[Stanislav_S]

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

[SIA]

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

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

[Stanislav_S]

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

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

[SIA]

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

Таблица - тут, думаю, все очевидно.
ПСП - это регистр сдвига с обратной связью, формирующий псевдослучайную последовательность максимальной длины (для твоей задачи за глаза хватит длины 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

[Stanislav_S]

Таблица - тут, думаю, все очевидно.
ПСП - это регистр сдвига с обратной связью, формирующий псевдослучайную последовательность максимальной длины (для твоей задачи за глаза хватит длины 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

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