Я тут провел небольшое исследование темы и обнаружил, что наука шагнула вперед за последние годы, так что линейный конгруэнтный генератор с его необходимостью деления отходит на второй план.
Современным наиболее широко применяемым, эффективным методом генерации случайных чисел является алгоритм Mersenne Twister. Если стандартные реализации ориентированы на сверхдлинный период повторения, то от ребят из Хиросимы существует реализация, ориентированная на малость потребляемых ресурсов. Она может подойти для Спектрума. Ее период повторения - 2^128-1, что намного лучше, чем практически реализуемые на Спектруме линейные конгруэнтные генераторы.
Вот ссылка на проект: https://github.com/MersenneTwister-Lab/TinyMT
Основные вычисления производятся в файле tinymt32.h, функции "tinymt32_next_state" и "tinymt32_temper". Всё остальное - вспомогательный код. Вот текст этих функций вместе с объявлением структуры состояния генератора:
Код:
struct TINYMT32_T {
uint32_t status[4];
uint32_t mat1;
uint32_t mat2;
uint32_t tmat;
};
inline static void tinymt32_next_state(tinymt32_t * random) {
uint32_t x;
uint32_t y;
y = random->status[3];
x = (random->status[0] & TINYMT32_MASK)
^ random->status[1]
^ random->status[2];
x ^= (x << TINYMT32_SH0);
y ^= (y >> TINYMT32_SH0) ^ x;
random->status[0] = random->status[1];
random->status[1] = random->status[2];
random->status[2] = x ^ (y << TINYMT32_SH1);
random->status[3] = y;
random->status[1] ^= -((int32_t)(y & 1)) & random->mat1;
random->status[2] ^= -((int32_t)(y & 1)) & random->mat2;
}
inline static uint32_t tinymt32_temper(tinymt32_t * random) {
uint32_t t0, t1;
t0 = random->status[3];
#if defined(LINEARITY_CHECK)
t1 = random->status[0]
^ (random->status[2] >> TINYMT32_SH8);
#else
t1 = random->status[0]
+ (random->status[2] >> TINYMT32_SH8);
#endif
t0 ^= t1;
t0 ^= -((int32_t)(t1 & 1)) & random->tmat;
return t0;
}
Copyright (c) 2011, 2013 Mutsuo Saito, Makoto Matsumoto,
Hiroshima University and The University of Tokyo.
All rights reserved.
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:
* Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.
* Redistributions in binary form must reproduce the above
copyright notice, this list of conditions and the following
disclaimer in the documentation and/or other materials provided
with the distribution.
* Neither the name of the Hiroshima University nor the names of
its contributors may be used to endorse or promote products
derived from this software without specific prior written
permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
Обратите внимание, что не используются операции умножения и деления, а только сдвиги и логические операции. Так что есть хороший шанс, что все это быстро заработает на Z80.
Лицензия - BSD
- - - Добавлено - - -
Нашел еще один, еще более быстрый, простой и качественный генератор - Xorshift.
Код вообще элементарный:
Код:
#include <stdint.h>
/* The state word must be initialized to non-zero */
uint32_t xorshift32(uint32_t state[static 1])
{
uint32_t x = state[0];
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
state[0] = x;
return x;
}
Никаких умножений и делений, только сдвиги и ксор. Период повторения - 2^32-1.
Сгенерировал 10000 чисел - вроде выглядят случайно, последовательность не повторяется, спектр белый. Так что скорее всего метод работает. Но выглядит до ужаса просто!
- - - Добавлено - - -
Навскидку код для Z80 (не тестировал)
Код:
; The RNG state (32 bits), must be initialized to nonzero
state: db 1
db 1
db 1
db 1
; Based on the current state of the RNG, updates the state to the next RNG. The result is saved into the state variable
; And also returned in DE:HL registers.
rand: ld hl,(state)
ld de,(state+2)
ld b,13
call shl
cal xorstate
ld b,17
call shr
call xorstate
ld b,5
call shl
jr xorstate
; Shift left a 32-bit number in DE:HL by B bits
shl: sla l
rl h
rl e
rl d
djnz shl
ret
; Shift right an unsigned 32-bit number in DE:HL by B bits
shr: srl d
rr e
rr h
rr l
djnz shr
ret
; Xors the current state (4 bytes) with DE:HL, returns result in both DE:HL and the state
xorstate:
ld bc,(state)
ld a,l
xor c
ld l,a
ld a,h
xor b
ld h,a
ld (state),hl
ld bc,(state+2)
ld a,e
xor c
ld e,a
ld a,d
xor b
ld d,a
ld (state+2),de
ret