# Codebase64 wiki

### 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 +
+   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:

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
sta b1
lsr
eor a1
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

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