Генерация случайных чисел в сборке NASM

Question

Я работаю над университетским проектом в ассемблере.Единственная проблема в том, что я не могу сгенерировать даже случайное число между 162 и 278. Я перепробовал много алгоритмов, но, кажется, не могу ограничить число в диапазоне.

Есть ли небольшая хитрость или подстройка, чтобы получитьжелаемый номер в диапазоне?Цель состоит в том, чтобы случайным образом отображать фрукты на экране (в основном это змеиные игры).

Answer 1

Как написано в моем комментарии, вы можете использовать

 ((random_number % 59) + 81) * 2

Следующая сила Брэндона 2 - 1 проста, но вам нужно будет выбрать и реализовать генератор случайных чисел.Многие из этих генераторов случайных чисел представляют собой LCG, которые используют умножение и прибавление по модулю некоторой степени 2, однако, можно создать специально для модуля некоторой степени или кратного 59, что устранит необходимость отбрасывать слишком большие числа иповторите последовательность случайных чисел.Wiki статья об этом.

https://en.wikipedia.org/wiki/Linear_congruential_generator

Другой альтернативой может быть недвоичный код Галуа LFSR:

https://en.wikipedia.org/wiki/Linear-feedback_shift_register#Non-binary_Galois_LFSR

Однако, LFSR делаютне включают 0, поэтому они дают значения q ^ m - 1.Можно было бы проверить, когда LFSR возвращается в исходное состояние и в этот момент возвращает ноль, чтобы в итоге получить значения q ^ m.

Поскольку 59 - простое число, LFSR может использовать GF (59^ 2) основанный на примитивном полиноме 1x ^ 2 + 1x + 2 (есть много других примитивных полиномов для GF (59 ^ 2), но любой из них будет работать).Это переключит все 3480 ненулевых значений.Каждый раз, когда LFSR возвращается в исходное состояние, можно вывести ноль, чтобы в итоге получить 3481 (59 ^ 2) значений.Художественная версия Ascii для этого LFSR выглядела бы так (вся математика была бы% 59):

1x^2  1x     2

→    *1     *2 
↑     ↓      ↓
↑     +      +  
←   ┌━┐ ← ┌━┐
    └━┘   └━┘

Я сделал это и использовал младший член (значение b в ax + b), чтобы получитьнабор из 3481 значений, как показано в этом связанном с текстовым файлом:

http://rcgldr.net/misc/x3481.txt

Если вы хотите более длинный цикл (12117360 циклов + 1 цикл для нуля), вы можете использовать GF (59 ^ 4) на основе примитивного полинома 1x ^ 4 + 1x + 14:

1x^4 0x^3  0x^2   1x     14

→    →      →     *1    *14 
↑                  ↓      ↓  
↑                  +      +  
←   ┌━┐ ← ┌━┐ ← ┌━┐ ← ┌━┐
    └━┘   └━┘   └━┘   └━┘

Примечание. Я нахожу примитивные полиномы с помощью программы поиска методом грубой силы, чтобы найти LFSR, для которого требуется q ^ m-1 цикловповторить.

Answer 2

генерирует четное случайное число между 162 и 278

Шаг 1

"генерирует случайное число"
Задача показа фрукта в игре со змеямине слишком требователен, поэтому я думаю, что использование TimeStampCounter вполне нормально.Вы продолжите с низким dword, найденным в EAX.

-

rdtsc                        ; -> EDX:EAX

Шаг 2

"число между 162 и 278"
Ограничитьчисло до желаемого диапазона [162,278], вы рассчитываете
(RandomNumber mod NumbersInTheRange) + StartOfTheRange.

• RandomNumber - это регистр EAX с 1-го шага.
• NumbersInTheRange равно upper bound - lower bound + 1. Не забывайте, что + 1.
• StartOfTheRange - его нижняя граница.

-

xor     edx, edx             ; Required because there's no division of EAX solely
mov     ecx, 278 - 162 + 1   ; 117 possible values
div     ecx                  ; EDX:EAX / ECX --> EAX quotient, EDX remainder
mov     eax, edx             ; -> EAX = [0,116]
add     eax, 162             ; -> EAX = [162,278]

Шаг 3

"четное число"
Сделать число четным , опустив его младший бит.

-

and     eax, -2              ; -> EAX = {162,164,...,276,278}

Answer 3

Во-первых;Следует понимать, что (для генерации случайных чисел) по модулю "не степень 2" вызывает смещение и его следует избегать.Например, если вы хотите число от 0 до 2 и начните с 4-битного случайного числа (значения 0, 1, 2, .., 14, 15), то после «по модулю 3» значения станут 0, 0, 0, 1, 1, 1, ..., 4, 4, 4, 5) и значение 5 будет намного менее вероятным, чем любое другое значение.

Самый простой способ исправить "смещение, вызванноепо модулю non-power of 2 "означает маскирование (с AND) до следующей наибольшей степени 2 минус 1, затем сбросьте число и повторите попытку, если значение все еще находится вне диапазона.Например, если вы хотите число от 0 до 2 и начните с 32-битного случайного числа;вы должны сделать «число = число & (4-1)» (потому что 4 является следующей по величине степенью 2), а затем, если число больше 2, вы отбросите его и снова получите совершенно новое случайное число.

Сейчас ...

Если вы пытаетесь избежать "смещения, вызванного по модулю не-силы 2";почему бы не повторить попытку, если число оказалось четным в диапазоне от 162 до 278?

Например (в C):

#define MAX_VALUE         500
#define NEXT_POWER_OF_2   512

int getNumber(void) {
    int number;

    do {
        number = rand();
        number = number & (NEXT_POWER_OF_2 - 1);
    } while( (number > MAX_VALUE) || ((number >= 162) && (number <= 278) && (number & 1 == 0)) );
}

Для сборки:

;Input
; none
;
;Output
; eax = random number in range from 0 to MAX_NUMBER that is not an even number from 168 to 278

%define MAX_VALUE         500
%define NEXT_POWER_OF_2   512

getNumber:
    call getRandomDword         ;eax = random 32-bit value
    and eax,NEXT_POWER_OF_2-1   ;eax = random N-bit value
    cmp eax,MAX_VALUE           ;Is it too large?
    ja getNumber                ; yes, retry
    cmp eax,278                 ;Is it larger than the "not even" range?
    ja .done                    ; yes, allow the number
    cmp eax,162                 ;Is it smaller than the "not even" range?
    jb .done                    ; yes, allow the number
    test al,1                   ;Is it even?
    je getNumber                ; yes, retry

.done:
    ret

Примечание: я понятия не имею, нужен ли вам 16-битный, 32-битный или 64-битный код, или должен ли код работать на каких процессорах или каков источник случайности.Например, последние процессоры поддерживают инструкцию rdrand, которая является относительно медленной (она предназначена для криптографии, а не для скорости, но может использоваться для регулярного «повторного заполнения» генератора псевдослучайных чисел), но если вам нужно убедиться, что код работаетхорошо на старом 80386 тогда ...

Answer 4

Я немного выгляжу в этом посте: функция генератора случайных чисел nasm .Может быть, вы можете попробовать (rdtsc% (278 - 162) / 2 + 162/2) * 2. Я надеюсь, что помог вам:)