User Tools

Site Tools


base:ranged_random_numbers_with_even_distribution

Ranged Random Numbers with Even Distribution

(Well, “amortized” even distribution, but keep reading…)

Normally with a random number generator you get an 8-bit value 1). This gives you a random number with a range of 256 possible values, from 0 to 255. But what if you want a smaller range?

For ranges that are a power of two (2, 4, 8, 16, 32, 64, 128) this is easy. You can trim the value; just use some of the bits and throw out the rest by ANDing w/ zeros.

But what about other ranges that don't fit neatly into this list? What if you want a range of 25 values, 0 through 24, for randomly picking a screen row for example?

Well one stupid thing you could do is keep calling the RNG until you get a value within your range. This gets (slightly) less stupid if you trim the value to the nearest higher power-of-two as described above. But still stupid; how many calls with it take each time you need a number? Who knows?

What if instead, every time you get a value outside of your range you subtract a constant number to bring the value into your range. This works but then some of the random values have double the probability of showing up than the others. This is a lot of bias and will definitly bite you.

Finally, what if instead you subtracted a DIFFERENT number each time to bring the outside numbers into your range? Each call to the RNG is biased, but if the bias is moved around enough to evenly distribute it throughout your range, over time the random numbers will be evenly distributed.

I'm calling this an “amortized” even distribution.

Code Example

Here's a code example with a range of 25 (generates a value from 0 to 24); just 18 bytes plus the base RNG. (See the commented macro code below for a detailed explanation.)

        jsr random
        and #%00011111
        cmp #25
        bcc return
        sbc #25
    mod_offset = *+1
        sbc #00
        bcs +
        adc #25
    +   sta mod_offset
    return:
        rts

Demonstration

Here's a demo of it in action to show how evenly distributed the numbers are. It uses 3 separate copies of the code to generate numbers in 3 different ranges, then plots pixels on a hi-res screen:

rand-range-kruthers.zip

It uses a 64tass macro to build the RNGs and calls the macro like this:

rand25 #randrange 25, 2021
rand40 #randrange 40, $d00d
rand64 #randrange 64, $c64

The first argument is the range and the second is an optional 16-bit seed.

Macro

And finally here's the 64tass macro that can setup an RNG for any 8-bit range:

; Ranged Random Number Generator with (amortized) even distribution
; by Kruthers
;
; get random number from XABC, remove bits to get next highest power-of-2,
; then distribute random values throughout range
; does not touch X or Y registers
randrange .macro range, seed=$1100
    .cerror (\range < 2 || \range > 256), "Range must be from 2 to 256"
    .cerror (\seed < 0 || \seed > 65535), "Seed must be 16-bit value"
 
        ; XABC random number generator
        ; credit to Wil, who gives credit to EternityForest
        ; https://codebase64.org/doku.php?id=base:x_abc_random_number_generator_8_16_bit
        inc x1
        clc
    x1 = *+1
        lda #<\seed     ; x1
    c1 = *+1
        eor #$c2        ; c1
    a1 = *+1
        eor #>\seed     ; a1 (orig $11)
        sta a1
    b1 = *+1            ; b1
        adc #$37
        sta b1
        lsr
        eor a1
        adc c1
        sta c1
 
        ; determine nearest power-of-2 equal or greater than range
        .for pow2 in 2, 4, 8, 16, 32, 64, 128, 256
            .if pow2 >= \range
                .break
            .endif
        .endfor
 
        ; truncate random value to our power-of-2-range
        .if pow2 < 256
            and #(pow2-1)
        .endif
 
        ; if the given range already is a power of 2, we're done
        .if pow2 == \range
            rts
 
        ; otherwise we need to do more...
        .else
            ; if the random value is already within the desired range, we're done
            cmp #\range
            bcc return
 
            ; otherwise, we need to move the value to within in our range
            sbc #\range     ; carry already set
 
            ; then offset it (negatively) so as to distribute excess throughout the range
        mod_offset = *+1
            sbc #00         ; carry set b/c previous sbc will not go negative
            bcs update_offset
 
            ; add range if we went below zero
            adc #\range     ; carry already clear
 
        update_offset:
            sta mod_offset
        return:
            rts
 
        .endif
.endm

Note About The Underlying RNG

Don't use an LFSR as the underlying random number generator. They have some very obvious patterns in the returned numbers that get even worse when you trim off bits. For example I always saw a long run of zeros when testing out one of them.

Instead use something like Wil's XABC routine like I used above, it's excellent.

1)
I'm ignoring 16-bit or higher RNGs here
base/ranged_random_numbers_with_even_distribution.txt · Last modified: 2021-12-10 17:42 by kruthers