Сборник по задачам и примерам Assembler

       

Мультипликативный конгруэнтный метод генерации последовательности случайных чисел



Мультипликативный конгруэнтный метод генерации последовательности случайных чисел

Мультипликативный конгруэнтный метод задает последовательность неотрицательных целых чисел Xj (Xj<m), получаемых по формуле:

Хn+1=аХn(mod m). (2)

На значения накладываются ограничения:

  • Хо — нечетно;
  • а=52р+1 (р=0, 1, 2, ...) или a=2m+3 (m=3, 4, 5, ...) — обе эти записи означают, что младшая цифра а при представлении а в восьмеричной системе счисления должна быть равна 3 или 5 (проще говоря, остаток от деления а/8 должен быть равен 3 или 5);
  • m=2 (1>4).
  • При соблюдении этих ограничений, длина периода будет равна m/4.

    :randjnult_cong_l.asm - датчик линейной (мультипликативной) :конгруэнтной последовательности случайных чисел (с=0).

    :Вход: Хо. a, m - в соответствии с указанными выше ограничениями. .-Выход: dl - значение очередного случайного числа.

    .data

    in db 128

    a db 11



    х db 3 начальное значение

    .code

    ;первое число в последовательности х-3

    cycl: moval.x вычисляем очередное случайное число Х=(а*Х) mod in

    mul а :а*х в ah:al

    divm ;в ah случайное число

    mov x.ah ;вывод в файл - командная строка rand_mu1t_cong.exe > p.txt

    mov dl .ah

    mov ah.02

    nit г»

    jmp cyc1

    end cycl:

    Если m является степенью 2, как в данном случае, то вместо команды DIV мож-, но использовать две команды сдвига.

    ;----------------------------------------------------------

    ;rand_mult_cong_2.asm - датчик линейной (мультипликативной) конгруэнтной последовательности

    ;случайных чисел (c=0).

    ;Вход: X0, a, m - в соответствие с указанными выше ограничениями.

    ;Выход: dl - значение очередного случайного числа.

    ;----------------------------------------------------------

    masm

    model small

    .486

    .data

    m db 128 ;128=27

    a db 11

    x db 3 ;начальное значение

    .stack 256

    .486

    .code

    main:

    mov dx,@data

    mov ds,dx

    xor dx,dx

    mov cl,7 ;значение степени m=27 в cl

    ;первое число в последовательности x=3

    cycl:

    ;вычисляем очередное случайное число X=(a*X) mod m

    mov al,x

    mul a ;a*x в ah:al

    shrd ax,ax,cl


    xor al,al

    rol ax,cl ;в al случайное число

    ;вывод в файл - командная строка rand_mult_cong.exe > p.txt

    mov x,al

    mov dl,al

    mov ah,02

    int 21h

    jmp cycl

    end_cycl:

    mov ax,4c00h

    int 21h

    end main

    Используя эти программы, можно получить последовательность случайных чисел, содержащую 32 значения — это ее период. Чтобы увеличить период, необходимо каким-либо способом сгенерировать значения а или х, удовлетворяющие приведенным выше ограничениям. Так, значение а можно вычислить, используя фрагмент:

    .data

    :.........

    divider db 8

    .code

    вычисляем а исходя из соотношения:

    :а mod 8=5

    :одним из способов получить значение а (т > а)

    удовлетворяем условию a mod 8 = 5

    m2: mov al .a

    xor ah,ah

    div divider

    cmp ah,5 :остаток 5?

    je ml

    cmp ah,3 :остаток 3?

    je ml

    inc a

    jmp m2 ml: ;теперь а найдено до конца

    Изменить (увеличить) период можно, корректируя значение т, для чего необходимо будет исправить соответствующие команды в программах rand_mult_ cong_l.asm и rand_mult_cong_2.asm, ориентированные на определенную разрядность регистров. Существует другая возможность увеличения периода — использование смешанного конгруэ}1т)юго метода генерации последовательности случайных чисел.


    Содержание раздела