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

[introspec]

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

Чисто проговорю чтобы можно было понять со стороны: в этом конкретном тесте, найденная незнамо где процедура работает лучше 66т генератора.

---------- Post added at 17:49 ---------- Previous post was at 17:37 ----------

...но если бы ты замешал биты, как я показывал вот здесь: http://forum.tslabs.info/viewtopic.php?f=3&t=391 , или взял бы не первый, а второй генератор оттуда же, даже без замешивания, то получилось бы по крайней мере не хуже и всё ещё быстрее.

[denpopov]

кстати, такой вопрос - как получить случайное число из диапазона, например random(60)?

ничего другого в голову не пришло, как int(rnd()/255*60)

[psb]

можно rnd()%60

[Barmaley_m]

ничего другого в голову не пришло, как int(rnd()/255*60)

Все правильно. Только зачем делить на 255? Это нужно, только если исходные случайные числа находятся в диапазоне 0..255.

Остаток от деления и (что равносильно) выделение младших бит не рекомендуется делать в тех книгах, которые я читал о генераторах случайных чисел. Обычно "качество" старших бит в генераторах лучше.

[denpopov]

Только зачем делить на 255? Это нужно, только если исходные случайные числа находятся в диапазоне 0..255.

потому что под rnd() я имел в виду ту функцию, которая выдает случайное число.

[ram_scan]

потому что под rnd() я имел в виду ту функцию, которая выдает случайное число.

Брать остаток от деления, делить нацело, либо пользовать какой-то иной фрагмент от значения ГСЧ верно только в случае когда ГСЧ является именно ГСЧ (и то сильно не всегда).

Если оперировать цифровым ГПСЧ, то можно наступить на реальные грабли, и тут уже "какой кусочек брать если меня разрядность не устраивает" играет очень заметную роль.

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

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

[Advertiser]

[denpopov]

"какой кусочек брать если меня разрядность не устраивает

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

[ram_scan]

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

Если по степени двойки можно замаскировать старшие биты. Если не по степени двойки - поделить нацело или взять остаток от деления нацело.

Но качество результата очень сильно зависит от того как устроен генератор ПСЧ.

Никто не говорит что так нельзя делать. Так иногда нельзя делать. Если вас результат устраивает (вряд-ли вы пишете криптостойкую софтину, да и генераторы тут опубликованные не для таковой) то пользуйтесь на здоровье и не грейте себе голову =) Перфекционизм - не всегда хорошо.

[denpopov]

еще из раскопок, слишком много на винте скачанного файла. Субботник!

; Fast RND
;
; An 8-bit pseudo-random number generator,
; using a similar method to the Spectrum ROM,
; - without the overhead of the Spectrum ROM.
;
; R = random number seed
; an integer in the range [1, 256]
;
; R -> (33*R) mod 257
;
; S = R - 1
; an 8-bit unsigned integer

 ld a, (seed)
 ld b, a 

 rrca ; multiply by 32
 rrca
 rrca
 xor 0x1f

 add a, b
 sbc a, 255 ; carry

 ld (seed), a
 ret

[aGGreSSor]

Сижу с генераторами ПСЧ8 для Вектор-06Ц.
Написалось три генератора, все 3 - отстой и работают кое-как, но делюсь.
Если у кого-то есть лучше - дайте знать.

; random_xorshift
; вход:  E - верхняя граница
; выход: A - псевдослучайное число [0, E]
RND8:	push h
	push d
	lhld SEED ; Загружаем состояние
	; XOR-shift алгоритм
	mov a, h
	rrc         ; Сдвиг вправо
	mov h, a
	mov a, l
	rlc         ; Сдвиг влево
	mov l, a
	xra h       ; XOR между H и L
	mov h, a
	shld SEED ; Сохраняем новое состояние
	mov a, l ; Берем случайное число
	cmp e ; Ограничиваем диапазоном [0, E]
	jc RDONE
MLX:    sub e
	cmp e
	jnc MLX
RDONE:  pop d
	pop h
	ret

SEED:   db  13h

; RND Дениса Попова переводим на 8080, вариант №1
; вход:  E - верхняя граница
; выход: A - псевдослучайное число [0, E]
RND8:	lda SEED
	mov B,A
	stc      ; rrca 1
	cma
	rar
	cma
	stc      ; rrca 2
	cma
	rar
	cma
	stc      ; rrca 3
	cma
	rar
	cma
	xri 0x1f ; A=A xor 0x1f
	add B    ; A=A+B
	sbi 255  ; A=A-255-CY
	sta SEED
	cmp E
	jnc RND8 ; если >= E, генерим по новой
	ret

SEED:   db  13h

; RND Дениса Попова переводим на 8080, вариант №2
; вход:  E - верхняя граница
; выход: A - псевдослучайное число [0, E]
RND8:	lda SEED
	mov B,A
	rar     ; rrca 1
	jnc RR2
	ori 80h
RR2:	rar     ; rrca 2
	jnc RR3
	ori 80h
RR3:	rar     ; rrca 3
	jnc RR4
	ori 80h
RR4:    xri 0x1f
        add b
	sbi 255 ; приплыли
 	sta SEED
	cmp E
	jnc RND8 ; если >= E, генерим по новой
	ret

SEED:   db  13h

- - - Добавлено - - -

Есть ещё инновационный подход.
1) Пишем за минуту программу на питоне
2) Генерируем нужное нам кол-во псевдослучайных чисел в нужном диапазоне
3) Загоняем в таблицу
4) По этой таблице и ходим в своей программе, чтобы не иметь себе мозг. Enjoy