| |
 Инициализация псевдослучайной последовательности, как это сделать? |
|
|
|
|
 Mar 20 2011, 12:29
|
Гуру
Группа: Участник
Сообщений: 3 834
Регистрация: 14-06-06
Из: Moscow, Russia
Пользователь №: 18 047
|
Цитата(ARV @ Mar 20 2011, 12:54)  мне нужен вариант, требующий не более 200 байт кода. У меня реализация xorshift (32-битный вариант) - 40 слов (80 байтов). asm, и, для экономии, без сохранения регистров (ускоренный вариант и с сохранением - вдвое толще). Нужно ? Избыточно, конечно (для озвученных требований), и не очень эффективная реализация (поскольку алгоритм плохо подходит для 8-битных контроллеров, и не умеющих сдвигать иначе как на один бит),зато просто исключительно хорошее распределение.
Сообщение отредактировал rx3apf - Mar 20 2011, 12:32
|
|
|
|
|
|
|
|
Mar 20 2011, 13:38
|
Профессионал
Группа: Свой
Сообщений: 1 143
Регистрация: 30-09-08
Из: Новочеркасск
Пользователь №: 40 581
|
Цитата(rx3apf @ Mar 20 2011, 15:29) У меня реализация xorshift (32-битный вариант) - 40 слов (80 байтов). asm, и, для экономии, без сохранения регистров (ускоренный вариант и с сохранением - вдвое толще). Нужно ? Избыточно, конечно (для озвученных требований), и не очень эффективная реализация (поскольку алгоритм плохо подходит для 8-битных контроллеров, и не умеющих сдвигать иначе как на один бит),зато просто исключительно хорошее распределение. по идее xor-shift довольно прост, все дело в "полиноме", не так ли? у меня сейчас так: Код static uint16_t prev_rand;
uint8_t rand(void){
if(prev_rand & 1)
prev_rand = (prev_rand >> 1) ^ POLYNOM;
else
prev_rand >>= 1;
return prev_rand & 7; // мне нужно число от 0 до 7 (точнее, 0 не нужно, но это мелочи)
} думаю, ваш вариант аналогичный, разве что не 16, а 32 бита "регистр". все упирается именно в POLYNOM... который я так и не смог подобрать... или я что-то не так делаю? так как я по сути использую только младшие 3 бита, меня интересует распределение именно этой части - все мои попытки дают крайне короткую последовательнсоть ИМЕННО этих битов... скажите мне свой полином - я протестирую, может. ваш вариант будет лучше...
--------------------
Я бы взял частями... но мне надо сразу.
|
|
|
|
|
|
|
|
Mar 20 2011, 14:05
|
Гуру
Группа: Участник
Сообщений: 3 834
Регистрация: 14-06-06
Из: Moscow, Russia
Пользователь №: 18 047
|
Цитата(ARV @ Mar 20 2011, 16:38) скажите мне свой полином - я протестирую, может. ваш вариант будет лучше... xorshift реализуется не так, как большинство простых алгоритмов реализации ПСП (обратная связь по нескольким "отводам" из регистра сдвига - полиномы для которых можно посмотреть, например, у Хоровица и Хилла), там сдвиг всего содержимого и xor всего этого добра. CODE ;----------------------------------------------------------------------
; Генератор псевдослучайных чисел (алгоритм XorShift32)
; Используются и не сохраняются регистры r2...r9, Z и temp
;----------------------------------------------------------------------
XorShift32:
ldi ZH,high(Rnd32)
ldi ZL,low(Rnd32)
ldd r5,Z+0
ldd r4,Z+1
ldd r3,Z+2
ldd r2,Z+3
movw r9:r8,r5:r4
movw r7:r6,r3:r2
ldi temp,5
XS32_1:
lsl r6
rol r7
rol r8
dec temp
brne XS32_1
eor r5,r8
eor r4,r7
eor r3,r6
movw r7:r6,r5:r4 ; сдвиг вправо на 16
lsr r7
ror r6 ; и еще на 1
eor r3,r7
eor r2,r6
movw r9:r8,r5:r4
movw r7:r6,r3:r2 ; копия регистра
ldi temp,5
XS32_2:
lsl r6
rol r7
rol r8
rol r9
dec temp
brne XS32_2
eor r5,r9
eor r4,r8
eor r3,r7
eor r2,r6
std Z+0,r5
std Z+1,r4
std Z+2,r3
std Z+3,r2
ret
|
|
|
|
|
|
|
|
Mar 21 2011, 09:07
|
Профессионал
Группа: Свой
Сообщений: 1 143
Регистрация: 30-09-08
Из: Новочеркасск
Пользователь №: 40 581
|
всем в очередной раз спасибо. как обычно, в попытках объяснить свою проблему другим сам начинаешь понимать, в чем причина и решение находится  моя проблема была в том, что я не учел, что вышеприведенный мной код генерирует при каждом обращении ТОЛЬКО 1 СЛУЧАЙНЫЙ БИТ, а я использовал сразу три бита из "регистра"... сейчас я улучшил генератор ПСП, как мне кажется, до приемлемого уровня случайности, путем заполнения выходного числа тремя случайными битами. в очередной раз проблема, похоже, решена раньше, например, всегда после числа 7 можно было ожидать число 3, причем однозначно, сейчас же с более менее равной вероятностью приходят другие числа.
--------------------
Я бы взял частями... но мне надо сразу.
|
|
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|
