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

Программирование, алгоритмы

Postby introspec » Mon, 07.04.2014 22:30:40

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

Вариант 1: Длина последовательности 216-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: Длина последовательности 216-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: Длина последовательности 224-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: Длина последовательности 224-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 тактов, лень сейчас считать точно).
User avatar
introspec
 
Posts: 541
Joined: Sun, 14.07.2013 15:36:47

Postby VBI » Mon, 20.10.2014 21:11:57

интересно, каким макаром можно свести результаты до нужных пределов?
rnd (0,319) например
User avatar
VBI
 
Posts: 1582
Joined: Mon, 03.06.2013 09:20:29

Postby diver » Tue, 21.10.2014 06:12:38

Вызывать 2 раза процедуру? Для старшего и младшего байта:)
User avatar
diver
 
Posts: 830
Joined: Sat, 29.06.2013 00:10:07

Postby VBI » Tue, 21.10.2014 09:28:27

спасибо XD
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

вот такое пользую. Ваши варианты?
User avatar
VBI
 
Posts: 1582
Joined: Mon, 03.06.2013 09:20:29

Postby 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 бит или нет?
отключена за неуплату
User avatar
den_p
Говнокодер
 
Posts: 682
Joined: Mon, 15.09.2014 12:33:13

Postby 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млн значений.
User avatar
TS-Labs
 
Posts: 4420
Joined: Thu, 26.07.2012 01:29:56

Postby TS-Labs » Sat, 24.01.2015 15:25:37

Слегка офтопик: как недетерминированно задать seed для рнд генератора?
Предлагается взять позицию внутри фрейма на момент запуска проги (замерить сколько тактов осталось до следующего фреймового инта).
Что скажете?
User avatar
TS-Labs
 
Posts: 4420
Joined: Thu, 26.07.2012 01:29:56

Postby noleg » Sat, 24.01.2015 17:33:50

один вопрос, для чего?
[16:36:13] <TSL> 3. плаг под ВЦ будет писать пушкин. я ему звонил, он согласился
User avatar
noleg
 
Posts: 38
Joined: Mon, 12.08.2013 17:51:25

Postby introspec » Sat, 24.01.2015 18:02:15

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

В плане затравки, бери что-то зависящее от пользователя. Быстрый цикл, микросекунды, и выходи из цикла по нажатию клавиши - это и будет твоё случайное число. На спектруме я обычно беру один байт из системной переменной времени, а второй - из регистра R.
User avatar
introspec
 
Posts: 541
Joined: Sun, 14.07.2013 15:36:47

Postby den_p » Sat, 24.01.2015 18:30:50

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

кстати, я до поры такую настройку seed убрал, проще отлаживать прогу, последовательность идет одинаковая.
отключена за неуплату
User avatar
den_p
Говнокодер
 
Posts: 682
Joined: Mon, 15.09.2014 12:33:13

Postby TS-Labs » Sat, 24.01.2015 19:11:45

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

Ну... Чтоб все СЛУЧЯЙНО было - неинтересно же когда флоу прецказуемый. Хе-хе. <_<
introspec wrote:Быстрый цикл, микросекунды, и выходи из цикла по нажатию клавиши - это и будет твоё случайное число.

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

Это только на момент отладки, а потом надо как надо. :yes:
User avatar
TS-Labs
 
Posts: 4420
Joined: Thu, 26.07.2012 01:29:56

Postby introspec » Sat, 24.01.2015 19:36:10

Для реала - м.б., но там нет текущего такта. В эмуляторе даже загрузка с ленты повторяется до такта, так что приходится вводить человеческий фактор :)
User avatar
introspec
 
Posts: 541
Joined: Sun, 14.07.2013 15:36:47

Postby den_p » Sat, 24.01.2015 20:22:31

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

а потом еще неизвестно, как заработаетImage
отключена за неуплату
User avatar
den_p
Говнокодер
 
Posts: 682
Joined: Mon, 15.09.2014 12:33:13

Postby 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.
User avatar
VBI
 
Posts: 1582
Joined: Mon, 03.06.2013 09:20:29

Postby introspec » Sat, 28.11.2015 19:24:16

Вова, нахер ты положил ещё раз генератор который уже есть выше? :)
User avatar
introspec
 
Posts: 541
Joined: Sun, 14.07.2013 15:36:47

Postby 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

пердачок защеканца лвд после чтения моих постов..

[14:29:28] <Alone> На пентагоне картинки на бордюре рисуют. Это вообще нечестно

Теперь поезд ваш в депо, а мой локомотив мчится на укрепление демосцены спектрума.(с)Пиздунков
User avatar
g0blinish
Упырь говнофорума
 
Posts: 3441
Joined: Tue, 18.06.2013 10:59:01

Postby VBI » Sat, 28.11.2015 21:59:37

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

ну да. почти как первый
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
User avatar
VBI
 
Posts: 1582
Joined: Mon, 03.06.2013 09:20:29

Postby introspec » Sat, 28.11.2015 22:06:18

Почти как третий, надеюсь хотел сказать ты!
User avatar
introspec
 
Posts: 541
Joined: Sun, 14.07.2013 15:36:47

Postby 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 ?
пердачок защеканца лвд после чтения моих постов..

[14:29:28] <Alone> На пентагоне картинки на бордюре рисуют. Это вообще нечестно

Теперь поезд ваш в депо, а мой локомотив мчится на укрепление демосцены спектрума.(с)Пиздунков
User avatar
g0blinish
Упырь говнофорума
 
Posts: 3441
Joined: Tue, 18.06.2013 10:59:01

Postby introspec » Tue, 01.12.2015 13:21:23

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

Чисто поверхностно - это похоже перенос старшего разряда в младший, что-то типа циклического сдвига. Но вообще, если честно, это выглядит как какая-то наговнокоженная херня (см., например, как в случае обнуления младшего байта на всякий случай инкрементируется следующий за ним байт).
User avatar
introspec
 
Posts: 541
Joined: Sun, 14.07.2013 15:36:47

Postby g0blinish » Tue, 01.12.2015 14:17:22

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


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

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

вот именно, что поверхностно.
пердачок защеканца лвд после чтения моих постов..

[14:29:28] <Alone> На пентагоне картинки на бордюре рисуют. Это вообще нечестно

Теперь поезд ваш в депо, а мой локомотив мчится на укрепление демосцены спектрума.(с)Пиздунков
User avatar
g0blinish
Упырь говнофорума
 
Posts: 3441
Joined: Tue, 18.06.2013 10:59:01

Postby introspec » Tue, 01.12.2015 14:35:54

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

Твой генератор просто не нужен. Он написан неоптимально, он длинный, медленный и, чисто судя по внешнему виду, едва ли даёт последовательность максимальной длины. Кто-то что-то наговнокодил, а ты рад бяку в рот сунуть. Ну раз тебе он всё же нужен - ты и разбирай за пределами "поверхностно".
User avatar
introspec
 
Posts: 541
Joined: Sun, 14.07.2013 15:36:47

Postby g0blinish » Tue, 01.12.2015 15:17:13

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

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

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

http://www.worldofspectrum.org/infoseek ... id=0024222
пердачок защеканца лвд после чтения моих постов..

[14:29:28] <Alone> На пентагоне картинки на бордюре рисуют. Это вообще нечестно

Теперь поезд ваш в депо, а мой локомотив мчится на укрепление демосцены спектрума.(с)Пиздунков
User avatar
g0blinish
Упырь говнофорума
 
Posts: 3441
Joined: Tue, 18.06.2013 10:59:01

Postby introspec » Tue, 01.12.2015 15:32:01

1987 год, Карл!
User avatar
introspec
 
Posts: 541
Joined: Sun, 14.07.2013 15:36:47

Postby psb » Tue, 01.12.2015 15:51:26

g0blinish, JP M - это комментарий.
User avatar
psb
 
Posts: 575
Joined: Tue, 30.12.2014 23:22:32

Next

Return to Coding

Who is online

Users browsing this forum: No registered users and 1 guest

x