Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Random number generator causing divide overflows

vikingnoisevikingnoise Member Posts: 15
I've been working on a 16-bit real-mode game for several months now, and I've had a custom random number generator written and tested for a good portion of that. It uses DOS interrupt 21h function 2Ch to return the system time as a seed for some arbitrary math operations, and the random 16-bit number is returned in AX, like so:
[code] public Random
Random proc
push bx
push cx
push dx
call GetSystemTime
push cx
mov cl,8
shr dx,cl ;Move DH into DL
pop cx
mov dh,cl ;Move minutes from CL to DH
mov ax,dx ;Save to AX
mov cl,13h
rcr ax,cl ;Rotate right to monkey with bits.
mov bx,7
mul bx ;Multiply by 13h to monkey further.
pop dx
pop cx
pop bx
ret
Random endp

public GetSystemTime
GetSystemTime proc
push ax
mov ah,2Ch
int 21h
pop ax
ret
GetSystemTime endp
[/code]
I then use division to limit the range to only what I need, like pulling a random monster from a data table or rolling for attack, defense, and damage.

The problem is that when I use ranges of less than 10 I periodically get a divide overflow, with smaller ranges causing more of them. I'm using an 8-bit value in BL, but BH and DX are zeroed out so I can divide DX:AX by BX and leave the remainder in DX where it's a little more convenient.

Any ideas on how I can improve my RNG or better limit the range of numbers?

Comments

  • BretBret Member Posts: 114
    You're not posting the code where you do the actual division and generate the overflow error, but I think the only way you could get an overflow is if you're not really zeroing out DX like you think you are. No matter what values you have for AX & BX (except for BX = 0), you will never get an error if you DIV with DX = 0.

    You are using DIV rather than IDIV, aren't you?
  • vikingnoisevikingnoise Member Posts: 15
    Thanks for the reply. I discovered I was pulling the divisor out of an incomplete data table, one that I originally fleshed out with zeros. D'oh! I replaced all the relevant zeros with stand-in values and everything worked out (using DIV, that is).

    On the other hand, I still seem to be getting more of a pattern to my random numbers than I'd like. What's your opinion of my RNG code?
  • AsmGuru62AsmGuru62 Member Posts: 6,519
    [color=Blue]
    This one is very good generator and it is short - easy to do in ASM (few minutes basically):

    [link=http://en.wikipedia.org/wiki/Xorshift]http://en.wikipedia.org/wiki/Xorshift[/link]

    It will always begin with the same number, but you can use some value to skip numbers before you begin main sequence. For example, take a number of seconds passed since the day began and use it as a shift value.
    [/color]
  • BretBret Member Posts: 114
    Just some "random" (pun intended) thoughts here. There is a huge difference between "randomness" (in the mathematical sense) and "unpredictability".

    Most of the Random Number Generators (RNG's) I've seen are based on the use of a "seed" of some sort, and the next number in the "random" sequence simply uses the result of the previous calculation as the new seed. If you always start with the same seed value, you always get the same numbers. Many of these RNG's pass mathematical randomness tests (like Diehard) with flying colors, even though the numbers they generate are actually 100% predictable (if you know the algorithm that is being used, or always start with the same seed).

    As asmguru62 suggests, you can use a second level of "randomness" (actually, in the case of the time-of-day, it is really more unpredictable than it is random) to initialize the seed. This will certainly make it "feel" more unpredictable. Depending on exactly what you're trying to accomplish, this may be sufficient.

    I use an RNG in one of my programs that is specifically designed to generate unpredictable numbers (words), even though it fails miserably on mathematical randomness tests like Diehard. For the purpose I'm using it, the unpredictability is more important than the randomness (in the pure mathematical sense).

    If anybody is interested, I can publish it here. Keep in mind that it is a "slow" algorithm (MUCH slower than any of the seed-based algorithms). You can also download the source code for my DOS USB drivers from my web site ([link=http://bretjohnson.us]http://bretjohnson.us[/link]), and find the RNG code in USBUHCI.A36 (the source code for the UHCI host controller driver).
Sign In or Register to comment.