Pseudo-Random Number Generator (PRNG)

Authoring Dialog
1

Could someone help me find a pseudo-random number generator?

More specifically, I need to find one (or more) with the following constraint: It must never generate a number greater than 16,383. (Some of you might recognize this as the highest number that can be represented by a single variable in Dialog.)

Any help – even a gesture in the right direction – would be appreciated.

2

It’s going to be tricky doing anything in Dialog because its maths functions don’t implement modular arithmetic - if the result is outside the bounds then it doesn’t wrap around, but fails or is unpredictable. It also doesn’t support any bitwise operations, which knocks out a bunch of PRNGs.

I think you could probably implement a really small linear congruential generator or Lehmer random number generator that wouldn’t go outside the bounds, but I don’t know which values will work best.

1 Like
3

Based on this doc (page 11), I think these values will work:

xn+1 = (axn + b) mod m

m = 2048
a = 5
b = 1

This should give you a full cycle PRNG from 0 to 2047. I think this is the biggest cycle LCG you can get that fits within 16383. It’s not a good PRNG by any means, but it’s something. Note that it alternates between odd and even numbers, i.e. the least significant digit cycles constantly. This could be problematic, depending on what you want to do with it.

2 Likes
4

This was so helpful! Thank you!

I have cobbled together some code that uses the modulo operation to obtain numbers within a range larger than what I want and division to obtain integer results within the desired range. In other words I have been effectively ignoring the less significant bits. The result still is not great, but I think it will do for my purposes.

Thanks again!

1 Like
5

Another idea is to use a 14-bit linear-feedback shift register (LFSR) with taps 0x3000, for a cycle of 11811. You could also sum the output of this and the LCG suggested by @Dannii to increase the range and get a longer period (with some repeats).

Here’s a way to implement the LFSR in Dialog:

(global variable (seed 1))

(get random $X)
        (seed $S)
        (if) ($S < 4096) (then)
                ($LowBits = $S)
                ($Carry = 0)
        (elseif) ($S < 8192) (then)
                ($LowBits = $S)
                ($Carry = 1)
        (elseif) ($S < 12288) (then)
                ($S minus 8192 into $LowBits)
                ($Carry = 1)
        (else)
                ($S minus 8192 into $LowBits)
                ($Carry = 0)
        (endif)
        ($LowBits plus $LowBits into $Shifted)
        ($Shifted plus $Carry into $X)
        (now) (seed $X)

Would you be helped by a Dialog feature to let you control the random seed of the built-in PRNG?

2 Likes
6

What elegant code! Thank you so much!

That is a good question! As I suspect you surmise, one of the main reasons I want more control over random number generation is so that I can repeat gameplay conditions when I am debugging. As I see it, it comes down to the trade-off between having a convenient authoring tool and the challenge of coding with certain constraints. I am leaning a bit more towards the challenge, which I find both joyful and educational (how else would I have learned about the pseudorandom number generators you and Danii introduced me to?). But I would not mind if you handed control of the seed to the author, and I would probably make use of the convenience myself on occasion.

1 Like