Быстрые генераторы ПСЧ на основе LFSR

by **introspec** » Mon, 07.04.2014 22:30:40

В процессе экспериментов, написал несколько генераторов псевдослучайных чисел (ПСЧ), с плавно растущим качеством случайных чисел (и плавно уменьшающейся скоростью). Идея у всех генераторов одна и та же: берётся LFSR по схеме Галуа (см. Wikipedia), разворачивается наоборот, чтобы заменить сдвиги сложением HL с самим собой, после чего подобраны полиномы, которые получше мешают биты и которые можно слегка соптимизировать в коде. Выбирай, но осторожно, но выбирай. Все генераторы возвращают результат в А, все портят HL, некоторые также портят BC. У каждого генератора указаны дополнительные команды для перемешивания битовых строк (без этих дополнительных команд возвращённые байты в А нельзя использовать как случайные числа). Если нужен именно один случайный бит за запуск - дополнительные команды можно выкинуть. Время исполнения указано и без, и с дополнительными командами.

Вариант 1: Длина последовательности 2¹⁶-1, вырожденный полином, время работы 66 тактов (для битов) или 66+15=81 тактов (для байтов).

Code: Select all: FastGalois16: ld hl, #FFFF ; 10 SeedValue: EQU $-2 add hl, hl ; 11 sbc a ; 4 and #BD ; 7 instead of #BD, one can use #3F or #D7 xor l ; 4 ld l, a ; 4 ld (SeedValue), hl ; 16 ; ================================= ld a, h and %10101010 add l ; +4+7+4 => +15t overhead ; ================================= ret ; 10 => 10+11+4+7+4+4+16 + 10 = 66t

Вариант 2: Длина последовательности 2¹⁶-1, полином получше, время работы 82 такта (для битов) или 82+11=93 такта (для байтов).

Code: Select all: Galois16: ld hl, #FFFF ; 10 SeedValue: EQU $-2 add hl, hl ; 11 sbc a ; 4 and #EB ; 7 instead of #EB one can use #AF ld c, a ; 4 xor l ; 4 ld l, a ; 4 ld a, c ; 4 xor h ; 4 ld h, a ; 4 ld (SeedValue), hl ; 16 ; ================================= and %10101010 add l ; +7+4 => +11t ; ================================= ret ; 10 => 10+11+4+7+4+4+4 + 4+4+4+16 + 10 = 82t

Вариант 3: Длина последовательности 2²⁴-1, вырожденный полином, время работы 90 тактов (для битов) или 90+11=101 такт (для байтов).

Code: Select all: FastGalois24: ld hl, #FFFF ; 10 Seed24_1: EQU $-2 ld a, #FF ; 7 Seed24_2: EQU $-1 add hl, hl ; 11 rla ; 4 ld (Seed24_2), a ; 13 sbc a ; 4 and #DB ; 7 instead of #DB one can use #F5 xor l ; 4 ld l, a ; 4 ld (Seed24_1), hl ; 16 ; ================================= and %10101010 add h ; +7+4 => +11t ; ================================= ret ; 10 => 10+7+11+4+13 + 4+7+4+4+16 + 10 = 90t

Вариант 4: Длина последовательности 2²⁴-1, полином получше, время работы 106 тактов (для битов) или 106+11=117 тактов (для байтов).

Code: Select all: Galois24: ld hl, #FFFF ; 10 Seed24_1: EQU $-2 ld a, #FF ; 7 Seed24_2: EQU $-1 add hl, hl ; 11 rla ; 4 ld (Seed24_2), a ; 13 sbc a ; 4 and #3F ; 7 instead of #3F one can use #3D or #6D ld c, a ; 4 xor h ; 4 ld h, a ; 4 ld a, c ; 4 xor l ; 4 ld l, a ; 4 ld (Seed24_1), hl ; 16 ; ================================= and %10101010 add h ; +7+4 => +11t ; ================================= ret ; 10 => 10+7+11+4+13+4+7+4+4+4 + 4+4+4+16 + 10 = 106t

Для каждого из этих генераторов важно проследить, чтобы затравочное значение внутренней константы не было нулём.

Все эти генераторы достаточно неплохи для включения в игру или демо, но качество полученных случайных чисел довольно невысоко по современным меркам. В то же самое время, я думаю, что эти генераторы качественнее любых сопоставимых по скорости генераторов ПСЧ на спектруме. Выбирать следует всегда самый медленный генератор из тех, что вы можете позволить себе по скорости. Если бы можете позволить себе потратить на генерацию случайного числа 120 или даже 150 тактов, есть смысл задуматься об использовании либо генератора на Xor-Shift (122 такта), либо генератора на Complimentary-Multiply-With-Carry (около 160 тактов, лень сейчас считать точно).

by **VBI** » Mon, 20.10.2014 21:11:57

интересно, каким макаром можно свести результаты до нужных пределов?
rnd (0,319) например

by **diver** » Tue, 21.10.2014 06:12:38

Вызывать 2 раза процедуру? Для старшего и младшего байта:)

by **VBI** » Tue, 21.10.2014 09:28:27

спасибо

Code: Select all: rasp_rand_view call Galois16 ld a,h and 1 ld h,a ld de,320 or a push hl sbc hl,de pop hl jr nc,rasp_rand_view

вот такое пользую. Ваши варианты?

by **den_p** » Tue, 21.10.2014 09:41:16

гоблин тут поделился процедуркой:

Code: Select all: sub_8981: ; CODE XREF: RAM:8449p RAM:8981 ; sub_8642+9p ... RAM:8981 ld de, unk_9DDA RAM:8984 ld h, e RAM:8985 ld l, 0FDh ; '¤' RAM:8987 ld a, d RAM:8988 or a RAM:8989 sbc hl, de RAM:898B sbc a, 0 RAM:898D sbc hl, de RAM:898F sbc a, 0 RAM:8991 ld e, a RAM:8992 ld d, 0 RAM:8994 sbc hl, de RAM:8996 jr nc, loc_8999 RAM:8998 inc hl RAM:8999 RAM:8999 loc_8999: ; CODE XREF: sub_8981+15j RAM:8999 ld (sub_8981+1), hl ; ?random RAM:899C ret

это 16 бит или нет?

by **TS-Labs** » Sat, 24.01.2015 14:48:44

А что скажете про такой (генератор из 'Elite'):

Code: Select all: RND ld a, (RSEED) ld c, a ld a, (RSEED + 1) ld (RSEED), a add a, c ld c, a ld a, (RSEED + 2) ld (RSEED + 1), a add a, c rlca ld (RSEED + 2), a ret RSEED defb 0, 0, 255

Про такты - ни слова. Меня интересует матанная часть. С указанным сидом он вывалил ряд из 16млн значений.

by **TS-Labs** » Sat, 24.01.2015 15:25:37

Слегка офтопик: как недетерминированно задать seed для рнд генератора?
Предлагается взять позицию внутри фрейма на момент запуска проги (замерить сколько тактов осталось до следующего фреймового инта).
Что скажете?

by **noleg** » Sat, 24.01.2015 17:33:50

один вопрос, для чего?

by **introspec** » Sat, 24.01.2015 18:02:15

TSL, пишут вот чего: http://wiki.alioth.net/index.php/Random ... _generator
С моей т.зр. выбор немного странный, в том смысле, что это не одна из вещей, которую вспоминают в списке методов генерации ПСЧ. Но нужно лезть в Кнута, у него там столько всего понаписано, что будет удивительно, если не окажется описан и такой подход.

В плане затравки, бери что-то зависящее от пользователя. Быстрый цикл, микросекунды, и выходи из цикла по нажатию клавиши - это и будет твоё случайное число. На спектруме я обычно беру один байт из системной переменной времени, а второй - из регистра R.

by **den_p** » Sat, 24.01.2015 18:30:50

introspec wrote:На спектруме я обычно беру один байт из системной переменной времени, а второй - из регистра R.

кстати, я до поры такую настройку seed убрал, проще отлаживать прогу, последовательность идет одинаковая.

by **TS-Labs** » Sat, 24.01.2015 19:11:45

noleg wrote:один вопрос, для чего?

Ну... Чтоб все СЛУЧЯЙНО было - неинтересно же когда флоу прецказуемый. Хе-хе. <_<

introspec wrote:Быстрый цикл, микросекунды, и выходи из цикла по нажатию клавиши - это и будет твоё случайное число.

Если софтина грузится с ленты или с флопа и запускается, то как раз текущий такт цпу во фрейме отличный выбор, потому что уже сработали задержки ленты/флопа, это не считая самого момента запуска лоадера.

den_p wrote:проще отлаживать прогу, последовательность идет одинаковая.

Это только на момент отладки, а потом надо как надо. :yes:

by **introspec** » Sat, 24.01.2015 19:36:10

Для реала - м.б., но там нет текущего такта. В эмуляторе даже загрузка с ленты повторяется до такта, так что приходится вводить человеческий фактор :)

by **den_p** » Sat, 24.01.2015 20:22:31

TS-Labs wrote: а потом надо как надо.

а потом еще неизвестно, как заработает

by **VBI** » Sat, 28.11.2015 14:10:43

дядькилёшкин генератор с пуета:
No, I did not, it needed better PRNG. To cut the long story short, a while ago I brute-forced all 16 and 24 bit Galous-type LSFRs, based on few types of polynomials that I knew could be efficiently implemented on Z80. BB uses the following 24-bit LSFR:
Code:

Code: Select all: ld a, c add ix, ix rla ld c, a sbc a and #DB ; instead of #DB you can use #B1, #F5, #1B, #DB or #87 xor ixl ld ixl, a

BB uses feedback constant #1B and a slightly different form of code, which is clumsier than this.

by **introspec** » Sat, 28.11.2015 19:24:16

Вова, нахер ты положил ещё раз генератор который уже есть выше? :)

by **g0blinish** » Sat, 28.11.2015 19:27:18

юзаю вот такую процедурку

Code: Select all: RANDOM: LD HL,(SEED+2) LD D,L ADD HL,HL ADD HL,HL LD C,H LD HL,(SEED) LD B,H RL B LD E,H RL E RL D ADD HL,BC LD (SEED),HL LD HL,(SEED+2) ADC HL,DE RES 7,H LD (SEED+2),HL JP M,RANDOM3 LD HL,SEED RANDOM2: INC (HL) INC HL JR Z,RANDOM2 RANDOM3: LD HL,(SEED) ret SEED: dw $E5,0

by **VBI** » Sat, 28.11.2015 21:59:37

introspec , очень странно, но я его там не увидел. своими раскосыми глазами.

ну да. почти как первый

Code: Select all: add hl, hl ; 11 sbc a ; 4 and #BD ; 7 instead of #BD, one can use #3F or #D7 xor l ; 4

by **introspec** » Sat, 28.11.2015 22:06:18

Почти как третий, надеюсь хотел сказать ты!

by **g0blinish** » Tue, 01.12.2015 13:13:09

Code: Select all: ; RANDOM: LD HL,(SEED+2) ; LD D,L ; ADD HL,HL ; ADD HL,HL ; LD C,H ; LD HL,(SEED) ; LD B,H ; RL B ; LD E,H ; RL E ; RL D ; ADD HL,BC ; LD (SEED),HL ; LD HL,(SEED+2) ; ADC HL,DE ; RES 7,H ; LD (SEED+2),HL ; JP M,RANDOM3 ; LD HL,SEED ; RANDOM2: INC (HL) ; INC HL ; JR Z,RANDOM2 ; RANDOM3: LD HL,(SEED) ; ret ; SEED: dw $E5,0

господа, поясните, откуда и зачем JP M ?

by **introspec** » Tue, 01.12.2015 13:21:23

Зачем юзать процедурки, смысла которых ты сам не понимаешь?

Чисто поверхностно - это похоже перенос старшего разряда в младший, что-то типа циклического сдвига. Но вообще, если честно, это выглядит как какая-то наговнокоженная херня (см., например, как в случае обнуления младшего байта на всякий случай инкрементируется следующий за ним байт).

by **g0blinish** » Tue, 01.12.2015 14:17:22

introspec wrote:Зачем юзать процедурки, смысла которых ты сам не понимаешь?

можно подумать, что ГСЧ в интернетах просто завались.

introspec wrote:Чисто поверхностно - это похоже перенос старшего разряда в младший,

вот именно, что поверхностно.

by **introspec** » Tue, 01.12.2015 14:35:54

Если не нравятся мои (которые все быстрее твоего уродца), взял бы xorshift или cmwc - ссылки делал для кого? ссылки в моём исходном посту - Patrik Rak даже заморочился погонять стандартные тесты на своих генераторах.

Твой генератор просто не нужен. Он написан неоптимально, он длинный, медленный и, чисто судя по внешнему виду, едва ли даёт последовательность максимальной длины. Кто-то что-то наговнокодил, а ты рад бяку в рот сунуть. Ну раз тебе он всё же нужен - ты и разбирай за пределами "поверхностно".

by **g0blinish** » Tue, 01.12.2015 15:17:13

introspec wrote:Кто-то что-то наговнокодил, а ты рад бяку в рот сунуть. Ну раз тебе он всё же нужен - ты и разбирай за пределами "поверхностно"

Ну ясно - ниасилил и просто отмазался. Возьму другую.

Генератор такой процедуры дважды испытан и дал неплохие результаты.

http://www.worldofspectrum.org/infoseek ... id=0024222

by **introspec** » Tue, 01.12.2015 15:32:01

1987 год, Карл!

by **psb** » Tue, 01.12.2015 15:51:26

g0blinish, JP M - это комментарий.

Быстрые генераторы ПСЧ на основе LFSR

Who is online