Генератор псевдослучайных чисел

[Titus]

А если построить огибающий колокол?

Алгоритм? Что за сумма величин?

[introspec]

Вот очень быстрый генератор ПСЧ на основе LSFR по схеме Галуа:

Galois16:		ld	hl, #FFFF		; 10
SeedValue:		EQU	$-2
			add	hl, hl			; 11
			sbc	a			; 4
			and	#BD			; 7	instead of #BD, one can use #2D, #39, #3F, #53 or #D7
			xor	l			; 4
			ld	l, a			; 4
			ld	(SeedValue), hl		; 16
			ret				; 10

Всего 66 тактов. С любым из перечисленных значений константы обратной связи, этот генератор даёт период в 65535 значений. Внимание: использовать 0 в качестве затравочной константы нельзя.

[Barmaley_m]

этот генератор даёт период в 65535 значений

LFSR дает хорошие случайные биты, но вот использовать все биты состояния в качестве 8- или 16-разрядных случайных чисел не рекомендуется: они все-таки довольно сильно коррелируют между соседними раундами работы генератора.

Любопытно, что несложной модификацией алгоритма можно заставить его "перескакивать" сразу на несколько бит, как будто подпрограмма была вызвана несколько раз. Если перескакивать каждый раз на 8 бит - то 8 из 16 разрядов такого генератора уже гораздо лучше подойдут в качестве 8-битных случайных чисел. Эта технология называется "Leap-ahead LFSR", можно погуглить и сразу найти описание.

[introspec]

LFSR дает хорошие случайные биты, но вот использовать все биты состояния в качестве 8- или 16-разрядных случайных чисел не рекомендуется: они все-таки довольно сильно коррелируют между соседними раундами работы генератора.

Это понятно. Кстати, с учётом скорости работы этого генератора, есть потенциал замесить биты, чтобы получался более-менее приличный "случайный" байт. Вот вариант на 30 тактов:

			add	h			; 4
			and	%10101010		; 7
			ld	h, a			; 4
			ld	a, l			; 4
			and	%01010101		; 7
			or	h			; 4

Пока что генератор Baze мне всё ещё нравится больше, но он работает 136 тактов, т.е. запас есть.

[introspec]

Я думаю, что вот это - самый быстрый генератор байтов "индустриального" качества:

rnd     ld  hl,0xA280   ; yw -> zt
        ld  de,0xC0DE   ; xz -> yw
        ld  (rnd+4),hl  ; x = y, z = w
        ld  a,l         ; w = w ^ ( w << 3 )
        add a,a
        add a,a
        add a,a
        xor l
        ld  l,a
        ld  a,d         ; t = x ^ (x << 1)
        add a,a
        xor d
        ld  h,a
        rra             ; t = t ^ (t >> 1) ^ w
        xor h
        xor l
        ld  h,e         ; y = z
        ld  l,a         ; w = t
        ld  (rnd+1),hl
        ret

Этот генератор был написан Патриком Раком (Patrik Rak) и опубликован на WoS в 2008 году. Процитированный выше код был слегка дооптимизирован Einar Saukas. Он выдаёт новый псевдослучайный байт за 122 тактa процессора.

Если скорость не критична, я бы рекомендовал использование именно этого генератора; он быстрее многих генераторов в этом треде, не требует большого буфера, а математически - намного, намного совершеннее LSFR.

[Titus]

Я думаю, что вот это - самый быстрый генератор байтов "индустриального" качества

А что за алгоритм в основе?

[introspec]

А что за алгоритм в основе?

Алгоритм называется Xor-Shift, вот ссылка на статью, описывающую идеологию таких генераторов: http://www.jstatsoft.org/v08/i14/paper
Партику пришлось заново пересчитать константы генератора, т.к. в статье основной упор на тройки 32-х битных слов, а Патрик переделал алгоритм для четвёрки восьмибитных, для удобства реализации на Z80.

[ram_scan]

Алгоритм называется Xor-Shift, вот ссылка на статью, описывающую идеологию таких генераторов:

Это классический образец генератора на сдвиговом регистре с обратной связью. Только насколько я понимаю он с 32битным "семечком". Полином считать мне лениво.

[introspec]

Это классический образец генератора на сдвиговом регистре с обратной связью. Полином считать мне лениво.

Да-да, так его, так, научите Джорджа Марсалью писать ГСЧ, научите...

[ram_scan]

Да-да, так его, так, научите Джорджа Марсалью писать ГСЧ, научите...

Ну, во первых если я что-либо в чем-либо понимаю то сверьху не M-генератор.

Во вторых зачем его учить ? Дональд Кнут всех в 50-е годы научил обобщив высшую математику для MIX машины. С той поры собсно ничего нового не придумали пока еще.

Достаточно открыть книжку и прочитать, не изобретая велосипеда. Я прочитал.