8086 random number generator (not just using the system time)?

Question

I am using assembly 8086emu and I need a numbers generator for 8 numbers.
I tried to use this piece of code by @johnfound:

RANDGEN:         ; generate a rand no using the system time

RANDSTART:
   MOV AH, 00h  ; interrupts to get system time        
   INT 1AH      ; CX:DX now hold number of clock ticks since midnight      

   mov  ax, dx
   xor  dx, dx
   mov  cx, 10    
   div  cx       ; here dx contains the remainder of the division - from 0 to 9

   add  dl, '0'  ; to ascii from '0' to '9'
   mov ah, 2h   ; call interrupt to display a value in DL
   int 21h    
RET    

but it is useful only when you generate one number. Repeated calls get the same number, because that clock only ticks 18.2 times per second.

I've tried to create pseudo-random function but I am pretty new to assembly and I did not succeed. I would like to know if there's a way to do something similar to java's Math.random() function in emu8086.

Solution 1

One simple pseudo random number generator multiplies the current number by 25173, then adds 13849 to it. This value now becomes the new random number.
If you started from the system timer like you did (this is called seeding the random number generator), this series of numbers will be random enough for simple tasks!

MOV     AH, 00h   ; interrupt to get system timer in CX:DX 
INT     1AH
mov     [PRN], dx
call    CalcNew   ; -> AX is a random number
xor     dx, dx
mov     cx, 10    
div     cx        ; here dx contains the remainder - from 0 to 9
add     dl, '0'   ; to ascii from '0' to '9'
mov     ah, 02h   ; call interrupt to display a value in DL
int     21h    
call    CalcNew   ; -> AX is another random number
...
ret

; ----------------
; inputs: none  (modifies PRN seed variable)
; clobbers: DX.  returns: AX = next random number
CalcNew:
    mov     ax, 25173          ; LCG Multiplier
    mul     word ptr [PRN]     ; DX:AX = LCG multiplier * seed
    add     ax, 13849          ; Add LCG increment value
    ; Modulo 65536, AX = (multiplier*seed+increment) mod 65536
    mov     [PRN], ax          ; Update seed = return value
    ret

This implements a Linear Congruential Generator (LCG) with a power-of-2 modulus. %65536 happens for free because the low 16 bits of the product + increment are in AX, and the higher bits aren't.

Solution 2

Good idea, flawed execution. The code shown above generates a predictable pattern of even-odd-even-odd-even-odd et cetera. That's not very "random". Wikipedia warns that Linear Congruential Generators tend to be very random in their higher bits but not the lower ones. The fix is to insert SHR AX,5 right after you save the seed. The seed still flips even-odd-even-odd but the random number obtained from the seed ignores the five least significant bits. Here's what the end of CalcNew should look like:

    mov     [PRN], ax          ; Update seed
    shr     ax,5               ; Discard 5 bits
    ret

It doesn't have to be exactly five bits. I chose five because fewer than five isn't random enough but more than five eats away at your ability to choose how big a random number you want. AX is only 16 bits; after you discard five of them, you've got a random number between 0 and 2047, which is great for the next step of dividing by some number n and taking the remainder. When n is 10, 2047 is plenty. But your n might be larger, depending on the application. If you need a random ascii character, you'll be dividing by 96. And if you dropped, say, seven bits instead of five, you'd have a random AX from 0 to 511, which you'd be dividing by 96 to get a remainder. This would skew your results because lower remainders would happen more frequently than higher ones. So five bits is a good compromise, when you're using a 16-bit CPU.

Comments

[Koren Minchev]

Thank You! I researched the topic and made a linear congruential generator.

[Peter Cordes]

@MichaelPetch: yes, DX is dead at that point. We only want a 16x16 => 16-bit multiply. There's no extra entropy in DX, because given AX you can uniquely determine the value in DX. i.e. work backwards to find the 16-bit PRN seed that gives this AX and you can also calculate DX. So it doesn't make sense to call it a 32-bit return value in DX:AX.