On Scaling random numbers.

[Whammo]

Say you're looking for a random number between 0 and 999, RND returns a number between 0 and 65,535.
How are you going to preserve your carefully crafted randomness?
999 requires 10 bits to represent. But that's 1023, there's 24 left over, a fraction off.
It's all easy-peasy until your range isn't a power of 2.
You could just throw away any random number larger than 1000 and call it done.
But why waste a good random number?
Back in the deep dark ages of 7th grade, when only Dick Tracy had cell phones,
I remember that you need the least common multiple. Great.

999 1023 um*

That's 1,021,977, it takes 20 bits to represent. But that's 1,048,575 there's 26,598 left over,
but because everything is scaled up, so everything divides evenly, this fraction's below our threshold.

include rnd

: rndmaze page
142 emit
begin $4d rnd 100/ $80 and
if 1+ then
rnd rnd 12 rshift
1023 um/mod nip
1024 + c! key? until
key drop page 14 emit ;

[jkotlinski]

Starting Forth introduces the helper word CHOOSE for this purpose: : CHOOSE ( u1 -- u2 ) RANDOM UM* NIP ; where CHOOSE returns a random integer within the range 0 = or < u2 < u1

…

On Wed, 13 Jul 2022 at 16:25, Whammo ***@***.***> wrote: Say you're looking for a random number between 0 and 999, RND returns a number between 0 and 65,535. How are you going to preserve your carefully crafted randomness? 999 requires 10 bits to represent. But that's 1023, there's 24 left over, a fraction off. It's all easy-peasy until your range isn't a power of 2. You could just throw away any random number larger than 1000 and call it done. But why waste a good random number? Back in the deep dark ages of 7th grade, when only Dick Tracy had cell phones, I remember that you need the least common multiple. Great. 999 1023 um* That's 1,021,977, it takes 20 bits to represent. But that's 1,048,575 there's 26,598 left over, but because everything is scaled up, so everything divides evenly, this fraction's below our threshold. include rnd : rndmaze page142 emitbegin $4d rnd 100/ $80 andif 1+ then rnd rnd 12 rshift1023 um/mod nip1024 + c! key? until key drop page 14 emit ; — Reply to this email directly, view it on GitHub <#439>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAY34O67SI4AYBMIEEKPUA3VT3GWJANCNFSM53O5RNTA> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[Whammo]

Here's a simple analysis of the method I used for random numbers between 0-999
I'm incrementing screen memory locations when it's number comes up, and stopping when 26 comes up.
You'll see at even this range it hits every point.
When it's through, hit a key, and it will clear the screen and display the:
Average of all points, the variation, the total iterations, and the last point hit.

require  rnd

: ud. <# #s #> type space ;

: viz page
1024 1000 0 fill
begin
rnd rnd 12 rshift
1023 um/mod nip dup
1024 + dup c@ 1+ dup rot c!
26 <> if drop else
0 s>d 2048 1024 do i c@ m+ loop
2dup
1000 um/mod key drop page
. . ud. .
exit then again
;

[lonetech]

Randomness is a tricky thing to characterize. For instance, you call rnd twice here, and there's absolutely no randomness in the second call; there's a 1 to 1 mapping from the result of the first. Therefore you only have at best 16 bits even if you assembled 16+16-12=20. Then you used um/mod to extract roughly 10 bits of value, but it's quite slow. (Technically the argument fits all over because rnd is only pseudorandom, but we consider this one reference to the generator.) The combination of bits discarded by rshift, mixed by the extra call to rnd, and reduced in weight past the decimal point by the division does mean the quality of these random numbers is roughly the same as rnd drop rnd. Because rnd takes an even number of calls to start repeating (2**16), that's about half of rnd itself, in the long run. But you did only 15k calls or so, so it never repeated either way and the double step just mixed more.

The CHOOSE method posted above uses a fixed point interpretation. If we consider rnd as a [0..1) fixed point value (0.16 bits), we can just multiply it with a scaling factor n and get a 16.16 result in the [0..n) range. From there we simply drop the fractional part and have as even a distribution as we could get.

This fits the pattern of using */ to scale with an additional optimization of never dividing, since the point was between words. 100/ does the same type of optimization at byte level. */ itself wouldn't do this right because you can't divide by $10000 with a 16 bit divisor, though you can get close.

[Whammo]

I believe that shifting bits off makes the sequence longer before it repeats.

[Whammo]

I will change that to a perhaps, but not the way I was doing it.

[lonetech]

It doesn't. rnd produces a sequence of 65536 16-bit numbers, one particular permutation of all possible values. If you ignore some of the bits produced, the sequence is the same length, but the number of possible values is smaller. That makes it possible, but not guaranteed, for the sequence to be shorter. Since the sequence is already the longest possible with the number of possible states, the only way to make it longer is to expand the state.

E.g. if we have a 3-bit state machine producing a sequence like [7, 4, 5, 0, 3, 6, 1, 2], and we only read the top bit, we get [1,1,1,0,0,1,0,0]. This doesn't shorten the sequence, but can't make it longer, either. But if it was [6, 3, 1, 4, 7, 0, 2, 5], the sequence would be [1,0,0,1,1,0,0,1], which is [1,0,0,1] repeated, so it would shorten.

What did shorten the sequence was consistently reading it in pairs. By calling rnd twice, you get something like [(7,4), (5,0), (3,6), (1,2)]. Every value is paired with the same adjacent value. This is because the sequence length divides evenly into the number of reads; e.g. if we were reading in threes, we'd get an interleaving pattern where numbers appear in different places: 745 036 127 450 361 274 503 612. This was 8*3=24 digits, the lowest common multiple of the sequence length and grouping length. But it's still only 8 values, as every digit fully determines which follow.

Some pseudorandom generators may shorten their outputs, e.g. using a 16-bit state to produce 8-bit values. As demonstrated here, this doesn't make their sequence longer, but since 8-bit values occur multiple times, you may not know where in the sequence you are by just reading one or a few times, even if you know what the sequence is. For instance, every possible pair of values occurs at least twice in [1,1,1,0,0,1,0,0]. It takes 3-5 reads to uniquely determine where in that sequence the generator is. If you knew reads always occurred in pairs, it would only take one pair read; [11 10 01 00] has no repeated values.

Another method to extend the randomness is to introduce external stimuli. For instance, if the state changed with timer interrupts or key presses, a program that doesn't observe or prevent those events can't predict when it changes. If the events mixed in are impossible for anyone to predict, we reach true randomness.

[Whammo]

I think I was just saying that the pseudo-random repeating sequence when viewed as a 16-bit window in a circular bit stream, which bit you start with will give a different sequence.

[Whammo]

Here's the similar sort of thing with the choose choice.
It's simple enough to do with any other sorts of randomness.
The cool thing about rndis that it can always return the same sequence.

marker foo
require  rnd

: ud. <# #s #> type space ;

: viz page
1024 1000 0 fill
begin 1000
rnd um* nip dup
1024 + dup c@ 1+ dup rot c!
26 <> if drop else
0 s>d 2048 1024 do i c@ m+ loop
2dup
1000 um/mod key drop page
. . ud. .
exit then again
;

[lonetech]

If you like the repeatability, also note that the state is stored in the variable seed. This is useful for things like generating a particular level consistently in a game.

[jkotlinski]

For the fun of it, another visualization!

require gfx
require rnd
variable p 318 allot
p 320 0 fill
$21 clrcol
hires
: choose rnd um* nip ;
variable x
variable y
: blood begin
320 choose x !
p x @ + y !
x @ y @ c@ plot
1 y @ +!
again ; blood

[Whammo]

Someone doesn't have to know what's going on to say, "Hey that's cool."
But if you even have an inkling of what it's doing, you might say, "That's way cool!"

[lonetech]

require gfx
require rnd
create ys 320 allot
: choose rnd um* nip ;
: blood
 ys 320 0 fill
 $21 clrcol
 hires
 begin
  320 choose
  dup ys +
  dup c@ dup 1+ rot c!
  plot
 again ; blood

Thank you for the demo! Comments:
variable and allot may not use contiguous regions in other implementations. create let me specify the desired size.
x was an index, y was a pointer, p was an array. Picked different naming.
Moved initialization so I could rerun the demo.
+! was doing word access to a byte array (including out of bounds)
Today I learned gfx plot does bound check
I wonder if 320 should be a constant

[Whammo]

320 is a constant.

: screen $ffed sys xr c@ 8 * ;

👍

[jkotlinski]

Neat!

…

On Tue, 26 Jul 2022 at 14:04, Yann Vernier ***@***.***> wrote: require gfx require rnd create ys 320 allot : choose rnd um* nip ; : blood ys 320 0 fill $21 clrcol hires begin 320 choose dup ys + dup c@ dup 1+ rot c! plot again ; blood Thank you for the demo! Comments: variable and allot may not use contiguous regions <https://forth-standard.org/standard/usage#usage:dataspace> in other implementations. create let me specify the desired size. x was an index, y was a pointer, p was an array. Picked different naming. Moved initialization so I could rerun the demo. +! was doing word access to a byte array (including out of bounds) Today I learned gfx plot does bound check I wonder if 320 should be a constant — Reply to this email directly, view it on GitHub <#439 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAY34O2CIEKC2ZL4HTJ5UELVV7H5HANCNFSM53O5RNTA> . You are receiving this because you commented.Message ID: ***@***.***>

[Whammo]

Adapted for two bytes of sid noise.
It seems to be a little more spiky.

require gfx
create ys 320 allot
: sidini ( -- )
$ffff $d40e !
$80 $d412 c! ;

: rnd ( -- c )
$D41B c@
$D41B c@ $100 * + ;

: choose rnd um* nip ;
: blood sidini
 ys 320 0 fill
 $21 clrcol
 hires
 begin
  320 choose
  dup ys +
  dup c@ dup 1+ rot c!
  plot
 again ; blood

[lonetech]

I was about to mention that or would be faster than +, but then I realized there's no 100* to match 100/ (like movhi in some processors). So here is one:

code 100* ( n -- n )
 lsb lda,x  msb sta,x
 0   lda,x  lsb sta,x
;code

: rnd ( -- n )
 $D41B c@
 $D41B c@ 100* or ;

If we were feeling explicit, including the $ prefix would clarify that 100 is in hex.

On a simple 8-bit processor like the 6502, byte swap operations like these are much faster than shifting wider words one bit at a time (as lshift and * do).

Quicker still would be a word combiner:

code lh>w ( lsb msb -- n )
 lsb lda,x
 msb 1+ sta,x
 inx, ;code

[Whammo]

You are on fire, my Brother!