Быстрые генераторы ПСЧ на основе LFSR
Posted: Mon, 07.04.2014 22:30:40
В процессе экспериментов, написал несколько генераторов псевдослучайных чисел (ПСЧ), с плавно растущим качеством случайных чисел (и плавно уменьшающейся скоростью). Идея у всех генераторов одна и та же: берётся LFSR по схеме Галуа (см. Wikipedia), разворачивается наоборот, чтобы заменить сдвиги сложением HL с самим собой, после чего подобраны полиномы, которые получше мешают биты и которые можно слегка соптимизировать в коде. Выбирай, но осторожно, но выбирай. Все генераторы возвращают результат в А, все портят HL, некоторые также портят BC. У каждого генератора указаны дополнительные команды для перемешивания битовых строк (без этих дополнительных команд возвращённые байты в А нельзя использовать как случайные числа). Если нужен именно один случайный бит за запуск - дополнительные команды можно выкинуть. Время исполнения указано и без, и с дополнительными командами.
Вариант 1: Длина последовательности 216-1, вырожденный полином, время работы 66 тактов (для битов) или 66+15=81 тактов (для байтов).
Вариант 2: Длина последовательности 216-1, полином получше, время работы 82 такта (для битов) или 82+11=93 такта (для байтов).
Вариант 3: Длина последовательности 224-1, вырожденный полином, время работы 90 тактов (для битов) или 90+11=101 такт (для байтов).
Вариант 4: Длина последовательности 224-1, полином получше, время работы 106 тактов (для битов) или 106+11=117 тактов (для байтов).
Все эти генераторы достаточно неплохи для включения в игру или демо, но качество полученных случайных чисел довольно невысоко по современным меркам. В то же самое время, я думаю, что эти генераторы качественнее любых сопоставимых по скорости генераторов ПСЧ на спектруме. Выбирать следует всегда самый медленный генератор из тех, что вы можете позволить себе по скорости. Если бы можете позволить себе потратить на генерацию случайного числа 120 или даже 150 тактов, есть смысл задуматься об использовании либо генератора на Xor-Shift (122 такта), либо генератора на Complimentary-Multiply-With-Carry (около 160 тактов, лень сейчас считать точно).
Вариант 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 тактов, лень сейчас считать точно).