Generating random numbers, without the TI's randomization routines?

[jrhodes]

I am sure there is a better way to do this, but here is my first attempt at getting a random number that does not use the TI's randomization routines.

If you were going to write your own randomization routine for the TI, where would you start?

I suppose there is a good place to PEEK from memory, but i would like something that works regardless if the user has 32k or not, from both basic and XB.

[RXB]

RXB allows CALL PEEK(adddress,value) with no 32K required or needed.

 

So from console alone you peek the Random Numbers from the VDP countdown timer >8379

CALL PEEK(-32879,X) would give you a kind of a random number from 0 to 255

[Asmusr]

Are you looking for something faster or more random, or are you just interested in how random number generators work? It's difficult to help with the 'how' without knowing the 'why'.

[RXB]

Well he asked for a CALL with no 32K so the only one possible is RXB that can access Scratch Pad without 32K needed.

 

Without 32K and just Console can you name another way?

[+DZ-Jay]

I don't understand how that "randomization" routine works. The way we do random numbers in other platforms is by using Linear-Feedback Shift Register (LFRS), which is just a register that shifts its value by a number of bits, and in doing so applies a function (typically a simple XOR) on itself.

 

Thus, every new state is wholly determined by its previous state, but depending on the initial seed value, the sequence is pseudo-random. The initial seed is typically a polynomial.

 

I guess that if you have access to write it in machine code, you could get away with something serviceable that only takes a few bytes of code. In interpreted BASIC it may be too slow. Here's a sample implementation.

 

Another alternative -- and indeed, the one implemented in the game Doom -- is to run your pseudo-random number generator outside your program with a good seed, creating a pseudo-random sequence of numbers, and store that as an array of data in your program. Then, your program only has to read the next value in the array. Your game will be utterly deterministic, but by doing something like you had above to select a "random" entry point into the array, you could add a bit of entropy.

 

And if all you need is one random number, then that's even easier. just follow the advice in here.

 

-dZ.

[jrhodes]

Are you looking for something faster or more random, or are you just interested in how random number generators work? It's difficult to help with the 'how' without knowing the 'why'.

I am kind of interested in how R.N.G.'s in general work.

I wrote that program in post #1 originally as a personal aid for when i am reading a gamebook.

It is timer based, so depending on when you hit a key will directly effect the result... But when the gamebook says to roll as you are just reading along, it is easy to loose track of when the last key press was, so the results will more then likely still seem random to you at the time.

 

I am kind of curious what type of results i would get if i compiled the program, thus speeding up its execution time.

Edited September 8, 2018 by jrhodes

[jrhodes]

RXB allows CALL PEEK(adddress,value) with no 32K required or needed.

 

So from console alone you peek the Random Numbers from the VDP countdown timer >8379

CALL PEEK(-32879,X) would give you a kind of a random number from 0 to 255

I think TI XB allows CALL PEEK without 32k? But yes RXB really does have a lot going for it.

[Asmusr]

In machine code you could use an algorithm similar to this to generate a number between 0 and 65535 (one word). The first line is setting the seed, which determines the rest of the sequence.

10 R=357
20 R=R+27463
30 R=R*19365
40 R=R-65536*INT(R/65536)
50 PRINT R
60 GOTO 20

I don't think XB has a remainder function, so that's what line 40 does: calculates the remainder after division by 65536.

 

Note that this generates alternating odd and even numbers. In machine code you would bit-shift the result to break this pattern.

[RXB]

I don't understand how that "randomization" routine works. The way we do random numbers in other platforms is by using Linear-Feedback Shift Register (LFRS), which is just a register that shifts its value by a number of bits, and in doing so applies a function (typically a simple XOR) on itself.

 

Thus, every new state is wholly determined by its previous state, but depending on the initial seed value, the sequence is pseudo-random. The initial seed is typically a polynomial.

 

I guess that if you have access to write it in machine code, you could get away with something serviceable that only takes a few bytes of code. In interpreted BASIC it may be too slow. Here's a sample implementation.

 

Another alternative -- and indeed, the one implemented in the game Doom -- is to run your pseudo-random number generator outside your program with a good seed, creating a pseudo-random sequence of numbers, and store that as an array of data in your program. Then, your program only has to read the next value in the array. Your game will be utterly deterministic, but by doing something like you had above to select a "random" entry point into the array, you could add a bit of entropy.

 

And if all you need is one random number, then that's even easier. just follow the advice in here.

 

-dZ.

As I already said RXB does not check for 32K before it does a CALL PEEK or CALL LOAD thus is the ONLY XB made that can do a CALL PEEK of the VDP Count down timer.

It is pretty random, but not as random as the Random Number Generator, which you could also CALL PEEK directly from XB with no Assembly needed.

 

Yes TI Basic does not need a 32K to do a CALL PEEK or CALL LOAD, but TI Basic is really slow compared to XB let alone GPL or Assembly.

Edited September 9, 2018 by RXB

[+adamantyr]

My latest blog post covers random number generation in assembly language, the techniques described include most of the common variants.

[+Lee Stewart]

As a point of reference, this thread, RND and RAND: Pseudorandom Number Generation by TI Basic, details the GPL RAND function and the TI Basic RND function that calls it.

 

The above RAND function updates the random number seed (s) at >83C0 by this equation:

 

s' = s * 28645 + 31417

 

The developers of TI Forth (also used in fbForth) added a circular right shift (SRC) of 5 bits to improve the resulting distribution. However, it did shorten the number of iterations for repeats from 65536 to 26068.

 

s' = (s * 28645 + 31417) SRC 5

 

Both of the above equations generate reproducible pseudo-random sequences that aid program debugging. They are very simple to code in Assembler, but in TI Basic and XB, the circular right shift is definitely more challenging.

 

...lee

[+TheBF]

For what it's worth I was investigating/testing PRNGs in Forth. Lee Stewart helped me speed up a test routine

http://atariage.com/forums/topic/273872-camel99-forth-information-goes-here/page-8

 

The method I was testing came from GNU Forth. The method is so simple it's hard to believe it works, but when I compared it against the slightly more complicated method from TI-Forth it seems a little better.

It repeats every 64K numbers and gives similar "randomness" The calculations must all be integers. I tried it BASIC and it overflows.

 

GNU Method

 

1 SEED=1235

2 PRIME= 28649

3 SEED= INT(SEED*PRIME)+1

4 PRNG=INT(SEED)

 

 

SEED @ 6FE5 * 7AB9 + 5 SRC DUP SEED ! ; \ 28 bytes + SRC

 

I was scratching my head how to test these things I developed 2 tests.

One test is test repeatability in the sequence. It gets a random number and then gets new random #s until the first one shows up again.

The TI Forth method duplicates after 20,000 or so. The GNU Forth method goes for 64K numbers before repeating.

 

To see how random the numbers are I did this: (pseudo-code)

do
  Get a random screen position
  Getchar at random position
  If char is a space

  then put "A" at the position
       blank_cntr=blank_cntr-1

  else incr. char at the position
       duplicates=duplicates+1

   iterations=iterations+1

until blank_cntr=0

This test took over 6000 loops to fill the screen!

[matthew180]

Generating good random numbers on a computer is actually very hard. This topic was discussed before, in the Assembly thread I think, when I incorrectly made an assertion about TI's RNG function before I understood the details. The methods on the 99/4A are more or less the same as an LFSR in that they use every number in the data type (i.e. all 65536 values in a 16-bit number) before repeating. Starting with any given seed, the sequence of numbers is always the same. Tursi provided a routine (in assembly) that turned out to be the fastest (does not use multiply) and produced good results.

 

Edit: Here is a post where this topic came up, and I found a link to the original thread as well:

 

http://atariage.com/forums/topic/162941-assembly-on-the-994a/page-28?do=findComment&comment=3943708

https://atariage.com/forums/topic/163646-not-prime/

Edited September 11, 2018 by matthew180

[+TheBF]

Cool.

 

I think you mean this one.

! Calculate next random number, use r0 as seed and put result in r0 
       shlr r0         ! Shift r0 1 bit to the right, carry goes to T bit in status register 
       bf nocarry      ! If carry was not set, jump to label nocarry 
       xor #0xb400, r0 ! calculate new random number with 0xb400 as mask 
nocarry:

I will code this one up in Forth 9900 assembler and use the testing routines to see how it compares to the GNU Forth and TI Forth methods. I will try to get some timings on each one as well.

 

Another rabbit hole to run down...

[Tursi]

Be aware that routine is not amazing - it has a period of 16-bits (65535 values) with that mask, never returns 0, and returns every other number in the range exactly once before repeating. People using it for small random numbers (including myself) often find that the least significant bits don't change as often as we'd like (for this routine, smaller numbers are supposed to use a different mask), but I usually just worked around that by grabbing bits from the middle instead. It has those properties that make it interesting but it's not for every use.

Edited September 12, 2018 by Tursi